【补档】题解：P7075 [CSP-S2020] 儒略日

vectorwyx · 2024-12-25 12:57:09 · 题解

先说一下本题的几个坑点：

闰年的不同判断方式：公元前年份的绝对值模 4 余 1 时为闰年，公元后到 1582 年年份是 4 的倍数为闰年，1582 年之后年份是 4 的倍数但不是 100 的倍数，或年份为 400 的倍数时为闰年。
被删除的 10 天。千万不要忘记处理它。很多人在洛谷上测的40分（包括我）就是因为这里或多或少的出了疏漏。
数据范围。由于年份最大是 10^{9}，我们可以推断出给定的 r 最大为 365\times10^{9} 左右。因此第一点就是要开 long long，其次就是要注意时间复杂度。直接枚举年份或日期肯定过不了。

再说一下我的思路：

先确定年份，然后确定月份，最后由年份和月份推出具体的日子。

确定年份需要写一个count_year函数，用来计算从公元前 4713 年 1 月 1 日到某年 12 月 31 日一共有多少天。注意这里是有多少天而非过了多少天，唯一的区别就是公元前 4713 年 1 月 1 日到底算 1 还是算 0。当然题目中给定的 r 是经过了多少天，因此实际操作的时候还需要把给定的 r 加上 1 再处理，不过没太大差别（。

count_year函数的难点在于计算闰年的数量。如果是标准的四年一闰，那么闰年数量显然为 \frac{k}{4}（k 为过了多少年）。而公元前是从公元前 4713 年开始，这是个闰年，把它单独摘出来后就成了标准的四年一闰。公元后元年到 1582 年本来就是标准的四年一闰，直接处理即可。1582 年以后就比较麻烦，为了简便运算我把 1582 年以后又分成了四段：1582 年，1583 年，1584 年到 1600 年，1601 年及以后。写出来大概是这样：

ll count_year(int year){//计算截止到year年12月31日有多少天 
    if(year<0){
        int cnt=year+4713+1;
        return 1ll*cnt*365+ceil(cnt/4.0);
    }
    else if(year<1582){
        return count_year(-1)+year*365+year/4;
    }
    //注意，1582这一年少了10天 
    else if(year==1582){
        return count_year(1581)+355; 
    }
    else if(year==1583){
        return count_year(1581)+355+365;
    }
    else if(year<=1600){
        int cnt=year-1583;
        return count_year(1583)+cnt*365+(cnt-1)/4+1;
    }
    else{
        int cnt=year-1600;
        return count_year(1600)+1ll*cnt*365+cnt/4-cnt/100+cnt/400;
    }
}

有了count_year函数后，由于起始日期到答案日期的天数 r 一定小于等于起始日期到答案的年份的最后一天的天数，我们可以使用二分求出答案的年份，得到年份之后我们只需要枚举一下月份，思路和求年份是共通的，只不过由于月份只有十二种取值因此没必要用二分。这里也需要写一个count_month函数，用来计算从某一年的 1 月 1 日到某个月的最后一天有多少天：

int mo[30]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int sum[30];
int count_month(int year,int month){//截止到year年month月的最后一天有多少天
    return sum[month]+(check(year)&&(month>=2))-(year==1582&&month>=10)*10;
}

年份和月份都得到了，那么具体的日期只需要把总天数减去年份和月份所占的天数。千万不要忘记在求出答案后再处理一下那消失的十天！

完整代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;++i)
#define go(i,x,y) for(int i=x;i>=y;--i)
using namespace std;

inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

ll count_year(int year){//计算截止到year年12月31日有多少天 
    if(year<0){
        int cnt=year+4713+1;
        return 1ll*cnt*365+ceil(cnt/4.0);
    }
    else if(year<1582){
        return count_year(-1)+year*365+year/4;
    }
    //注意，1582这一年少了10天 
    else if(year==1582){
        return count_year(1581)+355; 
    }
    else if(year==1583){
        return count_year(1581)+355+365;
    }
    else if(year<=1600){
        int cnt=year-1583;
        return count_year(1583)+cnt*365+(cnt-1)/4+1;
    }
    else{
        int cnt=year-1600;
        return count_year(1600)+1ll*cnt*365+cnt/4-cnt/100+cnt/400;
    }
}

bool check(int x){
    if(x<0) return ((-x)%4==1);
    if(x<=1582) return x%4==0;
    return ((x%4==0&&x%100!=0)||(x%400==0));
}

int mo[30]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int sum[30];
int count_month(int year,int month){//截止到year年month月的最后一天有多少天
    return sum[month]+(check(year)&&(month>=2))-(year==1582&&month>=10)*10;
   //sum是mo数组的前缀和
}

int main(){
    fo(i,1,12) sum[i]=sum[i-1]+mo[i];
    int T=read();
    while(T--){
        ll ri=read()+1;
        int L,R,mid,Year,Month,Day; 
        L=-4713,R=1e9+5;
        while(L<=R){//二分年份 
            mid=(L+R)>>1;
            if(count_year(mid)>=ri) Year=mid,R=mid-1;
            else L=mid+1;
        }
        ri-=count_year(Year-1);
        fo(i,1,12){
            int cm=count_month(Year,i);
            if(cm>=ri){
                Month=i;
                Day=ri-count_month(Year,i-1);
                break;
            }
        }
        if(Year==1582&&Month==10&&Day>4) Day+=10;
        if(Year<0) printf("%d %d %d BC\n",Day,Month,-Year);
        else printf("%d %d %d\n",Day,Month,Year);
    }
    return 0;
}