第十一届蓝桥杯[蓝桥杯2020年初赛] 七段码
小兰用七段码数码管来表示一种特殊的文字。 
上图显示了七段码数码管的图表。数码管中有7个 段能发光的二极管分别标记为a, b, c, d, e, f, g。 小兰应该选择一些二极管（至少一个）来发光来表达字符。在设计字符的表达时，所有发光的二极管都必须连接在一起。 例如：b 发光，其他二极管不发光可以用来表达一个字符。 例如：c 发光，其他二极管不发光可以用来表达一个字符。这个方案可以用来表示不同的字符，尽管它看起来很相似。 例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一个字符。 例如：b, f 如果其他二极管不发光，就不能用来表达一个字符，因为发光的二极管不连接在一起。 小蓝能用七段码数码管表达多少种不同的字符？
思路：
这个问题的状态不多(2的7种方种状态，每个开关2种)。只需列举所有状态，判断状态是否合法，统计合法状态即可
并查集 暴力
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 10; int e[N][N]; bool st[N]; int p[N]; int find(int x) {
if(p[x] != x) p[x] = find(p[x]); return p[x]; } int main() {
//存储两侧是否相连 e[1][2] = e[1][6] = 1; e[2][1] = e[2][7] = e[2]
[
3
]
=
1
; e
[
3
]
[
2
]
= e
[
3
]
[
7
]
= e
[
3
]
[
4
]
=
1
; e
[
4
]
[
3
]
= e
[
4
]
[
5
]
=
1
; e
[
5
]
[
4
]
= e
[
5
]
[
7
]
= e
[
5
]
[
6
]
=
1
; e
[
6
]
[
1
]
= e
[
6
]
[
7
]
= e
[
6
]
[
5
]
=
1
; e
[
7
]
[
2
]
= e
[
7
]
[
3
]
= e
[
7
]
[
5
]
= e
[
7
]
[
6
]
=
1
;
int ans
=
0
;
for
(
int i
=
1
;i
<
1
<<
7
;i
++
)
//一共2的7次方种可能（对应一个7位二进制，1代表开0代表关），且枚举的每一种状态都不同
{
memset
(st
,
0
,
sizeof st
)
;
for
(
int j
=
1
;j
<=
7
;j
++
)p
[j
]
= j
;
for
(
int j
=
0
;j
<
7
;j
++
)
if
(
(i
>>j
)
&
1
)st
[j
+
1
]
=
true
;
//这位为1代表开
for
(
int k
=
1
;k
<=
7
;k
++
)
for
(
int j
=
1
;j
<=
7
;j
++
)
if
(e
[k
]
[j
]
&&st
[k
]
&&st
[j
]
)
//是否相邻，且是否都开了
{
int pk
=
find
(k
)
;
int pj
=
find
(j
)
;
if
(pk
!= pj
) p
[pk
]
=pj
;
//归到同一个父节点中
}
int cnt
=
0
;
for
(
int j
=
1
;j
<=
7
;j
++
)
if
(st
[j
]
&& p
[j
]
==j
)cnt
++
;
if
(cnt
==
1
)ans
++
;
} cout
<< ans
;
}