对 CSP-S T1 儒略日 的三份代码的分析与题解

尽管是一道简单的模拟题，但是却能反映出我和高水平选手的差距。

注：本文日期将由 YY/MM/DD 的形式描述。例如 2020 年 11 月 20 日为 2020/11/20，公元前将加上后缀 BC。如公元前 4713 年 1 月 1 日为 4713/1/1 BC

首先贴出三分将要被分析的代码：

#include<bits/stdc++.h>
typedef long long ll;
const int U=24e5,aa[14]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int Q,a[14],D[U],M[U],Y[U],d,m,y,L,bc;bool BC[U];
ll r;
int main(){
    freopen("julian.in","r",stdin);freopen("julian.out","w",stdout);
    d=1;m=1;y=4713;bc=1;
    for(;;){
        if(bc || y!=1582 || m!=10 || d<=4 || d>=15){
            D[L]=d;M[L]=m;Y[L]=y;BC[L]=bc;++L;
        }
        if(d==31 && m==12 && y==1582 && !bc)break;
        if(d==28 && m==2 && (bc?y%4==1:y%4==0))d=29,m=2;else{
            if(d==31 && m==12){
                d=m=1;
                if(bc)--y,y==0?y=1,bc=0:0;else ++y;
            }else if(d>=aa[m])d=1,++m;else ++d;
        }
    }
    for(scanf("%d",&Q);Q--;){
        scanf("%lld",&r);
        if(r<L){
            printf("%d %d %d %s\n",D[r],M[r],Y[r],BC[r]?"BC":"");
        }else{
            r-=L;d=m=1;y=1583;
            int z=365*400+97,x;
            y+=r/z*400;r%=z;
            for(;x=y%4==0 && (y%100 || y%400==0)?366:365,r>=x;r-=x,++y);
            for(;x=m==2 && y%4==0 && (y%100 || y%400==0)?29:aa[m],r>=x;r-=x,++m);
            printf("%d %d %d\n",d+(int)r,m,y);
        }
    }
}
// source ZJ-00783

