洛谷P7075 [CSP-S2020] 儒略日

洛谷P7075 [CSP-S2020] 儒略日

洛谷题目传送门

题目描述

为了简便计算，天文学家们使用儒略日（Julian day）来表达时间。所谓儒略日，其定义为从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数，不满一天者用小数表达。若利用这一天文学历法，则每一个时刻都将被均匀的映射到数轴上，从而得以很方便的计算它们的差值。

现在，给定一个不含小数部分的儒略日，请你帮忙计算出该儒略日（一定是某一天的中午 12 点）所对应的公历日期。

我们现行的公历为格里高利历（Gregorian calendar），它是在公元 1582 年由教皇格里高利十三世在原有的儒略历（Julian calendar）的基础上修改得到的（注：儒略历与儒略日并无直接关系）。具体而言，现行的公历日期按照以下规则计算：

1. 公元 1582 年 10 月 15 日（含）以后：适用格里高利历，每年一月 $31$ 天、 二月 $28$ 天或 $29$ 天、三月 $31$ 天、四月 $30$ 天、五月 $31$ 天、六月 $30$ 天、七月 $31$ 天、八月 $31$ 天、九月 $30$ 天、十月 $31$ 天、十一月 $30$ 天、十二月 $31$ 天。其中，闰年的二月为 $29$ 天，平年为 $28$ 天。当年份是 $400$ 的倍数，或日期年份是 $4$ 的倍数但不是 $100$ 的倍数时，该年为闰年。
2. 公元 1582 年 10 月 5 日（含）至 10 月 14 日（含）：不存在，这些日期被删除，该年 10 月 4 日之后为 10 月 15 日。
3. 公元 1582 年 10 月 4 日（含）以前：适用儒略历，每月天数与格里高利历相同，但只要年份是 $4$ 的倍数就是闰年。
4. 尽管儒略历于公元前 45 年才开始实行，且初期经过若干次调整，但今天人类习惯于按照儒略历最终的规则反推一切 1582 年 10 月 4 日之前的时间。注意，公元零年并不存在，即公元前 1 年的下一年是公元 1 年。因此公元前 1 年、前 5 年、前 9 年、前 13 年……以此类推的年份应视为闰年。

输入格式

第一行一个整数 $Q$，表示询问的组数。
接下来 $Q$ 行，每行一个非负整数 $r_i$，表示一个儒略日。

输出格式

对于每一个儒略日 $r_i$，输出一行表示日期的字符串 $s_i$。共计 $Q$ 行。 $s_i$ 的格式如下：

1. 若年份为公元后，输出格式为 Day Month Year。其中日（Day）、月（Month）、年（Year）均不含前导零，中间用一个空格隔开。例如：公元
   2020 年 11 月 7 日正午 12 点，输出为 7 11 2020。
2. 若年份为公元前，输出格式为 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=$	$r_i\le$
$1$	$1000$	$365$
$2$	$1000$	$10^4$
$3$	$1000$	$10^5$
$4$	$10000$	$3\times 10^5$
$5$	$10000$	$2.5\times 10^6$
$6$	$10^5$	$2.5\times 10^6$
$7$	$10^5$	$5\times 10^6$
$8$	$10^5$	$10^7$
$9$	$10^5$	$10^9$
$10$	$10^5$	年份答案不超过 $10^9$

思路详解

一开始想到的直接是打表，但一看数据范围1e9直接放弃打表，考虑使用**O(1)**代码。

公元 1582 年 10 月 15(5) 日（含）以后

根据题目可得，在这个神秘的日期之后，就只有满足年份 y (y%400=0||(y%4=0&&y%100!=0))的才为闰年。
可我们如果直接按这个日期考虑那就过于复杂。思考既然400年一个周期，那我们直接找1582之前最近的400的倍数即可。这个年份即为1200年，找到这个年份的1月1日对应的儒略日$N_{1200}$，用输入的儒略日$n$减去它即可。但我们发现由于中间消失了10天，那我们的$n$应减去10。还有根据新历法，1300，1400，1500不算闰年，所以$n$还要减去3。

