题解 P7075 【儒略日】

Fading

2020-11-11 22:20:58

Solution

心血来潮,来一个 $40$ 分钟内想 + 写 + 调的做法,作为自己最后一篇题解吧。 这个做法有一个优点就是**不会挂**,只要过了大样例就是对的。 ## 注意要 #define int long long !!! 首先将询问离线。 - 记录 rmon 数组表示闰年月份,mon 数组表示普通年月份。 - 定义一个结构体 QWQ 表示当前日期。 - 写一个判断闰年的函数 bool isr(QWQ x)。 - 写一个函数 QWQ nextday(QWQ x) 表示 $x$ 的下一天,返回一个 QWQ 类型。 这个函数需要讨论的是:当前是否是 $1582$ 年,当前是否是公元**前** $1$ 年(要进到公元 1 年),当前是否是 $1582$ 前的闰年,当前是否是 $1582$ 后的闰年。 这个分类讨论还是比较清晰的。 - 对于 $-4713.1.1 \sim 1999.12.31$ 这段时间,从元年开始暴力 nextday 函数求。打表出来第 $2451545$ 年就是 $2000.1.1$。 接下来闰年很难做怎么办?继续考虑暴力。打表打出这 $400$ 年有 $146097$ 天。 我们考虑暴力把这 $400$ 天用 nextday 函数跑出来,然后减去 $2451545$ 再除 $146097$ 求出这是第几轮循环(即第几个 $400$ 年),简单讨论一下就好了。 这样前面一步错样例就过不去,所以不可能挂分了。 时间复杂度 $O(2451545+146097+Q)$。~~我知道这样描述时间复杂度不严谨,但是就这样吧。~~ 代码其实很好写,中间那一大段都是复制粘贴的,所以看起来很长,但实际就那么一点点... ```cpp #include<bits/stdc++.h> #define ll long long #define int long long //重要 #define gc getchar using namespace std; inline ll read(){ ll x=0,f=1;char ch=gc(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=gc();} while (isdigit(ch)){x=x*10ll+ch-'0';ch=gc();} return x*f; } const int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; const int rmon[13]={0,31,29,31,30,31,30,31,31,30,31,30,31}; struct que{ int t,id; }q[1010101]; struct QWQ{ int y,m,d; }ori,tmp,ans[101010],X[300001]; int Q,mx,cnt; inline bool cmp(que a,que b){return a.t<b.t;} inline int mabs(int x){return (x>0?x:-x);} inline bool isr(QWQ a){ if (a.y<0) return (-a.y-1)%4==0; if (a.y>=1582) return a.y%400==0||(a.y%4==0&&a.y%100); if (a.y%4==0) return 1; return 0; } inline QWQ nextday(QWQ a){ //分类讨论 QWQ ans=a; if (a.y==1582){ if (a.m==12&&a.d==31) ans.y++,ans.d=1,ans.m=1; else if (a.m==10&&a.d==4) ans.d=15; else if (a.d==mon[a.m]) ans.d=1,ans.m++; else ans.d++; return ans; } if (a.y==-1&&a.m==12&&a.d==31) ans.y=1,ans.d=1,ans.m=1; else if (isr(a)){ if (a.m==12&&a.d==31) ans.y++,ans.d=1,ans.m=1; else if (a.d==rmon[a.m]) ans.d=1,ans.m++; else ans.d++; }else{ if (a.m==12&&a.d==31) ans.y++,ans.d=1,ans.m=1; else if (a.d==mon[a.m]) ans.d=1,ans.m++; else ans.d++; } return ans; } signed main(){ ori.y=-4713,ori.m=1,ori.d=1,cnt=-1; Q=read(); for (int i=1;i<=Q;i++) q[i].id=i,q[i].t=read(); sort(q+1,q+1+Q,cmp); tmp=ori; for (int i=1;i<=Q;i++){ if (q[i].t>=2451545) break; mx=i; } for (int i=1,now=0;i<=mx;i++){ for (;now!=q[i].t;now++) tmp=nextday(tmp); ans[q[i].id]=tmp; } tmp.d=1,tmp.m=1,tmp.y=2000; for (;tmp.y!=2400;) X[++cnt]=tmp,tmp=nextday(tmp); for (int i=mx+1;i<=Q;i++){ ans[q[i].id].d=X[(q[i].t-2451545)%146097].d; ans[q[i].id].m=X[(q[i].t-2451545)%146097].m; ans[q[i].id].y=X[(q[i].t-2451545)%146097].y+400*((q[i].t-2451545)/146097); } for (int i=1;i<=Q;i++){ printf("%lld %lld %lld",ans[i].d,ans[i].m,mabs(ans[i].y)); if (ans[i].y<0) printf(" BC"); puts(""); } return 0; } ```