#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"----------------"#x"----------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = "; For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned uint;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef pair <int,int> pii;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=7000*400;
struct date{
    int y,m,d,tp;
    date(){}
    date(int _y,int _m,int _d,int _tp){
        y=_y,m=_m,d=_d,tp=_tp;
    }
    friend bool operator == (date a,date b){
        return a.y==b.y&&a.m==b.m&&a.d==b.d&&a.tp==b.tp;
    }
}a[N],sd(1582,10,15,1),ed(1982,10,14,1),wtf(1582,10,4,1);
int sp,ep;
int md[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
date nxtday(date v){
    int y=v.y,m=v.m,d=v.d,tp=v.tp;
    if (tp==0){
        d++;
        int mxd=m==2&&y%4==1?29:md[m];
        if (d>mxd){
            d=1;
            m++;
            if (m>12){
                m=1;
                y--;
                if (y==0)
                    return date(1,1,1,1);
            }
        }
        return date(y,m,d,0);
    }
    else if (v==wtf){
        return sd;
    }
    else {
        d++;
        int mxd=m==2&&(y%4==0&&(y<=1582||y%100!=0||y%400==0))?29:md[m];
        if (d>mxd){
            d=1;
            m++;
            if (m>12){
                m=1;
                y++;
            }
        }
        return date(y,m,d,1);
    }
}
int main(){
#ifndef zzd
    freopen("julian.in","r",stdin);
    freopen("julian.out","w",stdout);
#endif
    date v=a[0]=date(4713,1,1,0);
    //0..ep-1
    for (int &i=ep=1;!(v==ed);i++){
        a[i]=v=nxtday(v);
        if (v==sd)
            sp=i;
    }
    int T=read();
    while (T--){
        LL x=read();
        if (x<sp){
            printf("%d %d %d%s\n",a[x].d,a[x].m,a[x].y,a[x].tp==0?" BC":"");
        }
        else {
            int rd=(x-sp)/(ep-sp);
            LL xx=x-rd*(ep-sp);
            printf("%d %d %d\n",a[xx].d,a[xx].m,a[xx].y+rd*400);
        }
    }
    return 0;
}
// source ZJ-00792

#include<bits/stdc++.h>
using namespace std;
bool Ka;
int Mon[]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
int _1=365,_4=_1*4+1,_100=_4*25-1,_400=_100*4+1,lim=107660;
int n,x,y,z,now;
long long a;
bool Bar;
int Chk(int x){
    return x%4==0&&(x<1582||x%100||x%400==0);;
}
int main() {
//  printf("%lf\n",(&Ka-&Bar)/1024.0/1024.0);
    freopen("julian.in","r",stdin);
    freopen("julian.out","w",stdout);
    scanf("%d",&n);
    for(int i=1; i<=n; ++i) {
        x=-4712,y=z=1;
        scanf("%lld",&a);
        while(a>=(_4*100)&&x+400<1582)x+=400,a-=_4*100;
        if(x==1288&&a>lim)a+=10;//,printf("++  ");
        while(a>=(now=(_1+(x%4==0)))&&x!=1582)a-=now,++x;
        x+=(a/_400)*400,a%=_400;
        while(a>=(now=(_1+Chk(x))))a-=now,++x;
        Mon[2]+=Chk(x);
        while(a>=Mon[y])a-=Mon[y],++y;
        Mon[2]=28;
        z+=a;
        printf("%d %d ",z,y);
        if(x<=0)printf("%d BC\n",-x+1);
        else printf("%d\n",x);
    }
    return 0;
}
// source ZJ-00127

这三份代码中，前两份代码的思路相似：通过一天一天地推到某个分界点。回答询问时，对询问在分界点前后进行讨论并回答。最后一份的代码思路是直接模拟地跳，但是运用了一些手段使得代码长度非常简单。

下面将对这两种思路分开进行分析。

思路一：一天一天地推再回答询问

前两份代码思路都是这种。

如果对于所有答案都一天一天推，那么复杂度将会是 O(r_i) 的。但是注意到在 1582/10/15 日之后，就可以直接以 400 年为步长进行跳跃。第一份代码就利用了这一点（对应代码 27，28 行），先将年份缩减至 400 年以内，然后再枚举年份进行跳跃即可。

注意到在预处理范围之外的日期，其实一定存在一个预处理范围之内的日期 xx（如第二份代码中命名），满足询问日期与 xx 仅在年份上差若干个 400 年。这样可以更简单地实现回答预处理范围之外的答案。

那么思路就非常清晰了，先递推，然后回答询问。因为是一天一天地推，细节非常少，实现非常简单。

自己在考后写的代码：

const int MAXN = 5e6 + 10;
const int month[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

#define chk(_) (tag ? (!(_.Y % 4) && ((_.Y % 100) || !(_.Y % 400))) : !(_.Y % 4))

bool tag;

struct Date {
    ll Y; int D, M;
    bool operator <(const Date& _) { return (Y < _.Y) || (Y == _.Y && M < _.M) || (Y == _.Y && M == _.M && D < _.D); }
    bool operator ==(const Date& _) { return (Y == _.Y) && (D == _.D) && (M == _.M); }
    Date() {}
    Date(int y, int m, int d) { Y = y, D = d, M = m; }
    void out() { IO::write(D), IO::write(M); (Y <= 0) ? IO::write(-Y + 1), puts("BC"), void() : IO::write(Y, '\n'), void(); }
} ans[MAXN];

ll st, ed;

Date St(1582, 10, 15);
Date BB(1582, 10, 4);
Date Ed(1982, 10, 15);

Date nxt(const Date& xx) {
    Date ret = xx;
    if (ret == BB) ret = St;
    else {
        bool tag = !(ret < St);
        ret.D++;
        if (ret.D > month[ret.M] + (ret.M == 2 && chk(ret))) ret.D = 1, ret.M++;
        if (ret.M > 12) ret.M = 1, ret.Y++;
    }
    return ret;
}

int main() {
    freopen("julian.in", "r", stdin);
    freopen("julian.out", "w", stdout);
    Date cur(-4712, 1, 1);
    ans[0] = cur;
    int idx = 1;
    while(cur < Ed) {
        ans[idx] = nxt(cur);
        if (ans[idx] == St) st = idx;
        if (ans[idx] == Ed) ed = idx;
        cur = ans[idx]; idx++;
    }
    int t; IO::read(t);
    rep(_, 1, t) {
        ll x; IO::read(x);
        if (x <= idx) ans[x].out();
        else {
            ll cnt = (x - st) / (ed - st);
            Date Ans = ans[x - cnt * (ed - st)]; Ans.Y += cnt * 400;
            Ans.out();
        }
    }
    return 0;
}

只要想到了这个思路，就可以非常快速地实现与调试。我认为在考场上选择这种思路是最优秀的。

思路二：模拟

第三份代码或许是一步一步从暴力讨论合并下来的，具体而言：

整个时间轴被 4713/1/1 BC，1/1/1，1582/10/4 分成了三部分，如果要对这三部分分开讨论，会非常麻烦。

如果能合并这三段就好了。

考虑到第一段（4713/1/1 BC - 1/1/1）和第二段（1/1/1 - 1582/10/4）的差距仅仅是在判断闰年是，第一段的闰年年份 \bmod 4 = 1，而第二段闰年年份 \bmod 4 = 0。为了合并，第三份代码将公元前第 x 年看作第 (-x + 1) 年，这样判断第一段和第二段时可以一样判断。达到了合并的目的。

第三段和第二段有两个区别：

• 判断闰年。第三段时格里高利历。为了合并，我们只需要维护一个标记，看答案是否是在第三段内。是的话就用格里高利历，否则就用儒略历。
• 跳过 1582/10/5 - 1582/10/14，同样的，如果答案是在第三段内，就给剩下未跳的天数加上 10，来保证跳过 1582/10/5 - 1582/10/14。

容易发现这两个步骤都只需要判断答案是否在 1582/10/4 之后。具体而言，先将时间推到 1582/1/1，然后判断剩下的天数是否超过了从 1 月 1 日到 10 月 4 日所需天数即可。

之后，先以 400 为步长地跳，执行上述两个步骤获取标记与加 10。再以 400 为步长地跳，然后枚举年份，以一个月为步长跳即可。

自己在考后写的代码：

typedef long long ll;

const int month[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
const int year = 365, fourYrs = year * 4 + 1, fourCtrs[] = { 100 * fourYrs, fourYrs * 100 - 3 };

int t, cur; bool tag;
ll Y; int D, M;

#define chk (tag ? (!(Y % 4) && ((Y % 100) || !(Y % 400))) : !(Y % 4))

void solve() {
    ll x; scanf("%lld", &x); tag = false;
    Y = -4712, D = M = 1;
    while ((x >= fourCtrs[tag]) && Y + 400 <= 1582) x -= fourCtrs[tag], Y += 400;
    while (x >= (cur = year + chk) && Y + 1 <= 1582) x -= cur, Y++;
    if (Y == 1582 && x >= 277) x += 10, tag = true;
    Y += 1ll * 400 * (x / fourCtrs[tag]), x %= fourCtrs[tag];
    while (x >= (cur = year + chk)) x -= cur, Y++;
    while (x >= (month[M] + (M == 2 && chk))) x -= month[M] + (M == 2 && chk), M++;
    D += x;
    printf("%d %d ", D, M);
    if (Y <= 0) printf("%lld BC\n", -Y + 1);
    else printf("%lld\n", Y);
}

int main() {
    freopen("julian.in", "r", stdin);
    freopen("julian.out", "w", stdout);
    scanf("%d", &t); while (t--) solve();
    return 0;
}

这个方法的代码非常短，经过一些压行，目前该代码是 LOJ 上最短的。但是该代码细节较之第一种思路略多，可能需要写的时候头脑清醒，不要一不留神就犯下错误。

对比两种思路

综合来看，我认为三份代码中一二份代码最优，不需要考虑太多细节，并且易于实现。但需要一些思维的基础，如果以前没有做过类似的题或许很难想到“先模拟一部分的答案”这个思路（例如我确实考场上就没想到）。而第三份代码则是基于暴力的讨论与模拟，这是更容易想到的。但是这种方法虽然思维含量相对不高，但细节较多。容易写错。如果不能理清思路，考虑完全，会像我一样得到很低地分数。

对比我和他们的差距

贴上考场写的代码：

typedef long long ll;

int q;
ll DD, MM, YY, x;

const ll month_days[2][14] = {{ 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }, { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }};
const ll centry_days[5] = { 36525, 36524, 36524, 36524 };

void get_DD_MM(bool tag) {
    for (int idx = 1; idx <= 12; ++idx) {
        if (x < month_days[tag][idx]) {
            DD += x;
            return ;
        } else MM++, x -= month_days[tag][idx];
    }
}

void get_YY(int flg) {
    if (x < 366) {
        get_DD_MM(true);
    } else {
        YY += flg; x -= 366;
        YY += x / 365 * flg; x = x % 365;
        get_DD_MM(false);
    }
}

void solve() {
    YY = DD = MM = 0;
    IO::read(x);
    if (x == 2299160) {
        DD = 4, MM = 10, YY = 1582;
        IO::write(DD, ' '), IO::write(MM, ' '), IO::write(YY, '\n');
        return ;
    } else if (x == 2299161) {
        DD = 15, MM = 10, YY = 1582;
        IO::write(DD, ' '), IO::write(MM, ' '), IO::write(YY, '\n');
        return ;
    }
    if (x < 1721424) { // Julian B.C.
        DD = 1, MM = 1, YY = 4713;
        YY -= x / 1461 * 4; // now its 1 1 ansYY
        x = x % 1461;
        get_YY(-1);
        IO::write(DD, ' '), IO::write(MM, ' '), IO::write(YY, ' '), puts("BC");
    } else if (1721424 <= x && x < 2299161) {
        x -= 1721424;
        YY = DD = MM = 1;
        YY += x / 1461 * 4; // now its 1 1 ansYY
        x = x % 1461;
        if (x < 1095) {
            YY += x / 365; x = x % 365;
            get_DD_MM(false);
        } else {
            x -= 1095;
            YY += 3, x = x % 365;
            get_DD_MM(true);
        }
        IO::write(DD, ' '), IO::write(MM, ' '), IO::write(YY, '\n');
    } else {
        YY = 1582, DD = 15, MM = 10;
        x -= 2299162;
        if (x < 6286) {
            if (x < 16) DD += x;
            else if (x < 77) {
                DD = 1, MM = 11; x -= 16;
                rep(i, 11, 12) {
                    if (x >= month_days[false][i]) x -= month_days[false][i], MM++;
                    else {
                        DD += x; break;
                    }
                }
            } else {
                x -= 77; YY = 1583; DD = MM = 1;
                YY += x / 1461 * 4;
                x = x % 1461;
                if (x < 365) {
                    get_DD_MM(false);
                } else if (x < 731) {
                    YY++; x -= 365, get_DD_MM(true);
                } else {
                    YY += 2, x -= 731;
                    YY += x / 365; x = x % 365;
                    get_DD_MM(false);
                }
            }
        } else {
            x -= 6286;
            YY = 1600, DD = MM = 1;
            YY += x / 146097 * 400; x = x % 146097;
            rep(i, 0, 3) {
                if (x >= centry_days[i]) YY += 100, x -= centry_days[i];
                else {
                    if (i == 0) {
                       YY += x / 1461 * 4;
                       x = x % 1461;
                       get_YY(1);
                    } else {
                        if (x < 1460) {
                            YY += x / 365; x = x % 365;
                            get_DD_MM(false);
                        } else {
                           x -= 1460; YY += 4;
                           YY += x / 1461 * 4;
                           x = x % 1461;
                           get_YY(1);
                        }
                    }
                    break;
                }
            }
        }

        IO::write(DD, ' '), IO::write(MM, ' '), IO::write(YY, '\n');
    }
}

int main() {
    // freopen("julian.in", "r", stdin);
    // freopen("julian.out", "w", stdout);
    IO::read(q);
    while (q--) solve();
    return 0;
}

直观的感受是，这份代码非常冗长。

虽然这份代码与第三份代码都是从暴力讨论出发，但是我没有进行合并等操作，导致需要分开处理三段。而且在计算 400 年内的递推时，我竟然没有枚举年份，而仍然是暴力讨论！这样讨论非常麻烦，需要先将时间调整到 1600/1/1 以从一个 \bmod 400 = 0 的年份开始，然后枚举这个年份是以 100 年一段的哪一段中……

总之，我的考场代码是“能讨论就不枚举”，总是想自己手算完所有情况呢，不把一些计算量较小的任务交给程序来做，而这恰恰是程序最擅长的。

题做少了，代码写少了，基础薄弱了，思路狭窄了。

接下来很长的一段时间里，我会着重强化自己的基础，提高自己的实现能力。

继续努力！