题解：P12843 [蓝桥杯 2025 国 A] 生日相遇问题
Sunrise_up
·
·
题解
目前最优解。
为什么这题是黄题啊，妥妥大水题。
思路
发现 k 的值域很小，考虑直接模拟。
这里要注意了：
如果某人的生日是 2 月 29 日，那么在非闰年中，他/她的生日将被视为 2 月 28 日进行计算。
那么我们直接使用基姆拉尔森计算公式进行计算就可以了。
基姆拉尔森计算公式：
W= (d+2m+\frac{3(m+1)}{5}+y+\frac{y}{4}-\frac{y}{100}+\frac{y}{400}) \bmod 7
其中，当 W=0 时代表星期日，当 W=1 时代表星期一，当 W=2 时代表星期二，以此类推。若是一月份，则 m=13，若是二月份，则 m=14。
基姆拉尔森计算公式证明
令 y 代表年份，m 代表月份，d 代表日期，W 代表星期。
对于第一个月我们可以得出公式 1：
W = (d-1) \bmod 7
在不考虑闰年的情况下，一年 365 天，365 \bmod 7=1，就是说一年的第一天和最后一天是相同的。
这就等价于，下一年的第一天星期几是会比这一年的最后一天多 1 的。
所以我们可以完善公式 1，得出公式 2：
W = (d-1 + y) \bmod 7
接下来考虑闰年。因为闰年会多出来一天，所以相当于，计算当前年份前面有多少个闰年，将日期数 w 额外多 1。
我们知道，计算闰年的公式为:
\frac{y}{4}-\frac{y}{100}+\frac{y}{400}
当计算结果为 1 时，结合之前的公式 1,2，得出公式 3：
W = (d-1+y +\frac{y-1}{4}-\frac{y-1}{100}+\frac{y-1}{400}) \bmod 7
对于其它月份，假设每个月都是 28 天
因为 28\bmod 7=0，也就是说每个月的 W 是相同的；
按正常月份计算的话，大月是 31 天，比 28 多 3 天，也就是说，2月的 w 值，是应该比 1 月按 28 计算的往后推迟 3 天。以此类推。
因为 12 月已是最后一个月，所以不用考虑 12 月的误差天数，同理，1 月份的误差天数是 0，因为前面没有月份影响它。
我们可以推出这样一个误差表：
| 月份 |
误差 |
累积 |
\bmod\ 7 |
| 1 |
3 |
0 |
0 |
| 2 |
0 |
3 |
3 |
| 3 |
3 |
3 |
3 |
| 4 |
2 |
6 |
6 |
| 5 |
3 |
8 |
1 |
| 6 |
2 |
11 |
4 |
| 7 |
3 |
13 |
6 |
| 8 |
3 |
16 |
2 |
| 9 |
2 |
19 |
5 |
| 10 |
3 |
21 |
0 |
| 11 |
2 |
24 |
3 |
| 12 |
- |
26 |
5 |
如果用一个集合记录就是 e=\{0,3,3,6,1,4,6,2,5,0,3,5\}。
所以我们完善公式：
W = (d-1+y +e_{m-1}+\frac{y-1}{4}-\frac{y-1}{100}+\frac{y-1}{400}) \bmod 7
如果是闰年的话，2 月之后的都会顺移一天，即：
W = (d-1+y +e_{m-1}+\frac{y-1}{4}-\frac{y-1}{100}+\frac{y-1}{400}+1) \bmod 7
以上为基本推导过程。
观察 e 的规律我们对公式继续进行了优化（但是太难了，这里不做推导，可自己尝试）：
W= (d+2m+\frac{3(m+1)}{5}+y+\frac{y}{4}-\frac{y}{100}+\frac{y}{400}) \bmod 7
代码
注意没有符合的年份要输出 No Answer。
#include<bits/stdc++.h>
using namespace std;
int m,d1,n,d2,k;
bool f=0;
int day(int y,int m,int d){
if(m==2&&d==29&&!((y%4==0&&y%100!=0)||(y%400==0)))d=28;
if(m<3)m+=12,y--;
return (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400)%7;
}
int main(){
cin>>m>>d1>>n>>d2>>k;
for(int y=2025;y<2025+k;y++){
if(day(y,m,d1)==day(y,n,d2)){
cout<<y<<endl;
f=1;
}
}
if(!f)cout<<"No Answer";
return 0;
}
都看到这里了，还不点个赞？