题解：P12843 [蓝桥杯 2025 国 A] 生日相遇问题

· · 题解

题目传送门

思路

分析

  1. 需判断每个年份是否为闰年。
  2. 使用 Zeller 公式计算给定日期的星期几（不懂的请看百度）。
  3. 特别地，若生日为 2 月 29 日，非闰年按 2 月 28 日计算。

判断闰年

这个都很熟悉，能被 4 整除但不能被 100 整除的年份或能被 400 整除的年份是闰年。

每月的天数

小学就背过，非闰年 2 月 28 天，闰年 2 月 29 天，其他月份天数固定。

根据 Zeller 公式计算星期几

公式为：

h=\left ( q+\left \lfloor \frac{13\times \left ( m+1 \right ) }{5} \right \rfloor +K+\left \lfloor \frac{K}{4} \right \rfloor +\left \lfloor \frac{J}{4} \right \rfloor -2\times J\right )\bmod 7

其中：h 为星期几（0 = 星期六，1 = 星期日，\dots，6 = 星期五）。q 为日期，m 为月份（3 = 三月，4 = 四月，\dots，12 = 十二月；1 月和 2 月视为上一年的 13 月和 14 月）。K 为年份的后两位，J 为年份的前两位。

代码

#include<bits/stdc++.h>
#define lcm(x,y) x/__gcd(x,y)*y
#define lb(x) (x&-x)
#define str to_string
using namespace std;
using ll=long long;
const double EPS=1e-6,PAI=acos(-1.0);
const int MAX=3e4+5,mod=1e9+7,MOD=998244353;
bool isLeap(int y){// 判断是否为闰年
    return(y%4==0&&y%100!=0)||(y%400==0);
}
vector<int>day(int y){// 获取每月天数
    vector<int>d={0,31,28,31,30,31,30,31,31,30,31,30,31};
    if(isLeap(y))d[2]=29;
    return d;
}
int get(int y,int m,int d){// 计算星期几 (0=星期日)
    if(m<3){
        m+=12;
        y--;
    }
    int c=y/100;
    y%=100;
    int w=(c/4-2*c+y+y/4+13*(m+1)/5+d-1)%7;
    return(w+7)%7;
}
int m,d1,d2,n,k;
bool f=false;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>m>>d1>>n>>d2>>k;
    for(int y=2025;y<2025+k;y++){
        vector<int>days=day(y);
        int a1=d1,a2=d2;// 实际日期
        // 处理2月29日在非闰年的情况
        if(m==2&&d1==29&&!isLeap(y))a1=28;
        if(n==2&&d2==29&&!isLeap(y))a2=28;
        int w1=get(y,m,a1),w2=get(y,n,a2);
        if(w1==w2){
            cout<<y<<'\n';
            f=true;
        }
    }
    if(!f)cout<<"No Answer\n";
    return 0;
}

时间复杂度

应该是 O\left ( k \right ) ，因为只需要遍历 k 个年份。

AC 记录