题解：P7075 [CSP-S2020] 儒略日

· · 题解

十分炸裂的一道模拟题。

思路

这显然不能不能一天一天的加，肯定超时。那要怎么做呢？我们应该先分一下时间段。我的分段是先把公元前的归为一段时间，即 BC 4713.1.1-BC 1.12.31。然后在将从公元 1 年到 1581 年归为一段，即 1.1.1-1581.12.31。1582 年要特殊处理，所以 1582.1.1-1582.12.31 归为一段。最后 1582 年以后归为一段，即 1583.1.2-1145141919810.12.31 为一段。

然后最难的是如何确定到达每一段时间的天数。首先从 BC 4713.1.1-1.1.1，所需的天数是 1721424 天，大家可以自行计算。然后，从BC 4713.1.1-1582.1.1，所需的天数是 2298884 天。最后，从BC 4713.1.1-1583.1.1，所需的天数是 2299239 天。知道这些过后，这道题就很简单了，无非就是细节问题。

坑点

第一（闰年），在使用格里高利历之前，闰年的判断条件是 n \bmod 4=0（注意：在公园前是 (n-1)\bmod4=0）；在格里高利历之后的判断条件是 (n \bmod 4 = 0 \land n\bmod100=k,(k \in N_+,k<n))\lor(n \bmod 400 = 0)。

第二（关于 1582 年），1582年从 10 月 5 日到 10 月 14 日是不存在的。

代码

主函数

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int BC=1721424,Julia=2298884,Gregorian=2299239; //1.1.1 | 1582.1.1 | 1583.1.1
int q,mon[2][13]={{0,31,29,31,30,31,30,31,31,30,31,30,31},{0,31,28,31,30,31,30,31,31,30,31,30,31}};
LL r;
int main(){
    scanf("%d",&q);
    while(q--){
        scanf("%lld",&r);
        if(r<BC) BCday(r);
        else if(r==BC) printf("1 1 1\n");
        else if(r<Julia) Juliaday(r-BC);
        else if(r==Julia) printf("1 1 1582\n");
        else if(r>Julia&&r<Gregorian) Julia_Gregorian(r);
        else if(r==Gregorian) printf("1 1 1583\n");
        else Gregorianday(r-Gregorian);
    }
    return 0;
}
BC 4713.1.1-BC 1.12.31 
void BCday(LL r){ //BC 4713.1.1-BC 1.12.31
    int day=1,month=1,year=4713;
    while(r-((year-1)%4==0?366:365)>=0){
        r-=((year-1)%4==0?366:365);
        year--;
    }
    while(r-mon[min(1,(year-1)%4)][month]>=0){
        r-=mon[min(1,(year-1)%4)][month];
        month++;
    }
    day+=r;
    printf("%d %d %d BC\n",day,month,year);
}
1.1.1-1581.12.31 
void Juliaday(LL r){ //1.1.1-1581.12.31
    int day=1,month=1,year=1;
    while(r-(year%4==0?366:365)>=0){
        r-=(year%4==0?366:365);
        year++;
    }
    while(r-mon[min(1,year%4)][month]>=0){
        r-=mon[min(1,year%4)][month];
        month++;
    }
    day+=r;
    printf("%d %d %d\n",day,month,year);
}
1582.1.1-1582.12.31 
void Julia_Gregorian(LL r){ //1582.1.1-1582.12.31
    int October=2299157,December=2299178;
    int day=1,month=1;
    if(r==October) printf("1 10 1582\n");
    else if(r==December) printf("1 11 1582\n");
    else if(r<October||r>December){
        if(r>December) month=11,r-=December;
        else r-=Julia;
        while(r-mon[1][month]>=0){
            r-=mon[1][month];
            month++;
        }
        day+=r;
        printf("%d %d 1582\n",day,month);
    }else{
        month=10;
        r-=October;
        if(r<=3) day+=r;
        else day=11+r;
        printf("%d %d 1582\n",day,month); 
    }
}
1583.1.2-1145141919810.12.31 
int check(int n){
    if(n%400==0||(n%4==0&&n%100!=0)) return 366;
    return 365;
}
void Gregorianday(LL r){ //1583.1.2-1145141919810.12.31
    int day=1,month=1,year=1583,rp=1;
    while(r-check(year)>=0){
        r-=check(year);
        year++;
    }
    if(check(year)==366) rp=0;
    while(r-mon[rp][month]>=0){
        r-=mon[rp][month];
        month++;
    }
    day+=r;
    printf("%d %d %d\n",day,month,year);
}

