蓝桥杯每日一题2023.10.8

题目描述

七段码 - 蓝桥云课 (lanqiao.cn)

题目分析 

所有的情况我们可以分析出来一共有2的7次方-1种，因为每一个二极管都有选择和不选择两种情况，有7个二极管，但是还有一种都不选的情况需要排除，故-1

枚举每个方案看是否符合要求，对于每种方案，从任何一个选中的顶点出发进行dfs，如果这个方案找到的顶点是亮的并且有边相连那么这个方案就符合要求

 是否有边相连我们使用邻接矩阵存储，如第一行，与a相连的边有b, f所以g[a][b] = 1, g[a][f] = 1

答案：80

#include<bits/stdc++.h>
using namespace std;
int bright[7];
bool vis[7];
int g[7][7] = 
{{0, 1, 0, 0, 0, 1, 0},{1, 0, 1, 0, 0, 0, 1},{0, 1, 0, 1, 0, 0, 1},{0, 0, 1, 0, 1, 0, 0},{0, 0, 0, 1, 0, 1, 1},{1, 0, 0, 0, 1, 0, 1},{0, 1, 1, 0, 1, 1, 0}
};
void dfs(int x)
{for(int i = 0; i < 7; i ++){if(g[x][i] && bright[i] && !vis[i]){vis[i] = 1;dfs(i);}}
}
int main()
{int ans = 127;//128 - 1for(int i = 1; i <= 127; i ++){memset(vis, 0, sizeof vis);memset(bright, 0, sizeof bright);int x = i;int j = 0;while(x){if(x & 1)bright[j] = 1;x >>= 1;j ++;}int stick = 0;while(!bright[stick])stick ++;vis[stick] = 1;dfs(stick);for(int j = 0; j < 7; j ++){if(bright[j] && !vis[j])//此处应该为亮但是却没有访问过说明不相连 {ans --;break;}}}cout << ans; return 0;
}