题解 P7075 【儒略日（洛谷民间数据）】

· · 题解

0.题外话：

CSP-S T1 放这个真的好吗。。。T2都比这个简单

1. 10 分做法

由于第一个点 r_i\leq 365 ，所以判断几月几日就好。

等等，好像没那么简单？

有的同学发现了一点：一月一日是第 0 天，那么第 365 天不就到后一年去了吗？

其实公元前4713年是一个闰年，因为 4713\equiv 1\ \ \ (\text{mod}\ 4) ，而公元前1年为闰年。

所以只要枚举判断月份的前缀和是否超过了 r_i 即可。

    month[2]++;
    int qwq=0,mth;
    for(int i=1;i<=12;i++){
        qwq+=month[i];
        if(qwq>=k){
            mth=i;
            k-=(qwq-month[i]);
            printf("%lld %lld 4713 BC\n",k,mth);
            break;
        }
    }
    month[2]--;

2. 40 分做法

首先，公元1582年10月4日是第 2299160 天，所以只处理适用儒略历的就可以拿到 40 分了。

那如何处理儒略历呢？

注意到，儒略历 4 年一循环，所以可以让 r_i 对 365\times 4+1 取余，求出大致年份，再一年一年判断在哪一年。

然后再向上面一样判断月、日就好了。

void count_date(int year,int k,int r){
    if(r==1)month[2]++;
    int qwq=0,mth;
    for(int i=1;i<=12;i++){
        qwq+=month[i];
        if(qwq>=k){
            mth=i;
            k-=(qwq-month[i]);
            if(year-4713<0)printf("%lld %lld %lld BC\n",k,mth,4713-year);
            else printf("%lld %lld %lld\n",k,mth,year-4712);
            break;
        }
    }
    if(r==1)month[2]--;
}
        scanf("%lld",&n);
            int k=n%(365*4+1),year=n/(365*4+1)*4,r=1;
            if(k>=366)k-=365,year++,r=0;
            if(k>=366)k-=365,year++;
            if(k>=366)k-=365,year++;
            if(r==1)k++;
            count_date(year,k,r);

3. 100 分做法

没错，就是 100 分做法。

首先，对于格里高利历，有个很没良心的地方：当年份是 400 的倍数，或日期年份是 4 的倍数但不是 100 的倍数时，该年为闰年。

所以，变成了 400 一周期。怎么办？

其实和 40 分做法一样处理就行了。

具体来说，就是把那几个if语句写个循环，道理是一样的。

注意，循环里还是要判断闰年。

还有，由于以公元1600年1月1日为原点写起来会比较舒服（周期起点），所以可以为了减少代码量，特判一下公元1582年和公元1600年之间的那几年。

下面是完整的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int q,n,rsum,month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
void count_date(int year,int k,int r){
    if(r==1)month[2]++;
    int qwq=0,mth;
    for(int i=1;i<=12;i++){
        qwq+=month[i];
        if(qwq>=k){
            mth=i;
            k-=(qwq-month[i]);
            if(year-4713<0)printf("%lld %lld %lld BC\n",k,mth,4713-year);
            else printf("%lld %lld %lld\n",k,mth,year-4712);
            break;
        }
    }
    if(r==1)month[2]--;
}//儒略历时代的count_date
void count_date2(int year,int k,int r){
    if(r==1)month[2]++;
    int qwq=0,mth,f=0;
    for(int i=1;i<=12;i++){
        qwq+=month[i];
        if(qwq>=k){
            mth=i;
            k-=(qwq-month[i]);
            printf("%lld %lld %lld\n",k,mth,year+1600);
            f=1;
            break;
        }
    }
    if(f==0)printf("1 1 %lld\n",year+1601);
    if(r==1)month[2]--;
}//格里高利历时代的count_date
signed main(){
    //freopen("julian.in","r",stdin);
    //freopen("julian.out","w",stdout);
    for(int i=1;i<=400;i++)
        if((i%4==0&&i%100!=0)||i%400==0)rsum++;
    scanf("%lld",&q);
    while(q--){
        scanf("%lld",&n);
        if(n<=2299160){
            int k=n%(365*4+1),year=n/(365*4+1)*4,r=1;
            if(k>=366)k-=365,year++,r=0;
            if(k>=366)k-=365,year++;
            if(k>=366)k-=365,year++;
            if(r==1)k++;
            count_date(year,k,r);
        }//儒略历时代
        else {
            n+=10;//完美跳过不存在的那几天
            if(n<=2305457){
                int k=n%(365*4+1),year=n/(365*4+1)*4,r=1;
                if(k>=366)k-=365,year++,r=0;
                if(k>=366)k-=365,year++;
                if(k>=366)k-=365,year++;
                if(r==1)k++;
                count_date(year,k,r);
            }//特判的那几年
            else{
                n-=2305458;
                int k=n%(365*400+rsum),year=n/(365*400+rsum)*400,r=1;
                if(k>=366)k-=365,year++,r=0;
                for(int i=2;i<=399;i++){
                    if(i%4==0&&i%100!=0){
                        if(k>=367)k-=366,year++,r=1;
                        else break;
                    }
                    else{
                        if(k>=366)k-=365,year++,r=0;
                        else break;
                    }
                }
                if(r==1)k++;
                count_date2(year,k,r);
            }//格里高利历时代
        }
    }
    return 0;
}

时间复杂度：这看起来暴力的做法实际上是 O(q) 的不过常数比较大。