【蓝桥备赛冲刺】2020年第十一届省赛B组题解C/C++ 陆续更新状态ing
目录
A题:门牌制作
B题:既约分数
C题:蛇形填数
D题:跑步锻炼
E题:七段码
A题:门牌制作
问题描述
小蓝要为一条街的住户制作门牌号。这条街一共有2020 位住户，门牌号从1 到2020 编号。小蓝制作门牌的方法是先制作0 到9 这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌1017 需要依次粘贴字符1、0、1、7，即需要1 个字符0，2 个字符1，1 个字符7。请问要制作所有的1 到2020 号门牌，总共需要多少个字符2？思路分析
从1遍历到2020，对每个数进行取位，判断为2则计数+1。
题目代码
#include using namespace std;int main() { int cnt = 0; for (int i = 1; i <= 2020; i++) { int I = i; while (I) { int n = I % 10; I /= 10; if (n == 2) cnt++; } } cout << cnt; return 0;}题目答案
624B题:既约分数
问题描述
如果一个分数的分子和分母的最大公约数是1，这个分数称为既约分数。例如3/4，5/2，1/8，7/1都是既约分数。请问，有多少个既约分数，分子和分母都是1 到2020 之间的整数（包括1和2020）？思路分析
双层遍历代表分子与分母，只需要判断i与j的最大公约数是否为1即可。
题目代码
#include using namespace std;int gcd(int a, int b) { // 欧几里得算法 return b ? gcd(b, a % b) : a;}int main() { int cnt = 0; for (int i = 1; i <= 2020; i++) for (int j = 1; j <= 2020; j++) { if (gcd(i, j) == 1) cnt++; } cout << cnt; return 0;}题目答案
2481215C题:蛇形填数
问题描述
如下图所示，小明用从1 开始的正整数“蛇形”填充无限大的矩阵。1 2 6 7 15 ...3 5 8 14 ... 4 9 13 ... 10 12 ... 11 ... ...容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20 行第20 列的数是多少？思路分析
矩阵的填充方向有两种：左下与右上，我们只需要按这两种方向填充即可。
题目代码
#include using namespace std;int num[40][40];int main() { int sum = 1; for (int k = 0; k < 40; k++) { if ((k % 2) == 1) // 向左下填数 for (int i = 0, j = k - i; i <= k; i++, j--) { num[i][j] = sum; sum++; } else { // 向右上填数 for (int j = 0, i = k - j; j <= k; j++, i--) { num[i][j] = sum; sum++; } } } cout << num[19][19]; return 0;}题目答案
761D题:跑步锻炼
问题描述
小蓝每天都锻炼身体。正常情况下，小蓝每天跑1 千米。如果某天是周一或者月初（1 日），为了激励自己，小蓝要跑2 千米。如果同时是周一或月初，小蓝也是跑2 千米。小蓝跑步已经坚持了很长时间，从2000 年1 月1 日周六（含）到2020 年10 月1 日周四（含）。请问这段时间小蓝总共跑步多少千米？思路分析
处理好星期、月份与年份的增加即可。
题目代码
#include int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main() { int y = 2000, m = 1, d = 1, w = 6, ans = 0; while (true) { //每循环一次代表过去一天 ans += (d == 1 || w == 1) + 1; // 每天跑1km，特殊情况多跑1km if (y == 2020 && m == 10 && d == 1) { // 到达指定日期 break; } w = (w + 1) % 7; d++; if ((y % 4 == 0) && m == 2) { // 闰年判断 if (d > month[m] + 1) { d = 1; m += 1; } } else if (d > month[m]) { d = 1; m += 1; } if (m == 13) { // 表示经过一年 y += 1; m = 1; } } printf("%d", ans); return 0;}题目答案
8879E题:七段码
问题描述
小蓝要用七段码数码管来表示一种特殊的文字。上图给出了七段码数码管的一个图示，数码管中一共有7 段可以发光的二极管，分别标记为a, b, c, d, e, f, g。小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。例如：b 发光，其他二极管不发光可以用来表达一种字符。例如：c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。请问，小蓝可以用七段码数码管表达多少种不同的字符？思路分析
每个二极管只有亮和灭两种状态，dfs列举所有状态，再对状态判断是否没有孤立的亮的二极管，如果没有则为一种可行方案。这里采用的判断方法为：如果两个亮的二极管连通，则将他们全部加入到一个集合，最后进行去重，如果集合元素的个数与亮的二极管个数一致，则说明该方案可行。这样的算法还存在一个漏洞，就是如果存在多个连通块则会出现误判，例如{abde, afcd, bcef}，所以为不完全判断，这也是作者在输出时-3的原因。
题目代码(dfs + 不完全判断)
#include #include #include using namespace std;bool SEV[8][8]; // 邻接矩阵bool sev[8]; // 存储七段码亮灭情况int sum;void dfs(int num, bool a) { if (num > 0) sev[num] = a; if (num == 7) { int k = 0; // 记录点亮灯的个数 int arr[10] = {0}; vector vec; // 存储连通点 for (int i = 1; i = 2) { for (int i = arr[p]; i != arr[k - 1]; p++) { q = p + 1; i = arr[p]; for (int j = arr[q]; j; q++) { j = arr[q]; if (SEV[i][j]) { //点 i j 是否连通 /* 加入集合 */ vec.push_back(i); vec.push_back(j); } } } } sort(vec.begin(), vec.end()); // 排序 vec.erase(unique(vec.begin(), vec.end()), vec.end()); // 去重 if ((vec.size() == k || k == 1) && k != 0) { sum++; } return; } dfs(num + 1, 0); // 灭 dfs(num + 1, 1); // 亮}int main() { /* 初始化连通域 */ SEV[1][2] = SEV[1][6] = 1; SEV[2][3] = SEV[2][7] = 1; SEV[3][4] = SEV[3][7] = 1; SEV[4][5] = 1; SEV[5][6] = SEV[5][7] = 1; SEV[6][7] = 1; dfs(0, 0); cout << sum - 3; // -3 是存在多个连通块时的特殊情况 return 0;}题目代码（dfs + 并查集）占位更新
题目答案
80
