试题 D: 七段码
本题总分：10 分
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示
数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。
在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如：b 发光，其他二极管不发光可以用来表达一种字符。
例如：c 发光，其他二极管不发光可以用来表达一种字符。
这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。
例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
这是一道结果填空的题
你只需要算出结果后提交即可
本题的结果为一个整数
在提交答案时只填写这个整数
填写多余的内容将无法得分
这是一道需要判断连通的问题
那么我们就会很自然的想到运用并查集解题
能够运用连通分量个数判断是否满足条件
这里运用到了并查集列表法模板
那么首先我们需要表示出二极管和两个二极管间的关系:
我们可以用0到6表示七个二极管
用7 * 7的矩阵记录与其相连的管儿
先运用numpy下的zeros设置一个7 * 7的全是0的矩阵
将每一行表示为一个管儿
接着将与其相连的管儿对应的索引变为1
那么我们就记录了二极管间的对应连接关系
二极管表示数字有1个管儿发光到7个管儿发光七种选择
那么我们先将二极管（0到6）放置在num中
遇到需要拿取的管道我们再拿取
之后我们从1个管儿到7个管儿开始拿取
在取用管道时我们需要将其取用的方法进行全排列
这里用到combination随机无放回抽样
保证这样点亮没有重复
在取用时我们每次实例化一个7个节点的并查集
对于每一个取用的二极管
都需要将其与临近且点亮的二极管进行节点合并
在这里我们先取用相应个数的二极管
之后逐个二极管判断与其临近的二极管是否被取用（点亮）
如果被点亮则将这两个节点进行合并
合并之前一定要保证两个节点的索引都是整数的形式
否则并查集列表索引会报错
每连接一次会减少一个连通分量
被取用（点亮）的二极管若能满足条件
就会形成一个连通分量
初始有7个连通分量
减去被点亮的二极管个数加上新形成的连通分量数1
则剩下的就是满足条件的连通分量个数
以上所有筛选条件都满足后res的值加一
最后输出res的值就是所求
import numpy as np
import itertools as it
class UnionFind:
def __init__(self, n):
self.father = list(range(n))
self.size = [1] * n
# 当前连通分量数目
self.setCount = n
def find(self, x):
if self.father[x] == x:
return x
self.father[x] = self.find(self.father[x])
return self.father[x]
def merge(self, x, y):
x, y = self.find(x), self.find(y)
if x == y:
return False
if self.size[x] < self.size[y]:
x, y = y, x
self.father[y] = x
self.size[x] += self.size[y]
self.setCount -= 1
return True
res = 0
data = list(np.zeros((7, 7)))
data[0][1] = data[0][5] = 1
data[1][0] = data[1][6] = data[1][2] = 1
data[2][1] = data[2][3] = data[2][6] = 1
data[3][2] = data[3][4] = 1
data[4][3] = data[4][5] = data[4][6] = 1
data[5][0] = data[5][4] = data[5][6] = 1
num = [i for i in range(0, 7)]
for i in range(1, 8):
total = it.combinations(num, i)
for j in total:
uf = UnionFind(7)
for z in j:
for k in range(len(data[z])):
z = int(z)
b = int(data[z][k])
if b == 1 and k in j:
uf.merge(z, k)
if uf.setCount == 7 - len(j) + 1:
res += 1
print(res)
80