第十一届蓝桥杯第二次省赛—填空题E题. 七段码
题目描述：
小蓝要用七段码数码管来表示一种特殊的文字。 上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二 极管，分别标记为 a, b, c, d, e, f, g。 小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。 例如：b 发光，其他二极管不发光可以用来表达一种字符。 例如：c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。 例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。 例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。 请问，小蓝可以用七段码数码管表达多少种不同的字符？
答案：80
思路： dfs搜索所有状态，判断每种状态可不可行。判断的方法是把每条灯管当作一个节点，连边建图，每次并查集判断当前选中的灯管是否在同一个集合。
程序：
#include<bits/stdc++.h> using namespace std; const int N=10; int use[N],ans,e[N][N],fa[N]; void init(){ //连边建图，e[i][j]==1表示i和j相邻 //a b c d e f g //1 2 3 4 5 6 7 e[1][2]=e[1][6]=1; e[2][1]=e[2][7]=e[2][3]=1; e[3][2]=e[3][4]=e[3][7]=1; e[4][3]=e[4][5]=1; e[5][4]=e[5][6]=e[5][7]=1; e[6][1]=e[6][5]=e[6][7]=1; } int find(int u){if(fa[u]==u)return u;fa[u]=find(fa[u]);return fa[u];}//并查集 void dfs(int d){ if(d>7){ /* 并查集判联通 */ for(int i=1;i<=7;i++)fa[i]=i; for(int i=1;i<=7;i++) for(int j=1;j<=7;j++) if(e[i][j]&&use[i]&&use[j]){ int fx=find(i),fy=find(j); if(fx!=fy){ fa[fx]=fy; } } int k=0; for(int i=1;i<=7;i++)if(use[i]&&fa[i]==i)k++; if(k==1)ans++; return; } use[d]=1;//打开d这个灯，继续开关下一个灯 dfs(d+1); use[d]=0;//关闭d这个灯，继续开关下一个灯 dfs(d+1); } int main(){ init(); dfs(1); cout<<ans; }后记： 赛场上为了省事，图都建好了但是没写并查集判联通，只用了暴力判边是否有连边，却忘记了还可能出现两个联通块不联通的情况TvT 白白丢了15分
