网站建设属于什么经济科目,免费推广网站58,网站维护套餐,html怎么设置网页背景图片【题目描述】
七段码 HUSTOJ 题目导出文件
[蓝桥杯2020] 第十一届蓝桥杯第二次省赛—填空题E题
七段码
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示#xff0c;数码管中一共有 7 段可以发光的二 极管#xff0c;分别标记为 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邻接矩阵 并查集判断连通图
#includebits/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(k1);sel[k] true;dfs(k1);sel[k] false;
}
int main()
{init(7);initGraph();dfs(1);cout ans;return 0;
} 解法2邻接表 深搜判断连通图
#includebits/stdc.h
using namespace std;
#define N 10
int ans;
vectorint 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(k1);sel[k] true;dfs(k1);sel[k] false;
}
int main()
{initGraph();dfs(1);cout ans;return 0;
}
