当前位置: 首页 > news >正文

深圳网站建设外贸公司网络推广代理怎么做

深圳网站建设外贸公司,网络推广代理怎么做,金华网站建设公司哪家好,美国服务器日本服务器网站【题目描述】 七段码 HUSTOJ 题目导出文件 [蓝桥杯2020] 第十一届蓝桥杯第二次省赛—填空题E题 七段码 小蓝要用七段码数码管来表示一种特殊的文字。 上图给出了七段码数码管的一个图示,数码管中一共有 7 段可以发光的二 极管,分别标记为 a, b, c,…

【题目描述】

七段码 HUSTOJ 题目导出文件

[蓝桥杯2020] 第十一届蓝桥杯第二次省赛—填空题E题

七段码

小蓝要用七段码数码管来表示一种特殊的文字。
在这里插入图片描述

上图给出了七段码数码管的一个图示,数码管中一共有 7 段可以发光的二
极管,分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管(至少要有一个)发光来表达字符。在设计字符的表达时,要求所有发光的二极管是连成一片的。
例如:b 发光,其他二极管不发光可以用来表达一种字符。
例如:c 发光,其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符,尽管看上去比较相似。
例如:a, b, c, d, e 发光,f, g 不发光可以用来表达一种字符。
例如:b, f 发光,其他二极管不发光则不能用来表达一种字符,因为发光的二极管没有连成一片。请问,小蓝可以用七段码数码管表达多少种不同的字符?

【题目考点】

1. 深搜(子集树)

2. 图论 连通图(并查集,深搜)

【解题思路】

七段数码管中每个管是一个顶点,相邻的管之间有一条边,建立无向图:
在这里插入图片描述
一些数码管亮,相当于在图中选择一些顶点,让这些顶点对应的数码管亮起,其它数码管不亮。要求选择的数码管连成一片,也就是选择的顶点和选择顶点之间的边构成的子图必须是连通图。
选择的顶点是所有顶点的子集,通过深搜子集树遍历每种可能的选择顶点的方案。
对于每种选择顶点的方案,判断选择的顶点,及选择顶点之间的边构成的子图是不是连通图。
判断一个图是否是连通图,可以使用并查集,也可以使用深搜的方法。

【题解代码】

答案:80

解法1:邻接矩阵 并查集判断连通图

#include<bits/stdc++.h>
using namespace std;
#define N 10
int fa[N], ans;
int edge[N][N];
bool sel[N];//sel[i]:管i亮了 
void init(int n)
{for(int i = 1; i <= n; ++i)fa[i] = i;
}
int find(int x)
{if(fa[x] == x)return x;elsereturn fa[x] = find(fa[x]);
}
void merge(int x, int y)
{fa[find(x)] = find(y);
}
void addEdge(int u, int v)
{edge[u][v] = edge[v][u] = 1;
}
void initGraph()
{addEdge(1, 2);addEdge(2, 3);addEdge(3, 4);addEdge(4, 5);addEdge(5, 6);addEdge(6, 1);addEdge(6, 7);addEdge(5, 7);addEdge(2, 7);addEdge(3, 7);
}
bool check()//判断是否是连通图 
{init(7);int ct = 0;for(int i = 1; i <= 7; ++i)for(int j = 1; j <= 7; ++j)if(edge[i][j] && sel[i] && sel[j])merge(i, j);for(int i = 1; i <= 7; ++i)if(fa[i] == i && sel[i])//管i亮着且是根结点 ct++;return ct == 1;
}
void dfs(int k)//管k是否亮
{if(k > 7){if(check())ans++;return;}dfs(k+1);sel[k] = true;dfs(k+1);sel[k] = false; 
} 
int main()
{init(7);initGraph();dfs(1);cout << ans;return 0;
} 

解法2:邻接表 深搜判断连通图

#include<bits/stdc++.h>
using namespace std;
#define N 10
int ans;
vector<int> edge[N];
bool vis[N], sel[N];//sel[i]:管i亮了 
void addEdge(int u, int v)
{edge[u].push_back(v);edge[v].push_back(u);
}
void initGraph()
{addEdge(1, 2);addEdge(2, 3);addEdge(3, 4);addEdge(4, 5);addEdge(5, 6);addEdge(6, 1);addEdge(6, 7);addEdge(5, 7);addEdge(2, 7);addEdge(3, 7);
}
void dfsGraph(int u)//对图做深搜
{for(int v : edge[u]){if(sel[v] && vis[v] == false)//注意只能访问已选择的顶点{vis[v] = true;dfsGraph(v);}}
}
bool check()//判断是否是连通图 
{memset(vis, 0, sizeof(vis));int ct = 0;//连通分量个数 for(int v = 1; v <= 7; ++v){if(sel[v] && vis[v] == false){ct++;//连通分量个数增加1 vis[v] = true;dfsGraph(v);}}return ct == 1;//如果连通分量个数不为1,则不是连通图 
}
void dfs(int k)//管k是否亮
{if(k > 7){if(check())ans++;return;}dfs(k+1);sel[k] = true;dfs(k+1);sel[k] = false; 
} 
int main()
{initGraph();dfs(1);cout << ans;return 0;
} 
http://www.yidumall.com/news/14490.html

相关文章:

  • 衡阳微信网站开发营销方案推广
  • 安全的合肥网站建设百度实名认证
  • 舆情中心百度seo排名优化公司
  • 企业网站欣赏网络营销成功案例
  • 做视频资源网站有哪些邵阳seo优化
  • 国安中建建设集团网站真正永久免费网站建设
  • 网站模块是啥简述seo
  • 可以做彩票广告的网站吗竞价推广开户
  • html网页开发武汉搜索引擎排名优化
  • 广州专业做网站建设网络营销主要内容
  • 成都科技网站建设电话多少钱电子商务
  • 北京管庄网站建设公司seo知识点
  • 做视频点播网站如何赚钱seo关键词排名优化怎样
  • 德州金航网络公司网站建设cilimao磁力猫在线搜索
  • 最好的网站建设组织深圳百度快速排名提升
  • wordpress无法选择服务器配置长沙网站推广排名优化
  • 云服务器 可以做网站吗淄博网站seo
  • 大气网站欣赏危机公关
  • wordpress阿里云数据库标题优化
  • 自动优化网站建设热线营销策划书模板范文
  • wordpress 4.5.2 中文西安网络推广seo0515
  • 淘宝小程序开发文档重庆百度seo
  • 淘宝哪些做网站关键词排名的有用吗hao123网址之家官网
  • 登录网站怎么做自助建站系统哪个好用
  • 广州开公司的基本流程及费用宁波seo推广优化哪家强
  • 文件传输协议登陆网站校园推广方案
  • 有什么网站建设比较好的公司互联网营销师证书
  • wordpress添加网站地图优化标题关键词技巧
  • wordpress 采集 json免费下优化大师
  • 高端企业网站建设流程网站seo快速排名优化