AFO

题解 P7075 【儒略日】

2020-11-11 19:55:38


写篇题解来纪念一下爆炸的 CSP2020。

我考场切掉这题大概用了半个小时,虽然不算快但也不是很慢,所以写一下考场思路。

这个东西我是分三段算的:公元前、1582 年 10 月 4 日前、1582 年 10 月 15 日后。

每一段内都是先确定年,然后确定月,最后确定日。

为了自己思考方便,我把 $r$ 加了 $1$,变为从公元前 4714 年 12 月 31 日开始。下文的 $r$ 也是加 $1$ 之后的。

首先是第一段。通过一些小学奥数知识可以算出公元前 4714 年 12 月 31 日到公元前 1 年 12 月 31 日的天数是 $1721424$ 天。因为年数很少,所以我们可以直接求出每年的天数然后求前缀和,这样子就可以直接二分出年份了。求出年份后,我们把 $r$ 减掉到前一年 12 月 31 日的天数,再把每个月的天数求出来并求前缀和,然后直接枚举出月份即可。这样子再减掉前一年 12 月 31 日到前一月最后一天的天数后就可以得到日了。(可能写得有点绕,请见谅。)

如果不在第一段内,就把 $r$ 减掉 $1721424$,变成从公元前 1 年 12 月 31 日开始算。

第二段是类似的,通过一些小学奥数知识算出公元前 1 年 12 月 31 日到 1582 年 10 月 4 日的日期是 $577737$ 天后套用第一段的做法即可。

如果也不在第二段内,那就只能在第三段内了。为了方便,我们直接给 $r$ 加上 $10$,强行把不见的 $10$ 天补回来。沿用上面的思路,我们还是二分年份、枚举月份,主要问题变成了求公元前 1 年 12 月 31 日到公元 $x$ 年 12 月 31 日的天数。

这个其实很好算,我们只要用 $365x$ 加上闰年个数即可。闰年个数可以小小地容斥一下,即为 $\lfloor \frac{x}{4}\rfloor-\lfloor\frac{x}{100}\rfloor+\lfloor\frac{x}{400}\rfloor$?但是这实际上少算了一些,因为公元 1582 年 10 月 4 日前是儒略历,所以公元 100 年、200 年、300 年、500 年、600 年、700 年、900 年、1000 年、1100 年、1300 年、1400 年、1500 年这 12 年也是闰年,所以上面那个结果实际上还要加上 $12$。

然后就只剩下码了,感觉也没啥细节,注意一下题目里提醒的东西就好了。

因为 $r$ 是 $10^{12}$ 级别的,所以要开 long long

下面是考场代码,写得比较丑,虽然看着比较长但事实上有许多是直接复制粘贴的。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

namespace task1 { // BC
    int f[5000],g[20];
    void init() {
        for (int i=1;i<=4713;++i) f[i]=365+(i%4==1);
        for (int i=1;i<=4713;++i) f[i]+=f[i-1];
    }
    void main(ll r) {
        int p=lower_bound(f+1,f+4714,r)-f;
        int y=4714-p,m,d; r-=f[p-1];
        g[1]=31,g[2]=28+(y%4==1),g[3]=31,g[4]=30,g[5]=31,g[6]=30,g[7]=31,g[8]=31,g[9]=30,g[10]=31,g[11]=30,g[12]=31;
        for (int i=1;i<=12;++i) g[i]+=g[i-1];
        for (int i=1;i<=12;++i)
            if (g[i]>=r) { m=i,d=r-g[i-1]; break; }
        printf("%d %d %d BC\n",d,m,y);
    }
}

namespace task2 { // Before 1582.10.4
    int f[2000],g[20];
    void init() {
        for (int i=1;i<=1582;++i) f[i]=365+(i%4==0);
        for (int i=1;i<=1582;++i) f[i]+=f[i-1];
    }
    void main(ll r) {
        int y=lower_bound(f+1,f+1583,r)-f,m,d; r-=f[y-1];
        g[1]=31,g[2]=28+(y%4==0),g[3]=31,g[4]=30,g[5]=31,g[6]=30,g[7]=31,g[8]=31,g[9]=30,g[10]=31,g[11]=30,g[12]=31;
        for (int i=1;i<=12;++i) g[i]+=g[i-1];
        for (int i=1;i<=12;++i)
            if (g[i]>=r) { m=i,d=r-g[i-1]; break; }
        printf("%d %d %d\n",d,m,y);
    }
}

namespace task3 { // After 1582.10.15
    int g[20];
    ll sum(int y) { return 365ll*y+(y/4)-(y/100)+(y/400)+12; }
    int check(int y) { return (y%400==0)||(y%4==0&&y%100!=0); }
    void main(ll r) {
        if (r<=577825) { // 1582
            int y=1582,m,d; r-=577460;
            g[1]=31,g[2]=28+(y%4==0),g[3]=31,g[4]=30,g[5]=31,g[6]=30,g[7]=31,g[8]=31,g[9]=30,g[10]=31,g[11]=30,g[12]=31;
            for (int i=1;i<=12;++i) g[i]+=g[i-1];
            for (int i=1;i<=12;++i)
                if (g[i]>=r) { m=i,d=r-g[i-1]; break; }
            printf("%d %d %d\n",d,m,y);
            return;
        }
        int L=1583,R=1000000000;
        while (L<R) {
            int mid=(L+R)>>1;
            if (sum(mid)>=r) R=mid;
            else L=mid+1;
        }
        int y=L,m,d; r-=sum(y-1);
        g[1]=31,g[2]=28+check(y),g[3]=31,g[4]=30,g[5]=31,g[6]=30,g[7]=31,g[8]=31,g[9]=30,g[10]=31,g[11]=30,g[12]=31;
        for (int i=1;i<=12;++i) g[i]+=g[i-1];
        for (int i=1;i<=12;++i)
            if (g[i]>=r) { m=i,d=r-g[i-1]; break; }
        printf("%d %d %d\n",d,m,y);
    }
}

int main() {
    task1::init(),task2::init();
    int Q=read();
    while (Q--) {
        ll r=read()+1;
        if (r<=1721424) task1::main(r);
        else {
            r-=1721424;
            if (r<=577737) task2::main(r);
            else r+=10,task3::main(r);
        }
    }
    return 0;
}

当然你也可以不分成 3 段直接二分年,我没写不知道细节多不多。

当然你也可以直接 $\mathcal{O}(1)$ 算年,我懒得推式子不知道难不难推。