但是将上述代码一交才 70pts。这是为什么呢？是因为在加年数的时候是一次一次加的，这在 1583 年及以后计算是非常慢的，所以我们可以计算在 1583 年及以后，以 400 年为一周期，即 146097 天，减下去，就可以过了。当然，1581 年及以前，我们也可以以 4 年为一周前，即 1461 天，减下去，也可以加快。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int BC=1721424,Julia=2298884,Gregorian=2299239; //1.1.1 | 1582.1.1 | 1583.1.1 
const int mod1=1461,mod2=146097; //1582年以前4年一周期的天数，1583年后400年一周期的天数 
int q,mon[2][13]={{0,31,29,31,30,31,30,31,31,30,31,30,31},{0,31,28,31,30,31,30,31,31,30,31,30,31}};
LL r;
int check(int n){
    if(n%400==0||(n%4==0&&n%100!=0)) return 366;
    return 365;
}
void BCday(LL r){ //BC 4713.1.1-BC 1.12.31
    int day=1,month=1,year=4713;
    int t=r/mod1;
    year-=t*4;
    r-=t*mod1;
    while(r-((year-1)%4==0?366:365)>=0){
        r-=((year-1)%4==0?366:365);
        year--;
    }
    while(r-mon[min(1,(year-1)%4)][month]>=0){
        r-=mon[min(1,(year-1)%4)][month];
        month++;
    }
    day+=r;
    printf("%d %d %d BC\n",day,month,year);
}
void Juliaday(LL r){ //1.1.1-1581.12.31
    int day=1,month=1,year=1;
    int t=r/mod1;
    year+=t*4;
    r-=t*mod1;
    while(r-(year%4==0?366:365)>=0){
        r-=(year%4==0?366:365);
        year++;
    }
    while(r-mon[min(1,year%4)][month]>=0){
        r-=mon[min(1,year%4)][month];
        month++;
    }
    day+=r;
    printf("%d %d %d\n",day,month,year);
}
void Julia_Gregorian(LL r){ //1582.1.1-1582.12.31
    int October=2299157,December=2299178;
    int day=1,month=1;
    if(r==October) printf("1 10 1582\n");
    else if(r==December) printf("1 11 1582\n");
    else if(r<October||r>December){
        if(r>December) month=11,r-=December;
        else r-=Julia;
        while(r-mon[1][month]>=0){
            r-=mon[1][month];
            month++;
        }
        day+=r;
        printf("%d %d 1582\n",day,month);
    }else{
        month=10;
        r-=October;
        if(r<=3) day+=r;
        else day=11+r;
        printf("%d %d 1582\n",day,month); 
    }
}
void Gregorianday(LL r){ //1583.1.1-1145141919810.12.31
    int day=1,month=1,year=1583,rp=1;
    int t=r/mod2;
    year+=t*400;
    r-=(long long)t*mod2;
    while(r-check(year)>=0){
        r-=check(year);
        year++;
    }
    if(check(year)==366) rp=0;
    while(r-mon[rp][month]>=0){
        r-=mon[rp][month];
        month++;
    }
    day+=r;
    printf("%d %d %d\n",day,month,year);
}
int main(){
    scanf("%d",&q);
    while(q--){
        scanf("%lld",&r);
        if(r<BC) BCday(r);
        else if(r==BC) printf("1 1 1\n");
        else if(r<Julia) Juliaday(r-BC);
        else if(r==Julia) printf("1 1 1582\n");
        else if(r>Julia&&r<Gregorian) Julia_Gregorian(r);
        else if(r==Gregorian) printf("1 1 1583\n");
        else Gregorianday(r-Gregorian);
    }
    return 0;
}