综上，$n=n-N_{1200}+10-3$。然后我们计算出有多少个400年，再将其乘上400，即可得到重复的年数$y$。再将$n$除余上400年的天数即可得到不满400年的天数，这一部分数据很小，我们可以打表了。打表很简单，直接放代码里了，不懂得去看。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=(1582+4712)*365+(1582+4712)/4+31+28+31+30+31+30+31+31+30+4;//公元 1582 年 10 月 4 日对应的儒略日
const ll N1200=(1200+4712)*365+(1200+4712)/4;//公元 1200 年 1 月 1 日对应的儒略历
const ll gg=400*365+97;//新历法400年的天数
ll b[14]={0,31,28,31,30,31,30,31,31,30,31,30,31};//不闰月每月天数
ll c[14]={0,31,29,31,30,31,30,31,31,30,31,30,31};//闰月每月天数
ll t,n;
ll day[gg+5],month[gg+5],year[gg+5];//每400年第 i 天所对应的日，月，年
ll check(ll y,ll m){//寻找 y 年对于的月份月数if(((y)%4==0&&(y)%100!=0)||((y)%400==0))return c[m];return b[m];
}
int main(){
//	freopen("julian3.in","r",stdin);
//	freopen("julian3.out","w",stdout);cin>>t;day[0]=1;month[0]=1;//记得赋初值!!!for(ll i=1;i<gg;i++){day[i]=day[i-1]+1;//每天多一天month[i]=month[i-1];//每天不一定多一月/一年year[i]=year[i-1];if(day[i]>check(year[i],month[i])){//判断一月是否结束month[i]++;day[i]=1;}if(month[i]>12){//判断一年是否结束year[i]++;month[i]=1;}}for(ll i=1;i<=t;i++){cin>>n;if(n<=N){??????????}else{n-=N1200;n=n+10-3;//由公式可得ll t=n/gg*400+1200;//整400年的年数n=n%gg;//不满400年的天数cout<<day[n]<<' '<<month[n]<<' '<<t+year[n]<<'\n';//直接输出即可}}return 0;
}

公元 1582 年 10 月 4 日（含）以前

由于这个日期以前是4年一次闰年，那就不用400年一循环了，而是求出整4年的年数，在打表求不满4年的。

那我们需不需要在打一次表呢？？？不，由于一共只有4年，我们可以直接沿用新历法打的表(上100年才会有影响)。

if(n<=N){ll y=n/(365*4+1)*4;//整4年的天数n%=(365*4+1);//不满4年的天数if(y+year[n]-4712<=0){//由于没有公元0年，那我们将公元前4713年向后平移1年，即4712cout<<day[n]<<' '<<month[n]<<' '<<4713-(y+year[n])<<" BC"<<'\n';//记得加 1}else{cout<<day[n]<<' '<<month[n]<<' '<<y+year[n]-4712<<'\n';//公元后无需加1，不信的话可以自己举一下。}}

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=(1582+4712)*365+(1582+4712)/4+31+28+31+30+31+30+31+31+30+4;//公元 1582 年 10 月 4 日对应的儒略日
const ll N1200=(1200+4712)*365+(1200+4712)/4;//公元 1200 年 1 月 1 日对应的儒略历
const ll gg=400*365+97;//新历法400年的天数
ll b[14]={0,31,28,31,30,31,30,31,31,30,31,30,31};//不闰月每月天数
ll c[14]={0,31,29,31,30,31,30,31,31,30,31,30,31};//闰月每月天数
ll t,n;
ll day[gg+5],month[gg+5],year[gg+5];//每400年第 i 天所对应的日，月，年
ll check(ll y,ll m){//寻找 y 年对于的月份月数if(((y)%4==0&&(y)%100!=0)||((y)%400==0))return c[m];return b[m];
}
int main(){
//	freopen("julian3.in","r",stdin);
//	freopen("julian3.out","w",stdout);cin>>t;day[0]=1;month[0]=1;//记得赋初值!!!for(ll i=1;i<gg;i++){day[i]=day[i-1]+1;//每天多一天month[i]=month[i-1];//每天不一定多一月/一年year[i]=year[i-1];if(day[i]>check(year[i],month[i])){//判断一月是否结束month[i]++;day[i]=1;}if(month[i]>12){//判断一年是否结束year[i]++;month[i]=1;}}for(ll i=1;i<=t;i++){cin>>n;if(n<=N){ll y=n/(365*4+1)*4;//整4年的天数n%=(365*4+1);//不满4年的天数if(y+year[n]-4712<=0){//由于没有公元0年，那我们将公元前4713年向后平移1年，即4712cout<<day[n]<<' '<<month[n]<<' '<<4713-(y+year[n])<<" BC"<<'\n';//记得加 1}else{cout<<day[n]<<' '<<month[n]<<' '<<y+year[n]-4712<<'\n';//公元后无需加1，不信的话可以自己举一下。}}if(n>N){n-=N1200;n=n+10-3;//由公式可得ll t=n/gg*400+1200;//整400年的年数n=n%gg;//不满400年的天数cout<<day[n]<<' '<<month[n]<<' '<<t+year[n]<<'\n';//直接输出即可}}return 0;
}