题解 P7075 【儒略日】
Fading
2020-11-11 22:20:58
心血来潮,来一个 $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;
}
```