本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：P1202 [USACO1.1] 黑色星期五Friday the Thirteenth – 洛谷
【题目描述】
13 号又是一个星期五，那么 13号在星期五比在其他日子少吗？
为了回答这个问题，写一个程序，要求计算每个月的十三号落在周一到周日的次数。给出 n 年的一个周期，要求计算 1900 年 1 月 1 日至 1900+n−1 年 12 月 31 日中十三号落在周一到周日的次数。
这里有一些你要知道的：
【输入】
一个正整数 n。
【输出】
依次输出周六、日、一、二、三、四、五在 13 日出现的次数。
【输入样例】
20
【输出样例】
36 33 34 33 35 35 34
【核心思想】
问题分析：给定
n
n
n 年周期（1900 年至
1900
+
n
−
1
1900+n-1
1900+n−1 年），需要统计每个月 13 号落在周六、日、一、二、三、四、五的次数。关键在于确定每个月 13 号是星期几，而星期几由该月 13 号距离某个已知星期几的基准日的天数决定。
算法选择：
- 日期递推：以 1900 年 1 月 1 日为起点，逐月累加天数，利用模 7 运算确定星期几
- 闰年判断：根据规则判断每年是否为闰年，选择对应月份天数
- 偏移量计算：每个月 13 号的星期 =
(
该月1号距离基准日的天数
+
12
)
m
o
d
7
(\\text{该月1号距离基准日的天数} + 12) \\bmod 7
(该月1号距离基准日的天数+12)mod7，代码中用 (day + 13) % 7（day 为当月 1 号距离 1900 年 1 月 1 日的天数，加 13 等价于加 12 偏移到 13 号）
关键步骤：
- 初始化：day = 0 表示 1900 年 1 月 1 日距离自身的偏移为 0 天
- 闰年判断函数 f(n)：
- 若
n
m
o
d
4
=
0
n \\bmod 4 = 0
nmod4=0 且n
m
o
d
100
≠
0
n \\bmod 100 \\neq 0
nmod100=0，或n
m
o
d
400
=
0
n \\bmod 400 = 0
nmod400=0，则为闰年
- 若
- 逐月遍历（外层年份
i
i
i，内层月份j
j
j）：- 计算当月 13 号的星期索引：c[(day + 13) % 7]++
- 更新 day：加上当月总天数（闰年用
m
2
[
j
]
m2[j]
m2[j]，平年用m
1
[
j
]
m1[j]
m1[j]），使 day 变为下月 1 号的偏移量
- 输出：按周六(
c
[
6
]
c[6]
c[6])、日(c
[
0
]
c[0]
c[0])、一(c
[
1
]
c[1]
c[1])…五(c
[
5
]
c[5]
c[5]) 的顺序输出
时间/空间复杂度：
- 时间复杂度：
O
(
12
n
)
O(12n)
O(12n)，遍历n
n
n 年每年 12 个月，闰年判断O
(
1
)
O(1)
O(1) - 空间复杂度：
O
(
1
)
O(1)
O(1)，仅需常数级数组存储月份天数和计数
日期递推的核心思想：
- 基准日锚定：以已知星期几的日期（1900 年 1 月 1 日，星期一）为基准，所有日期通过天数偏移量确定星期
- 模 7 周期性：星期每 7 天循环一次，因此
(
偏移天数
)
m
o
d
7
(\\text{偏移天数}) \\bmod 7
(偏移天数)mod7 即可得到星期索引 - 逐月累加而非逐日：不需要遍历每一天，只需记录每月 1 号的偏移量，加 12 即得 13 号偏移量，再加当月天数即得下月 1 号偏移量
- 闰年规则精确建模：世纪年需被 400 整除才为闰年，单独处理 2 月天数
- 适用于固定周期内日期星期统计、日历生成等问题
【解题思路】
【算法标签】
#普及- #数学
【代码详解】
#include <bits/stdc++.h>
using namespace std;
bool f(int n) // 定义闰年判断函数
{
if (n%4==0 && n%100!=0 || n%400==0) { // 模板（背下来！！！）
return true;
}
return false;
}
int m1[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // 定义平年和闰年的每个月日子数
int m2[13] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int c[10] = {0}; // 定义c数组，统计周一-周日的计数
int n, day=0;
int main()
{
cin >> n; // 输入n
for (int i=1900; i<=1900+n–1; i++) { //从1900年遍历至1900+n-1年
for (int j=1; j<=12; j++) { // 依次遍历每个月
if (f(i)) { // 如果为闰年
c[(day+13)%7]++; // 先计算余数，并自增
day = day + m2[j]; // 再增加天数，2月要加31天，3月要加29年。到了下一年的1月，则是加上前一年的12月31天
} else { //平年的计算过程，同上
c[(day+13)%7]++;
day = day + m1[j];
}
}
}
cout << c[6] << " " << c[0] << " " << c[1] << " " << c[2] << " " << c[3] << " " << c[4] << " " << c[5] << endl; // 因为没有遍历的规律，所以按要求依次输出周六、日、一、二、三、四、五的计数
return 0;
}
【运行结果】
20
36 33 34 33 35 35 34
