⏰总用时：130/240 🎯总分：25/150
| 题号 |
时间 |
结果 |
满分 |
难度 |
备注 |
| 1 |
20 |
✅ |
5 |
🌕 |
🔸 注意从获得一个数各个位上的数字的做法：先 ‘/’ 再 ‘%’ |
| 2 |
10 |
✅ |
5 |
🌕 |
|
| 3 |
15 |
❌ |
10 |
🌕 |
🔹 要看清题目所给的下标是从0开始还是从1开始！
🔹 注意题目要求。比如这道题只求(20, 20)的数，就只用找坐标为(a, a)的元素的规律，而不用把所有的都找出
🔹 找规律要容易出错，要多算几个验证 |
| 4 |
10 |
❌ |
10 |
🌓 |
🔸 回溯 |
| 5 |
10 |
❌ |
10 |
🌓 |
🔹 用递推解决，观察递推关系式
🔹 注意初始状态的确定 |
| 6 |
5 |
✅ |
15 |
🌕 |
|
| 7 |
60 |
❌ |
20 |
🌕 |
|
| 8 |
|
|
20 |
|
|
| 9 |
|
|
25 |
|
|
| 10 |
|
|
25 |
|
|
1 门牌制作
题目
小蓝要为一条街的住户制作门牌号。
这条街一共有 2020 位住户，门牌号从 1 到 2020 编号。
小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、0、1、7，即需要 1 个字符 0，2 个字符 1，1 个字符 7。
请问要制作所有的 1 到 2020 号门牌，总共需要多少个字符 2？
解析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <iostream>
using namespace std;
int main(){
int s=0;
for(int i=1;i<=2020;i++){
if(i%10==2) s++; // 个位为2
if(i/10%10==2) s++; // 十位为2
if(i/100%10==2) s++; // 百位为2
if(i/1000==2) s++; // 千位为2
}
printf("%d",s);
return 0;
}
|
2 既约分数
题目
如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。
例如 3/4, 1/8, 7/1，都是既约分数。
请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020）？
解析
填空题，没什么好说的，直接暴力解决啦~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <iostream>
using namespace std;
int main(){
int sum=0;
for(int i=1;i<=2020;i++){ // 分子
for(int j=1;j<=2020;j++){ // 分母
int flag=1;
for(int k=2;k<=2020;k++){
if(i%k==0 && j%k==0){
flag=0;break;
}
}
sum+=flag;
}
}
cout<<sum;
return 0;
}
|
3 蛇形填数
题目
如下图所示，小明用从 1 开始的正整数“蛇形”填充无限大的矩阵。
1
2
3
4
5
6
|
1 2 6 7 15 ...
3 5 8 14 ...
4 9 13 ...
10 12 ...
11 ...
...
|
容易看出矩阵第二行第二列中的数是 5。请你计算矩阵中第 20 行第 20 列的数是多少？
解析
小学找规律题，可手算🎉🎉
🟠 把所有坐标的元素表达式都找出来
这种做法比较普适，缺点是可能会浪费宝贵的答题时间，并且规律较多的情况会把自己绕晕，很容易疏忽一两个点导致答案不对。😭😤
我们先把每次填充的同一条斜线上的元素看成一组，很容易发现一些规律：
- 这条斜线上有 n 个元素，对每个元素 (i, j) 都有：i + j = n + 1（i，j 都是从1开始的❗❗❗）
- 当 n 为奇数时，从下往上填充，也就是 j 从 1 开始，比如：(3, 1)，(2, 2)，(1, 3)。偶数则相反。
- 元素值 = 它是第几个被填充的
那么，要求位置为 (20, 20) 的元素值，我们只需要知道他是第几个被填充的。
首先 20+20=40，说明 (20, 20) 所在的斜线上有39个元素，每个元素的坐标和都为40。又由于 39 是个奇数，所以这条斜线填充的顺序为：(39,1)，(38,2)，(37,3)…(20,20)…(1,39)。 (20,20) 是这条斜线上的第 20 个元素。而在这条斜线被开始填充前，已经填充的元素数为：1+2+3+4+5...+38 = 741 。最终可以得到 (20,20) 是第几个被填充的： 741+20=261 。
🟡 只考虑坐标为 (a, a) 的元素
先自己手动补充后面的元素，坐标形式为 (a, a) 的元素值依次为：1, 5, 13, 25, 41……
仔细分析可以发现：1=4×0+1；5=4×1+1；13=4×3+1；25=4×6+1；41=4×10+1。除开表达式的相同点，接下来只用找 1, 3, 6, 10 的规律：1=1；3=1+2；6=1+2+3；10=1+2+3+4。由此我们很容易得到坐标为 (a,a) 的元素值表达式：4×(1+2+3+...a-1)+1 。
带入 a=20 得到最终答案：261。
⚠ 此处要注意的是，一定要多写几个检验❗❗❗只看 1, 5, 13, 25 找规律就很容易出错❗❗❗
4 七段码
题目
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示，数码管中一共有 77 段可以发光的二 极管，分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。
例如：b 发光，其他二极管不发光可以用来表达一种字符。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
解析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <bits/stdc++.h>
using namespace std;
int g[7][7]={ // 存储相邻的边
{1,1,0,0,0,1,0},
{1,1,1,0,0,0,1},
{0,1,1,1,0,0,1},
{0,0,1,1,1,0,0},
{0,0,0,1,1,1,1},
{1,0,0,0,1,1,1},
{0,1,1,0,1,1,1},
};
int backtrace(int v[], int x){
int cnt=1; // 初值为 1: x本身也是一种方式
for(int i=0;i<7;i++){
if(v[i]==0 && g[i][x]==1){
v[i]=1;
cnt+=backtrace(v,i);
v[i]=0; // 每次回溯完恢复
}
}
return cnt;
}
int main(){
int v[7]={0,0,0,0,0,0,0}; // 表示边的点亮状态
cout<< backtrace(v, 0)/2; // 要记得除 2 ，因为每种可能都被算了 2 次！！！
return 0;
}
|
5 平面分割
题目
20 个圆和 20 条直线最多能把平面分成多少个部分？
解析
🟠 用 【递推】 解决，设 a[i][j] 为 i 条直线、j个圆能分割平面的数量。注意 a[0][0]=1 ❗❗❗
🟡 考虑增加直线。给 a[i-1][0] 增加一条直线，会多出 i-1 个交点，也就会多出 i 个平面。因此有： a[i][0]=a[i-1][0]+i 。
🟢 考虑增加圆。给 a[i][j-1] 增加一个圆，这个新增圆和一个直线最多有 2 个交点，和一个圆最多有2个交点，而圆与直线、圆与圆每多 1 个交点，就多 1 个平面。因此有： a[i][j]=a[i-1][j-1]+2*i+2*(j-1) 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[21][21]; // 表示直线数、圆数给定时的可能数
a[0][0]=1; // 注意本身就有一个平面！！！
for(int i=1;i<=20;i++) // 更新所有加直线的情况
a[i][0]=a[i-1][0]+i;
for(int i=1;i<=20;i++){ // 更新所有加圆的情况
for(int j=1;j<=20;j++)
a[i][j]=a[i][j-1]+2*i+2*(j-1);
}
cout<<a[20][20];
return 0;
}
|
6 成绩分析
题目
小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。
请计算这次考试的最高分、最低分和平均分。
输入描述
输入的第一行包含一个整数 n (1≤n≤$10^4$) ，表示考试人数。
接下来 n 行，每行包含一个 0 至 100 的整数，表示一个学生的得分。
输出描述
输出三行。
第一行包含一个整数，表示最高分。
第二行包含一个整数，表示最低分。
第三行包含一个实数，四舍五入保留正好两位小数，表示平均分。
解析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <iostream>
using namespace std;
int main(){
int max=0,min=100,sum=0,n,s;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&s);
if(s>max) max=s;
if(s<min) min=s;
sum+=s;
}
double avg=(int)(sum*100.0/n+0.5);
avg/=100;
printf("%d\n%d\n%.2f",max,min,avg);
return 0;
}
|
7 回文日期
题目
2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。
给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。
输入描述
输入包含一个八位整数 N，表示日期。
对于所有评测用例，10000101≤ N ≤89991231，保证 N 是一个合法日期的 8 位数表示。
输出描述
输出两行，每行 1 个八位数。第一行表示下一个回文日期，第二行表示下一个 ABABBABA 型的回文日期。
解析
虽然官方给这道题贴的标签是 中等 ，但感觉难度一般，暴力穷举就好。不过确实很容易出错QAQ。
🔴 计算第1个回文日期时，即 ABCDDCBA 型，只用根据 ABCD 来枚举，需要确保两点：1️⃣ ABCDDCBA 的值需大于输入的 起始日期date 2️⃣ ABCDDCBA 需要是一个合法日期。注意 D 的值只能是0或1，可以减少枚举量。
🔵 计算第2个回文日期时，即 ABABBABA 型，只用根据 AB 来枚举，条件和上面类似。不过由于B只能取0或1，又只有输出第一个符合的回文日期，A的值要么是a，要么是a+1。（a是输入日期 date 的最高位）
🟢 判断是否是合法日期，只需把日期拆成年、月、日，看月、日的值是否合法，注意需要看年份是否是闰年。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <iostream>
using namespace std;
// 用于判断输入的值是否是一个合格日期
bool isDate(int y,int m,int d){
int mon1[13]={0,31,29,31,30,31,30,31,31,30,31,30,31}; // 闰年
int mon2[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; // 非闰年
if((y%4==0 && y%100!=0) || y%400==0){ // 闰年
if(m>=1 && m<=12 && d>=1 && d<=mon1[m])
return true;
}
else{ // 非闰年
if(m>=1 && m<=12 && d>=1 && d<=mon2[m])
return true;
}
return false;
}
int main()
{
int date,fh=0,ye,mo,da;
cin>>date;
int a=date/10000000;
int b=date/1000000%10;
int c=date/100000%100;
int d=date/10000%1000;
// 寻找第一个回文串日期
int flag=0;
for(int i=a;i<=9;i++){
for(int j=0;j<=3;j++){
for(int k=0;k<=9;k++){
if(i*10000001+j*1000010+k*100100 + 11000 <= date)
continue;
if(i*10000001+j*1000010+k*100100 > date){ // d=0
if(isDate(i*1000+j*100+k*10, k, j*10+i)){
cout << i*10000001+j*1000010+k*100100 <<endl;
flag=1;
break;
}
}
if(isDate(i*1000+j*100+k*10+1, 10+k, j*10+i)){ // d=1
cout << i*10000001+j*1000010+k*100100+11000 <<endl;
flag=1;
break;
}
}
if(flag==1) break;
}
if(flag==1) break;
}
// 寻找第一个 ABABBABA型回文串
if(a*10000000+a*100000+a*100+a>date)
cout<< a*10000000+a*100000+a*100+a <<endl;
else if(a*10000000+a*100000+a*100+a+1011010>date && (a==1 || a==2))
cout<< a*10000000+a*100000+a*100+a+1011010 <<endl;
else cout<< (a+1)*10000000+(a+1)*100000+(a+1)*100+a+1<<endl;
return 0;
}
|
8 子串分值
9 荒岛探测
10 字串排序
菜菜的秘密花园