第十一届蓝桥杯 ——七段码

题目描述
小蓝要用七段码数码管来表示一种特殊的文字。

上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。

小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。

• 例如：b 发光，其他二极管不发光可以用来表达一种字符。

• 例如：c 发光，其他二极管不发光可以用来表达一种字符。

这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。

• 例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。

• 例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。

请问，小蓝可以用七段码数码管表达多少种不同的字符？

答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

答案：80

题解一
位运算 & 打印图案 & 人眼观察：

x >> i & 1：判断数字 x 的二进制排列中，第 i 位是否为 1；

#include <iostream>
using namespace std;

int main()
{
	int cnt = 1;			
	for (int x = 1; x <= 127; x ++)
	{
		cout << "====" << cnt ++ << "====" << endl;
		for (int i = 0; i < 7; i ++)
		{
			if(i == 0)
			{
				if(x >> i & 1) cout << " --";
				cout << endl;
			}
			if(i == 1)
			{
				if(x >> i & 1) cout << '|';
				else cout << " ";
			}
			if(i == 2)
			{
				if(x >> i & 1) cout << "  |";
				cout << endl;
			}
			if(i == 3)
			{
				if(x >> i & 1) cout << " --";
				cout << endl;
			}
			if(i == 4)
			{
				if(x >> i & 1) cout << '|';
				else cout << " ";
			}
			if(i == 5)
			{
				if(x >> i & 1) cout << "  |";
				cout << endl;
			}
			if(i == 6)
			{
				if(x >> i & 1) cout << " --";
				cout << endl;
			}
		}
		cout << endl;
	}
	
	return 0;
}

题解二
DFS && 并查集：

解题思路：

1. 用 1 ~ 7 来代表 a ~ g；
2. 若某两个二极管相邻，那么就在它们之间连一条边；
3. 先用 dfs 枚举出二极管的所有亮灭情况；
4. 再用 并查集 判断是否只有一个连通块；

#include <iostream>
using namespace std;

const int N = 10;

int ans;
int p[N];
bool st[N];
int e[N][N];

int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}

void dfs(int u)
{
	if(u == 8)
	{
		for (int i = 1; i <= 7; i ++) p[i] = i;
		
		for (int i = 1; i <= 7; i ++)
			for (int j = 1; j <= 7; j ++)
				if(e[i][j] && st[i] && st[j])
					p[find(i)] = find(j);
		
		int cnt = 0;
		for (int i = 1; i <= 7; i ++)
			if(st[i] && p[i] == i)
				cnt ++;
		
		if(cnt == 1) ans ++;
		return;				
	}
	
	st[u] = 1;				// 打开第 u 个二极管
	dfs(u + 1);
	
	st[u] = 0;				// 关闭第 u 个二极管
	dfs(u + 1);
} 

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;
	
	dfs(1);
	
	cout << ans << endl;
	return 0;
} 

蓝桥杯C/C++组省赛历年题