题解 P7075 【儒略日】
囧仙
2020-11-07 22:37:33
## $\stackrel{\text{废话}}{\textbf{前言}}$
- 这条题目成功加冕成为新一代毒瘤题我是没想到的。但 $\frak{u1s1}$ ，个人感觉这题不是很难，主要考的选手的细心程度。
- 个人总结，只要**不贪**，这题还是挺容易做的。
## 题解
让我们首先解决一些题面中给出的特殊情况。
- 起始时间为公元前 $4713$ 年 $1$ 月 $1$ 日。
- 公元 $1582$ 年 $10$ 月 $4$ 日以前，当一个年份被四整除时为闰年。但是如果一个年份在公元前，则应当将这个年份减去 $1$ 后进行闰年判定。
- 公元 $1582$ 年 $10$ 月 $5$ 日至 $10$ 月 $14$ 日被删除。
- 公元 $1582$ 年 $10$ 月 $15$ 日以后，一个年份为闰年，当且仅当它被四百整除或者能被四整除但不能被一百整除。
- 公元前一年的下一年，就是公元元年。
让我们先把闰年判定写出来。为了区分公元前后，我们用数字的正负进行区分。
```cpp
bool chk(i64 y){
if(y<=1582ll){
if(y<0ll) y=-y-1ll; return y%4ll==0ll;
}
return (y%400ll==0ll)||(y%4ll==0ll&&y%100ll!=0ll);
}
```
题目给了相当多的信息，尤其是非常多的时段分类……但是，如果你仔细思考时段的长度，你能发现，
$$\textbf{4713.1.1 BC 至 1582.10.15 一共不超过 2.5}\boldsymbol{\times 10^6 }\textbf{天}$$
所以，我们能非常简单的写出这样一份代码，直接枚举这所有天的情况。
```cpp
up(1,2305447,i){
Y[i]=Y[i-1],M[i]=M[i-1],D[i]=D[i-1]+1;
if(M[i]==12ll&&D[i]==32ll){
if(Y[i]==-1) Y[i]=1; else ++Y[i];
M[i]=1,D[i]=1;
} else if(Y[i]==1582ll&&M[i]==10ll&&D[i]==5ll){
Y[i]=1582ll,M[i]=10ll,D[i]=15ll;
} else if(M[i]==2ll&&chk(Y[i])&&D[i]==29ll){
continue;
} else if(D[i]>MD[M[i]]) ++M[i],D[i]=1;
}
//其中Yi,Mi,Di分别为第i天的年份、月份、日数。
//chk(Yi) 是检查Yi年是否是闰年。
```
- 经过一些暴力计算，我们能发现，$1600.1.1$ 的儒略日是 $2305448$ 。
好了，我们已经砍掉这题一半的难度了。下面考虑 $1600$ 年之后的事情。
要注意的是，**从天数推日期总是比从日期推天数难**。
这里启发我们二分年份，计算它和 $1600.1.1$ 的日期之差。（为什么是差值？因为差值可以忽略掉一些可能导致的错误，因为两个错误相减后会互相消去，可以大大提升调对的概率）。月份和日期都可以直接枚举。这题就做完了。
```cpp
//计算绝对日期
#define f(x) ((x)/4-(x)/100+(x)/400)
i64 clc(i64 y,i64 m,i64 d){
return 365ll*(y-1ll)+f(y-1ll)+((chk(y)&&m>=3ll)?1ll:0ll)+S[m-1ll]+d;
//这部分并不需要非常严格，因为我们只需要计算日期和1600.1.1的差值。
}
//主程序片段
dn(qread(),1,Q){
i64 t=qread(); if(t<=2305447ll){
i64 y=Y[t],m=M[t],d=D[t]; //直接从表中获取答案
if(y<0) printf("%lld %lld %lld BC\n",d,m,-y); //公元前
else printf("%lld %lld %lld\n",d,m, y); //公元后
} else {
t-=2305448ll; i64 y=0,m=1,d=1;
dn(30,0,i){ //二分
if(clc(y|(1<<i),m,d)-clc(1600,1,1)<=t) y|=1<<i;
}
up(1,12,i) if(clc(y,i,d)-clc(1600,1,1)<=t) m=i; //枚举月
up(1,31,i) if(clc(y,m,i)-clc(1600,1,1)<=t) d=i; //枚举日
printf("%lld %lld %lld\n",d,m,y);
}
}
```
## 参考代码
```cpp
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
i64 qread(){
i64 r=0,w=1,c=0;
for(c=getchar();!isdigit(c);c=getchar()) w=(c=='-'?-1:1); r=c-'0';
for(c=getchar(); isdigit(c);c=getchar()) r=r*10+c-'0';
return r*w;
}
const int MD[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
const int MAXN =2400000+3;
int Y[MAXN],M[MAXN],D[MAXN],S[13];
bool chk(i64 y){
if(y<=1582ll){
if(y<0ll) y=-y-1ll; return y%4ll==0ll;
}
return (y%400ll==0ll)||(y%4ll==0ll&&y%100ll!=0ll);
}
#define f(x) ((x)/4-(x)/100+(x)/400)
i64 clc(i64 y,i64 m,i64 d){
return 365ll*(y-1ll)+f(y-1ll)+((chk(y)&&m>=3ll)?1ll:0ll)+S[m-1ll]+d;
}
int main(){
freopen("julian.in","r",stdin);
freopen("julian.out","w",stdout);
Y[0]=-4713ll,M[0]=1ll,D[0]=1ll; up(1,12,i) S[i]=S[i-1]+MD[i];
up(1,2305447,i){
Y[i]=Y[i-1],M[i]=M[i-1],D[i]=D[i-1]+1;
if(M[i]==12ll&&D[i]==32ll){
if(Y[i]==-1) Y[i]=1; else ++Y[i];
M[i]=1,D[i]=1;
} else if(Y[i]==1582ll&&M[i]==10ll&&D[i]==5ll){
Y[i]=1582ll,M[i]=10ll,D[i]=15ll;
} else if(M[i]==2ll&&chk(Y[i])&&D[i]==29ll){
continue;
} else if(D[i]>MD[M[i]]) ++M[i],D[i]=1;
}
dn(qread(),1,Q){
i64 t=qread(); if(t<=2305447ll){
i64 y=Y[t],m=M[t],d=D[t];
if(y<0) printf("%lld %lld %lld BC\n",d,m,-y);
else printf("%lld %lld %lld\n",d,m, y);
} else {
t-=2305448ll; i64 y=0,m=1,d=1;
dn(30,0,i){
if(clc(y|(1<<i),m,d)-clc(1600,1,1)<=t) y|=1<<i;
}
up(1,12,i) if(clc(y,i,d)-clc(1600,1,1)<=t) m=i;
up(1,31,i) if(clc(y,m,i)-clc(1600,1,1)<=t) d=i;
printf("%lld %lld %lld\n",d,m,y);
}
}
return 0;
}
//这是赛时代码，马蜂可能比较丑，请见谅。
```