P7075 [CSP-S2020] 儒略日
题面：
题目描述
为了简便计算，天文学家们使用儒略日（Julian day）来表达时间。所谓儒略日，其定义为从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数，不满一天者用小数表达。若利用这一天文学历法，则每一个时刻都将被均匀的映射到数轴上，从而得以很方便的计算它们的差值。
现在，给定一个不含小数部分的儒略日，请你帮忙计算出该儒略日（一定是某一天的中午 12 点）所对应的公历日期。
我们现行的公历为格里高利历（Gregorian calendar），它是在公元 1582 年由教皇格里高利十三世在原有的儒略历（Julian calendar）的基础上修改得到的（注：儒略历与儒略日并无直接关系）。具体而言，现行的公历日期按照以下规则计算：
- 公元 1582 年 10 月 15 日（含）以后：适用格里高利历，每年一月 31 31 31 天、 二月 28 28 28 天或 29 29 29 天、三月 31 31 31 天、四月 30 30 30 天、五月 31 31 31 天、六月 30 30 30 天、七月 31 31 31 天、八月 31 31 31 天、九月 30 30 30 天、十月 31 31 31 天、十一月 30 30 30 天、十二月 31 31 31 天。其中，闰年的二月为 29 29 29 天，平年为 28 28 28 天。当年份是 400 400 400 的倍数，或日期年份是 4 4 4 的倍数但不是 100 100 100 的倍数时，该年为闰年。
- 公元 1582 年 10 月 5 日（含）至 10 月 14 日（含）：不存在，这些日期被删除，该年 10 月 4 日之后为 10 月 15 日。
- 公元 1582 年 10 月 4 日（含）以前：适用儒略历，每月天数与格里高利历相同，但只要年份是 4 4 4 的倍数就是闰年。
- 尽管儒略历于公元前 45 年才开始实行，且初期经过若干次调整，但今天人类习惯于按照儒略历最终的规则反推一切 1582 年 10 月 4 日之前的时间。注意，公元零年并不存在，即公元前 1 年的下一年是公元 1 年。因此公元前 1 年、前 5 年、前 9 年、前 13 年……以此类推的年份应视为闰年。
输入格式
第一行一个整数 Q Q Q，表示询问的组数。
接下来 Q Q Q 行，每行一个非负整数 r i r_i ri，表示一个儒略日。输出格式
对于每一个儒略日 r i r_i ri，输出一行表示日期的字符串 s i s_i si。共计 Q Q Q 行。 s i s_i si 的格式如下：
- 若年份为公元后，输出格式为
Day Month Year。其中日（Day）、月（Month）、年（Year）均不含前导零，中间用一个空格隔开。例如：公元
2020 年 11 月 7 日正午 12 点，输出为7 11 2020。- 若年份为公元前，输出格式为
Day Month Year BC。其中年（Year）输出该年份的数值，其余与公元后相同。例如：公元前 841 年 2 月 1 日正午 12
点，输出为1 2 841 BC。样例 #1
样例输入 #1
3 10 100 1000样例输出 #1
11 1 4713 BC 10 4 4713 BC 27 9 4711 BC样例 #2
样例输入 #2
3 2000000 3000000 4000000样例输出 #2
14 9 763 15 8 3501 12 7 6239样例 #3
样例输入 #3
见附件中的 julian/julian3.in样例输出 #3
见附件中的 julian/julian3.ans提示
【数据范围】
测试点编号 Q = Q = Q= r i ≤ r_i \le ri≤ 1 1 1 1000 1000 1000 365 365 365 2 2 2 1000 1000 1000 1 0 4 10^4 104 3 3 3 1000 1000 1000 1 0 5 10^5 105 4 4 4 10000 10000 10000 3 × 1 0 5 3\times 10^5 3×105 5 5 5 10000 10000 10000 2.5 × 1 0 6 2.5\times 10^6 2.5×106 6 6 6 1 0 5 10^5 105 2.5 × 1 0 6 2.5\times 10^6 2.5×106 7 7 7 1 0 5 10^5 105 5 × 1 0 6 5\times 10^6 5×106 8 8 8 1 0 5 10^5 105 1 0 7 10^7 107 9 9 9 1 0 5 10^5 105 1 0 9 10^9 109 10 10 10 1 0 5 10^5 105 年份答案不超过 1 0 9 10^9 109
有点大的模拟，放在 CSP-D2T1 恐怖如斯.
我们看到 “年份答案不超过 1 0 9 10^9 109” 这句话，意味着我们肯定用二分，其他方法我赛场上多半想不到吧.
二分年份，但是分讨，分为公元前和公元后，公元后又分为 1582 1582 1582 年以前， 1582 1582 1582 年以后.
公元前注意刚开始的 B C BC BC 4713 4713 4713 年 1 1 1 月份 只有 30 30 30 天，且闰年为 { x ∣ [ 4 ∣ ( x − 1 ) ] } \{x | [4 \mid (x - 1)]\} {x∣[4∣(x−1)]}
我们可以通过另起一个程序暴力计算公元前的天数为 ： 1721423 1721423 1721423，
由于 1582 1582 1582 年前 闰年为 x ∣ [ 4 ∣ x ] {x | [4 \mid x]} x∣[4∣x]， 1582 1582 1582 年后 闰年为 { x ∣ [ ( 4 ∣ x ⋀ 100 ∤ x ) ⋁ ( 400 ∣ x ) ] } \{x | [(4 \mid x \bigwedge 100 \nmid x)\bigvee(400 \mid x)]\} {x∣[(4∣x⋀100∤x)⋁(400∣x)]}，且 1582 1582 1582 年的 10 10 10 月 消失了 5 ∼ 14 5 \sim 14 5∼14 这 10 10 10 天
所以，新建一个程序算出公元 1 ∼ 1582 1 \sim 1582 1∼1582 年 （含 1582 1582 1582 年） 共计 577815 577815 577815 天
判断闰年的时候，公元前 4713 4713 4713 本身就是闰年，但是他的 1 1 1 月份只有 30 30 30 天，所以他这年本身还是 365 365 365 天
其中分讨时，公元前闰月（除去 4713 4713 4713 年）有 4713 − T − 1 4 \frac{4713 - T - 1}{4} 44713−T−1 个（ T T T 为终止年份），公元 1582 1582 1582 年以前有 T 4 \frac{T}{4} 4T，
公元 1582 1582 1582 年后的 1584 1584 1584 年是第一个闰年，请以此为基准进行计算，在 1584 1584 1584 年之后、 1600 1600 1600 年之前 有 T − 1584 4 + 1 \frac{T - 1584}{4} + 1 4T−1584+1 个闰年，
公元后 1600 1600 1600 年之后，用容斥计算，有 T − 1584 4 + 1 − T − 1600 100 − 1 + T − 1600 400 + 1 = T − 1584 4 − T − 1600 100 + T − 1600 400 + 1 \frac{T - 1584}{4} + 1 - \frac{T - 1600}{100} - 1 + \frac{T - 1600}{400} + 1 = \frac{T - 1584}{4} - \frac{T - 1600}{100} + \frac{T - 1600}{400} + 1 4T−1584+1−100T−1600−1+400T−1600+1=4T−1584−100T−1600+400T−1600+1 个闰年。
闰月的计算先告一段落，来谈谈二分
我已经被所谓万能二分搞崩溃了，决心还是不用了
请正常二分，设计 c h e c k check check 函数，求到达目前年份 1 1 1 月 1 1 1 日的总天数，尤其是上面的闰年的计算需要重点关注！
因为公元没有 0 0 0 世纪，所以二分的 m i d mid mid 是要减一计算的。
然后是月份计算，先判断重要月份，预处理出 B C 4713 BC\ 4713 BC 4713 年的月份天数前缀和， 1582 1582 1582 年的月份天数前缀和，闰年的月份天数前缀和，非闰年的月份天数前缀和,和它们每个月的天数
int _m[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int yeapm[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
int _sm[13] = {0,31,59,90,120,151,181,212,243,273,304,334,365};
int yeap_sm[13] = {0,31,60,91,121,152,182,213,244,274,305,335,366};
int _1852[13] = {0,31,28,31,30,31,30,31,31,30,21,30,31};
int _s1852[13] = {0,31,59,90,120,151,181,212,243,273,294,324,355};
int _4713[13] = {0,30,29,31,30,31,30,31,31,30,31,30,31};
int _s4713[13] = {0,30,59,90,120,151,181,212,243,273,304,334,365};
然后针对
1582
1582
1582，
B
C
4713
BC\ 4713
BC 4713，闰年，非闰年 分讨；我校学长经典名言：分分分
×
×
×
\times\times\times
××× 讨讨讨
\sqrt{}\sqrt{}\sqrt{}
注意!有一组数据是
input:
...
0
...
output:
...
1 1 4713 BC
...
请不要输出
...
0 0 4713 BC
...
本人就是因为这个没有过第一个点。
然后减去前面月份的天数前缀和，
再对
1582
1582
1582 年的
10
10
10 月份和
B
C
4713
BC\ 4713
BC 4713 的
1
1
1 月份进行特判即可！
AC-code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int rd() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
void wt(int x) {
static int sta[35];
int f = 1;
if(x < 0) f = -1,x *= f;
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
if(f == -1) putchar('-');
while (top) putchar(sta[--top] + 48);
}
namespace workspace{
int y,m,d;
bool BC = false;
const int bef = 1721423;
int getytd(int yr) {
int re = 0,ypyr = 0;
if(!BC) {
yr--;
if(yr >= 1582) {
re += 577815;
if(yr >= 1584) ypyr += (yr - 1584) / 4 + 1;
if(yr >= 1600) ypyr -= (yr - 1600) / 100 + 1,ypyr += (yr - 1600) / 400 + 1;
yr -= 1582;
}else ypyr = yr / 4;
}else {
yr = 4713 - yr;
ypyr += (yr - 1) / 4;
}
re = ypyr + yr * 365 + re;
return re;
}
bool yeap(int yr) {
if(BC) return ((yr - 1) % 4 == 0);
else if(yr <= 1582) return (yr % 4 == 0);
return ((yr % 4 == 0 && yr % 100 != 0)|| yr % 400 == 0);
}
int _m[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int yeapm[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
int _sm[13] = {0,31,59,90,120,151,181,212,243,273,304,334,365};
int yeap_sm[13] = {0,31,60,91,121,152,182,213,244,274,305,335,366};
int _1852[13] = {0,31,28,31,30,31,30,31,31,30,21,30,31};
int _s1852[13] = {0,31,59,90,120,151,181,212,243,273,294,324,355};
int _4713[13] = {0,30,29,31,30,31,30,31,31,30,31,30,31};
int _s4713[13] = {0,30,59,90,120,151,181,212,243,273,304,334,365};
void getday(int yr,int mon,int dy) {
if(!BC && yr == 1582 && mon == 10) {
if(dy <= 4) d = dy;
else d = dy + 10;
}else if(BC && yr == 4713 && mon == 1){
d = dy + 1;
}else d = dy;
}
void getmonth(int yr,int dy) {
int &mon = m;
if(!BC && yr == 1582) {
while(mon++ < 12) if(_s1852[mon] > dy) break;
dy -= _s1852[mon - 1];
if(dy == 0) dy = _1852[--mon];
}else if(BC && yr == 4713) {
while(mon++ < 12) if(_s4713[mon] > dy) break;
dy -= _s4713[mon - 1];
if(dy == 0) dy = _4713[--mon];
}else if(yeap(yr)) {
while(mon++ < 12) if(yeap_sm[mon] > dy) break;
dy -= yeap_sm[mon - 1];
if(dy == 0) dy = yeapm[--mon];
}else {
while(mon++ < 12) if(_sm[mon] > dy) break;
dy -= _sm[mon - 1];
if(dy == 0) dy = _m[--mon];
}
if(m == 0) dy = 0,m++;
getday(y,m,dy);
}
void getyear(int dy) {
int del = 0;
if(!BC) {
int l = 1,r = 1e9+5;
while(l < r) {
int mid = (l + r + 1) >> 1;
int t = getytd(mid);
if(t >= dy) r = mid - 1; //本年份不计算
else l = mid,del = t;
}
y = l;
}else {
int l = 1,r = 4713;
while(l < r) {
int mid = (l + r) >> 1;
int t = getytd(mid);
if(t >= dy) l = mid + 1;
else r = mid,del = t;
}
y = r;
}
getmonth(y,dy - del);
}
void print() {
wt(d),putchar(' ');
wt(m),putchar(' ');
wt(y),putchar(' ');
if(BC) putchar('B'),putchar('C');
putchar('\n');
}
void solve(){
y = m = d = 0;
int r = rd();
BC = r < bef;
getyear(BC ? r : r - bef);
print();
}
}
signed main() {
int q = rd();
while(q--) workspace::solve();
return 0;
}
/*
良心数据，检查你是否也在这些数据上栽了
2
2000000
3000000
1
154059721
2
3251
8793
1
2378588
1
1721236
*/
模拟还是一如既往的简单但难写
标签：10,4713,1582,题解,31,30,儒略,int,P7075 From： https://blog.csdn.net/qq_49785217/article/details/141685988