试题A：门牌制作
小蓝要为一条街的住户制作门牌号。
这条街一共有 2020 位住户，门牌号从 1 到 2020 编号。
小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，
最后根据需要将字符粘贴到门牌上，
例如门牌 1017 需要依次粘贴字符 1、 0、 1、 7，
即需要 1 个字符 0， 2 个字符 1， 1 个字符 7。
请问要制作所有的 1 到 2020 号门牌，总共需要多少个字符 2？
解题思路：
直接枚举就行啦：
#include using namespace std; int main() { int cnt = 0; for (int i = 0; i <= 2020; i++) { int tmp = i; while (tmp) { if (tmp % 10 == 2) { cnt++; } tmp /= 10; } } cout << cnt << endl; return 0; }
答案：
624
试题B：既约分数
如果一个分数的分子和分母的最大公约数是1，这个分数称为既约分数。
例如：3 / 4 , 5 / 2 , 1 / 8 , 7 / 1 都是既约分数。
请问，有多少个既约分数，分子和分母都是1 到2020 之间的整数（包括1和2020）？
解题思路：
既约分数其实就是约好的分数，
而约好的分数有一个特点就是，分子分母的最大公约数是1。
#include using namespace std; //找最大公约数 int gcd(int a, int b) { while (b) { int c = a % b; a = b; b = c; } if (a == 1) return a; } int main() { int cnt = 0; for (int i = 1; i <= 2020; i++) { for (int j = 1; j <= 2020; j++) { //如果最大公约数是1，证明是既约分数 if (gcd(i, j) == 1) { cnt++; } } } cout << cnt << endl; return 0; }
答案：
2481215
试题C：蛇形填数
如下图所示，小明用从1 开始的正整数“蛇形”填充无限大的矩阵。
容易看出矩阵第二行第二列中的数是5。
请你计算矩阵中第 20 行第 20 列的数是多少？
解题思路：
我的方法是找规律，很容易看出：
1，5，13 ......
下一个数比上一个数大(i - 1) * 4
#include using namespace std; int main() { int res = 1; for (int i = 2; i <= 20; i++) { res += (i - 1) * 4; } cout << res << endl; return 0; }
答案：
761
试题D：跑步训练
小蓝每天都锻炼身体。
正常情况下，小蓝每天跑 1 千米。
如果某天是周一或者月初（1 日），为了激励自己，小蓝要跑 2 千米。
如果同时是周一或月初，小蓝也是跑 2 千米。
小蓝跑步已经坚持了很长时间，
从 2000 年 1 月 1 日周六（含）到 2020 年10 月 1 日周四（含）。
请问这段时间小蓝总共跑步多少千米？
解题思路：
这是一道经典的日期问题，
最好就是记住日期类问题的模板，
这道题我们先计算到2019年，最后再特殊处理2020年那10个月：
#include using namespace std; //打表 int day[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; bool is_leap(int year) { return (year % 4 == 0 && year % 100 || year % 400 == 0); } int get_day(int year, int month) { if (is_leap(year) && month == 2) return day[month] + 1; else return day[month]; } int main() { int cnt = 0, res = 0; //2000~2019 for (int i = 2000; i <= 2019; i++) { for (int j = 1; j <= 12; j++) { for (int k = 1; k <= get_day(i, j); k++) { //我们用0~6表示周一到周日，因为2000.1.1是周六，所以+5 int weekday = (cnt + 5) % 7; if (k == 1 || weekday == 0) res += 2; else res++; cnt++; } } } //2020.1.1~2020.9.30 for (int i = 1; i <= 9; i++) { for (int j = 1; j <= get_day(2020, i); j++) { int weekday = (cnt + 5) % 7; if (j == 1 || weekday == 0) res += 2; else res++; cnt++; } } //2020.10.1 res += 2; cout << res << endl; return 0; }
细节一定要注意好，否则很容易出错。
答案：
8879
试题E：七段码
小蓝要用七段码数码管来表示一种特殊的文字。
七段码上图给出了七段码数码管的一个图示，
数码管中一共有7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。
在设计字符的表达时，要求所有发光的二极管是连成一片的。
例如：b 发光，其他二极管不发光可以用来表达一种字符。
例如：c 发光，其他二极管不发光可以用来表达一种字符。
这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。
例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
解题思路：
这道题用dfs + 并查集，
尴尬的是我不会并查集，所以我只能将答案搬运一下，希望对你们能有所帮助：
代码搬运：代码参考
#include using namespace std; const int N = 10; int ans;//统计结果 int p[N];//存放并查集中，根信息的数组 bool st[N];//记录DFS搜索的状态 int e[N][N];//记录七段码灯管彼此连通的的信息,e[i[[j]表示i和j的连通与否 //补全并查集的核心函数 int find(int x) { if(p[x] != x) p[x] = find(p[x]); return p[x]; } //补全DFS函数 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++) { //i是点亮了。j是点亮了。i和j之间是直接联系的 if(st[i] && st[j] && e[i][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;//打开当前灯管的情况 dfs(u+1); st[u] = 0; dfs(u+1);//关闭当前灯管的情况 } int main() { //初始化1到7号，各个灯管，直接连通的情况 e[1][2] = e[1][6] = 1;//意思就是，代表a号灯管的的1，和代表b的2号灯管连通，和代表f的6号灯管连通 e[2][1] = e[2][3] = e[2][7] = 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; //从1号灯管开始DFS dfs(1); cout << ans << endl; return 0; }
答案：
80
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
