题解 P7075 [CSP-S2020] 儒略日
当时考场上因为这个炸掉，一年后回来复仇。
这里提供一个与大多数人不一样的做法。
首先考虑一个简单一些的问题，怎么应付单个询问？
不难想到，我们对于一个日期，让他从 $-4713$ 年 $1$ 月 $1$ 日开始，然后一年一年地加，年加不了了加月，月加不了了加日。这样很容易做，具体的细节可以看代码实现。这样就拿下了 $50pts$。
但是肯定不能满足于这 $50$ 分。对于数据过大造成的TLE，我们考虑扩展我们的做法。实际上，优化的本质是重复利用之前已经求过的东西。然后可以想到从每个询问入手。可以自己先思考一下再往下看。
我们可以考虑将询问离线然后排序，每次将上一次求出的答案为起始的日期，然后重复较为暴力的算法。但是由于有的月份的上限比别的月份高，又或者 $1582$ 年这种比较特殊的日子，我们不能直接跑暴力的操作。我们需要把起始日期再转换为 $n$ 年 $1$ 月 $1$ 日 这种形式的日期，再跑暴力。这里面有一些的细节，可以自己先尝试写，再看具体代码实现。(如我的实现有问题可以私信提醒我一下，谢谢！)
发现这么写得到了 $90pts$ 的好成绩，但是就是没切，有些许难受。没关系，我们继续优化。我们不难发现对于在 $1852$ 年之后的日子，是满足连续 $400$ 年的总天数是一定的，可以自己尝试算一下有多少天。
具体就是 $146097$ 天，算法就是 $400\times 365+100-4+1$ ，$400$ 天里 $100$ 个 $4$ 的倍数，$4$ 个 $100$ 的倍数，$1$ 个 $400$ 的倍数。
然后我们在暴力操作里面在一年一年加前面加上 $400$ 年 $400$ 年地加，就可以愉快的 $AC$ 了！
Code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define filein(a) freopen(#a".in","r",stdin)
#define fileot(a) freopen(#a".out","w",stdout)
inline int read(){
int s=0,f=1;char ch=getchar();
while(ch<'0'||'9'<ch) {if(ch=='-') f=-1;ch=getchar();}
while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}
return s*f;
}//经典快读
inline ll read_ll(){
ll s=0;int f=1;char ch=getchar();
while(ch<'0'||'9'<ch) {if(ch=='-') f=-1;ch=getchar();}
while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}
return s*f;
}//快读long long版
inline void write(int x,char g){
static char ch[30],top;
top=0;if(x<0) {putchar('-');x=-x;}
do{ch[++top]=x-x/10*10;} while(x/=10);
do{putchar(ch[top--]+'0');} while(top);
if(g!=0) putchar(g);
}//经典快写
inline void write_st(short x,char g){
static char ch[30],top;
top=0;if(x<0) {putchar('-');x=-x;}
do{ch[++top]=x-x/10*10;} while(x/=10);
do{putchar(ch[top--]+'0');} while(top);
if(g!=0) putchar(g);
}//快写short版
int mt[12+3]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int yt[2+3]={365,366};
inline bool isR(int x){
if(x<0) return !((x+1)%4);
if(x<=1582) return !(x%4);
return ((!(x%4) and x%100) or !(x%400) );
}//判断是否为闰年
inline short adm(short x,int y){
if(y!=1582) return 0;
if(x==10) return -10;
return 0;
}//用来处理1582
inline short ady(int x){
if(x==1582) return -10;
return 0;
}//同上
struct ques{
int id;ll x;
inline friend bool operator<(ques x,ques y){
return x.x<y.x;
}
}q[(int)1e5+3];
int ay[(int)1e5+3];short am[(int)1e5+3],ad[(int)1e5+3];
int ckt1;
inline void ck1() {ckt1=clock();}
inline void ck2() {printf("%dms\n",clock()-ckt1);}
//这个是测速用的，可以忽略
int main(){
//filein(a);fileot(a);
int Q=read();
for(int i=1;i<=Q;++i){
q[i].x=read_ll();
q[i].id=i;
}
sort(q+1,q+1+Q);//操作离线
for(int ss=1;ss<=Q;++ss){
ll x=q[ss].x;
int y=-4713;short m=1,d=1;
if(ss!=1){//这个就是转换了
x-=q[ss-1].x;
y=ay[q[ss-1].id];
m=am[q[ss-1].id];
d=ad[q[ss-1].id];
//printf("%d %d %d %d\n",q[ss-1].id,d,m,y);
if(m!=1){
if(d!=1){
short kb=0;
if(d<5 and y==1582 and m==10){
kb+=10;
}//越过空的日期
if(x+kb>=mt[m]+((m==2)?isR(y):0)-d+1){
x+=kb;
x-=mt[m]+((m==2)?isR(y):0)-d+1;
d=1;++m;
if(m>12){
m-=12;
++y;
if(y==0) y=1;
}
if(m!=1){
bool flag=0;
for(short i=m;i<=12;++i){
if(x>=mt[i]+((i==2)?isR(y):0+adm(i,y) ) ){
x-=mt[i]+((i==2)?isR(y):0+adm(i,y) );
}else{
d+=x;
if(d-x<=4 and d>4 and y==1582 and m==10){
d+=10;
}//这边越过空的日期花费了能量，补回来，下面的重复操作同理
ay[q[ss].id]=y;
am[q[ss].id]=i;
ad[q[ss].id]=d;
flag=1;break;//发现在转换的过程中就找到答案了，就结束操作，下面的重复操作同理
}
}
if(flag) {continue;}
m=1;++y;
if(y==0) y=1;
}
}else{
d+=x;
if(d-x<=4 and d>4 and y==1582 and m==10){
d+=10;
}
ay[q[ss].id]=y;
am[q[ss].id]=m;
ad[q[ss].id]=d;
continue;
}
}else{
bool flag=0;
for(short i=m;i<=12;++i){
if(x>=mt[i]+((i==2)?isR(y):0+adm(i,y) ) ){
x-=mt[i]+((i==2)?isR(y):0+adm(i,y) );
}else{
d+=x;
if(d-x<=4 and d>4 and y==1582 and m==10){
d+=10;
}
ay[q[ss].id]=y;
am[q[ss].id]=i;
ad[q[ss].id]=d;
flag=1;break;
}
}
if(flag){continue;}
m=1;++y;
if(y==0) y=1;
}
}else if(d!=1){
short kb=0;
if(d<5 and y==1582 and m==10){
kb+=10;
}
if(x+kb>=mt[m]-d+1){
x+=kb;
x-=mt[m]-d+1;
d=1;++m;
bool flag=0;
for(short i=m;i<=12;++i){
if(x>=mt[i]+((i==2)?isR(y):0+adm(i,y) ) ){
x-=mt[i]+((i==2)?isR(y):0+adm(i,y) );
}else{
d+=x;
if(d-x<=4 and d>4 and y==1582 and m==10){
d+=10;
}
ay[q[ss].id]=y;
am[q[ss].id]=i;
ad[q[ss].id]=d;
flag=1;break;
}
}
if(flag) {continue;}
m=1;++y;
if(y==0) y=1;
}else{
d+=x;
if(d-x<=4 and d>4 and y==1582 and m==10){
d+=10;
}
ay[q[ss].id]=y;
am[q[ss].id]=m;
ad[q[ss].id]=d;
continue;
}
}
}
//printf(" %d %d %d %d\n",d,m,y,x);
bool Type=0;
if(y>1582)
while(x>=146100){
x-=146097;
y+=400;
}
while(x>=yt[Type=isR(y)]+ady(y) ){
x-=yt[Type]+ady(y);
++y;
if(y==0) y=1;
}
Type=isR(y);
while(x>=(mt[m]+((m==2)?Type:0+adm(m,y)) ) ){
x-=mt[m]+((m==2)?Type:0)+adm(m,y);
++m;
}
d+=x;
if(d-x<=4 and d>4 and y==1582 and m==10){
d+=10;
}
ay[q[ss].id]=y;
am[q[ss].id]=m;
ad[q[ss].id]=d;
}
for(int i=1;i<=Q;++i){
int y=ay[i];short m=am[i],d=ad[i];
if(y<0){
write_st(d,' ');write_st(m,' ');write(-y,' ');
printf("BC\n");
}else{
write_st(d,' ');write_st(m,' ');write(y,'\n');
}
}//输出
return 0;
}