蓝桥杯 七段码 python （2020）
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二 极管，分别标记为 a,b,c,d,e,f,g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。
例如：b 发光，其他二极管不发光可以用来表达一种字符。
例如 c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如：a,b,c,d,e 发光，f,g 不发光可以用来表达一种字符。
例如：b,f 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
思路
思路还是比较简单的，也就是利用并查集，首先写一个并查集的模板
对于我们的题来说，我们练成一片的不仅仅只有abcdef连在一起是相通的，同时比如gb连在一起也是相通的，所以不能用简单的二项式定理来解决这道题，所以我们就利用并查集来实现，对于并查集来说，如果都是一个父亲节点，就说明是相同的，用这样的思路就可以将我们的答案写出来，具体可以看代码
code
# https://www.lanqiao.cn/problems/595/learning/ import itertools class UnionFindSet(): def __init__(self,n): self.count = 0 # 当前连通分量数目 # self.count = n # 不连通区域 self.father=[x for x in range(n)] def find(self,x): root = x while self.father[root]!=root: # 找根节点 root=self.father[root] # 路径压缩 while x != root: o = self.father[x] # 找x的父节点 self.father[x] = root # 把x的父节点设置成刚才找到的根 x = o # 往上一层 return root def union(self,x,y): x,y=self.find(x),self.find(y) if x != y: self.father[y]=x # 合并 self.count +=1 return 0 result = 0 nums = [x for x in range(7)] for x in range(1,8): # 每次用的晶体管个数 for k in itertools.combinations(nums, x): #从所有的晶体管中按个数要求不重复的拿。 l = len(k)#晶体管的个数 ufs = UnionFindSet(l) #两两的逐个选取 for a in range(l): for b in range(a+1,l): #根据下图的数字判断两个晶体管是否相邻。 if abs(k[a]-k[b])==1 or (k[a]==1 and k[b]==6) or (k[a]==2 and k[b]==6) or (k[a]==4 and k[b]==6) or (k[a]==0 and k[b]==5): ufs.union(a,b) if l-ufs.count==1: #比如当用到三个二极管的时候只需要链接两次，那么当晶体管个数减去链接次数为1的时候符合要求。 result += 1 print(result)
答案
80
