6 跑步锻炼
题目
小蓝每天都锻炼身体。
正常情况下，小蓝每天跑 1 千米。如果某天是周一或者月初（1 日），为了激励自己，小蓝要跑 2 千米。如果同时是周一或月初，小蓝也是跑 2 千米。
小蓝跑步已经坚持了很长时间，从 2000 年 1 月 1 日周六（含）到 2020 年 10 月 1 日周四（含）。请问这段时间小蓝总共跑步多少千米？
答题总结
⏰解题耗时：30min 🎯难度：💡
- 大小月记不清。大月：
1、3、5、7、8、10、12
- 闰年的判断方法：
year%4==0 && year%100!=0) || year%400==0
- 注意闰年的2月是29天，不是28天！（因为这个调了好久 bug 💥💢）
解析
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
|
#include <iostream>
using namespace std;
// 判断是否是闰年，是则返回 true，否则返回 false
bool isRun(int year){
if((year%4==0 && year%100!=0) || year%400==0)
return true;
return false;
}
int main(){
// 每个月对应的天数
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}; // 非闰年
int cnt=6; // 用于判断是否是周一
int sum=0; // 计算总数
for(int y=2000;y<=2020;y++){ // 遍历每一年
for(int m=1;m<=12;m++){ // 遍历每一月
if(isRun(y)){ // 闰年
for(int d=1;d<=mon1[m];d++){
if(d==1 || cnt%7==1) // 如果是月初或者周一要额外加 1
sum++;
sum++;
cnt=(cnt+1)%7; // 更新 cnt 的值
// 遍历到最后一天 2020.10.01 结束
if(y==2020 && m==10 && d==1){
printf("%d\n",sum);
return 0;
}
}
}
else{ // 不是闰年
for(int d=1;d<=mon2[m];d++){
if(d==1 || cnt%7==1) // 如果是月初或者周一要额外加 1
sum++;
sum++;
cnt=(cnt+1)%7; // 更新 cnt 的值
}
}
}
}
return 0;
}
|
7 蛇形填数
题目
如下图所示，小明用从 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 列的数是多少？
答题总结
⏰解题耗时：15min 🎯难度：💡
- 小学找规律题，可手算🎉🎉
- 要看清题目所给的下标是从0开始还是从1开始！（因为题中的矩阵行列从0开始算，找了好久bug 💢💥
- 注意题目要求。比如这道题只求(20, 20)的数，就只用找坐标为(a, a)的元素的规律，而不用把所有的都找出
- 找规律要容易出错，要多算几个验证
解析
🟠 把所有坐标的元素表达式都找出来
这种做法比较普适，缺点是可能会浪费宝贵的答题时间，并且规律较多的情况会把自己绕晕，很容易疏忽一两个点导致答案不对。😭😤
我们先把每次填充的同一条斜线上的元素看成一组，很容易发现一些规律：
- 这条斜线上有 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 找规律就很容易出错❗❗❗
8 既约分数
题目
如果一个分数的分子和分母的最大公约数是 11，这个分数称为既约分数。
例如 3/4, 1/8, 7/1，都是既约分数。
请问，有多少个既约分数，分子和分母都是 11 到 2020 之间的整数（包括 11 和 2020）？
答题总结
⏰解题耗时：5min 🎯难度：💡
解析
填空题，没什么好说的，直接暴力解决啦~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#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;
}
|
9 数字三角形
题目
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。
输入描述
输入的第一行包含一个整数 N (1≤ N ≤100)，表示三角形的行数。
下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。
输出描述
输出一个整数，表示答案。
答题总结
⏰解题耗时：没写出来 🎯难度：💡💡
- 【求矩阵路径最值问题】动态规划、开一个数组记录到每个位置的最大/小值
解析
这道题想了很久毫无头绪，是10道题里唯一不会写的，看了评论区一个大佬的题解后醍醐灌顶。核心思想：
🔴 用一个数组 s[i][j] 记录从 a[1][1]到 a[i][j] 的路径上的数字和最大值。关注点在结果位置，是 【上一跳从哪来】 而不是 【下一跳往哪走】 。
🔵 遍历三角形数组，用动态规划更新矩阵 s。base case为： s[1][1]=a[1][1] 。状态转移方程为 s[i][j]=a[i][j]+max(s[i-1][j-1],s[i-1][j]) 。（ s[i][j] 处的最大值要么是从 [i-1][j-1] 过来的，要么是从 [i-1][j] 过来的）
🟢 由于要满足向左、向右的步数差不超过1，最终结果只能是最中间的。考虑n的奇偶性，n为奇数时，输出矩阵s最后一行最中间的，即 s[n][n/2+1] ；n为偶数时，矩阵s最后一行最中间有2个元素，输出值最大的那个，即 max(s[n][n/2],s[n][n/2+1]) 。
⚠ 这个思路真的强推，在很多动态规划的题目中都能应用上，例如今天刚好做的：931. 下降路径最小和
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
|
#include <iostream>
using namespace std;
int main()
{
// 读取数据
// s[i][j]：从 a[1][1] 遍历到 a[i][j] 的最大和
int a[105][105]={0},s[105][105]={0},n;
scanf("%d", &n);
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
scanf("%d",&a[i][j]);
}
}
// 计算最大和
s[1][1]=a[1][1];
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
s[i][j]=a[i][j]+max(s[i-1][j-1],s[i-1][j]);
}
}
// n 是偶数且要满足向左、向右的步数差不超过 1，只能是中间两个
// n 是奇数且要满足向左、向右的步数差不超过 1，只能是最中间的那个
if(n%2==0)
cout<<max(s[n][n/2],s[n][n/2+1]); // 注意 s 是二维矩阵，不能写错成一维的
else
cout<<s[n][n/2+1];
return 0;
}
|
10 回文日期
题目
2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。
给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。
输入描述
输入包含一个八位整数 N，表示日期。
对于所有评测用例，10000101≤ N ≤89991231，保证 N 是一个合法日期的 8 位数表示。
输出描述
输出两行，每行 1 个八位数。第一行表示下一个回文日期，第二行表示下一个 ABABBABA 型的回文日期。
答题情况
⏰解题耗时：60min 🎯难度：💡
解析
虽然官方给这道题贴的标签是 中等 ，但感觉难度一般，暴力穷举就好。不过确实很容易出错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;
}
|
菜菜的秘密花园