P7075 [CSP-S2020] 儒略日_2020年1月1日的儒略日时间

P7075 [CSP-S2020] 儒略日

题目

题目描述

1. 为了简便计算，天文学家们使用儒略日（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$，表示一个儒略日。

输出格式

1. 对于每一个儒略日 $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

3
10
100
1000
1
2
3
4

输出 #1

11 1 4713 BC
10 4 4713 BC
27 9 4711 BC
1
2
3

输入 #2

3
2000000
3000000
4000000
1
2
3
4

输出 #2

14 9 763
15 8 3501
12 7 6239
1
2
3

输入 #3

见附件中的 julian/julian3.in
1

输出 #3

见附件中的 julian/julian3.ans
1

说明/提示

【数据范围】

测试点编号	$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$

思路 & 代码

80pts

考试的时候看题目太繁琐,就直接跳过了(虽然也耽误了半个小时).后来发现80pts还是比较容易的.少了80pts,但是避免了被这题炸裂心态.

其实看80pts时$r_i\le 10^7$.不难想到按$r$排序,直接一天一天模拟.

对于一个日期,我们只要求出它的下一天时什么时候就好.(我的做法的核心就只在next这一个函数)

struct date {
	int y , d , m;
};
inline date next(date d) {
	if(d.y == 1582 && d.m == 10 && d.d == 4){
		d.d = 15;
		return d;
	}
	
	bool run;
	if(d.y < 0)
		run = ((-d.y - 1) % 4 == 0);
	else if(d.y <= 1582)
		run = (d.y % 4 == 0);
	else
		run = (d.y % 4 == 0 && d.y % 100 != 0 || d.y % 400 == 0);
		
	++d.d;
	if(d.d > mon[run][d.m])
		++d.m , d.d = 1;
	if(d.m > 12)
		++d.y , d.m = 1;
	if(d.y == 0)
		d.y = 1;
	return d;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
//#pragma GCC optimized(2)
using namespace std;
const int Q = 100010;

int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = c - '0' + (re << 1) + (re << 3) , c = getchar();
	return negt ? -re : re;
}

const int mon[2][15] = {
	{0,31,28,31,30,31,30,31,31,30,31,30,31},
	{0,31,29,31,30,31,30,31,31,30,31,30,31}
};
struct date {
	int y , d , m;//year date month. y<0表示公元前
};
inline date next(date d) {
	if(d.y == 1582 && d.m == 10 && d.d == 4){
		d.d = 15;
		return d;
	}
	
	bool run;
	if(d.y < 0)
		run = ((-d.y - 1) % 4 == 0);
	else if(d.y <= 1582)
		run = (d.y % 4 == 0);
	else
		run = (d.y % 4 == 0 && d.y % 100 != 0 || d.y % 400 == 0);
		
	++d.d;
	if(d.d > mon[run][d.m])
		++d.m , d.d = 1;
	if(d.m > 12)
		++d.y , d.m = 1;
	if(d.y == 0)
		d.y = 1;
	return d;
}

struct query {
	int r , id;
} q[Q];
bool cmp(query a , query b) {
	return a.r < b.r;
}
int qnum;
date ans[Q];
signed main() {
	qnum = read();
	for(int i = 1 ; i <= qnum ; i++)
		q[i].r = read() , q[i].id = i;

	sort(q + 1 , q + qnum + 1 , cmp);

	int cnt = 0;
	date d;
	d.y = -4713 , d.m = 1 , d.d = 1;
	for(int i = 1 ; i <= qnum ; i++) {
		while(cnt < q[i].r)
			++cnt , d = next(d);
		ans[q[i].id] = d;
	}

	for(int i = 1 ; i <= qnum ; i++) {
		if(ans[i].y < 0) {
			printf("%d %d %d BC\n" , ans[i].d , ans[i].m , -ans[i].y);
		} else {
			printf("%d %d %d\n" , ans[i].d , ans[i].m , ans[i].y);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

100pts

考虑到1600年之后奇奇怪怪的规定就会变少,所以我们用2000.1.1作为基线,前面直接暴力,后面做出一些优化.

根据闰年的定义,我们以400年为一个周期(400年的天数总是固定的),算出400年中有97个闰年,即400年有$365\times 400+97$天(具体留给电脑算就好).

我们从时间基线开始,用$400\times 2^j$​做倍增(应该也可以$O(1)$​做,但是没必要,本人太弱没搞出来).让当前年数与目标年数之差不超过400,然后一年一年地和目标日期逼近,使日期只差不超过365天,最后按一天一天逼近即可.计算次数分别为$\log r,400,360$,乘上$q$,是在$10^8$​以内的,可以通过.

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
//#pragma GCC optimized(2)
using namespace std;
const int Q = 100010;
const int DayOf400Y = 365 * 400 + 97;
const int LogR = 30;

int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = c - '0' + (re << 1) + (re << 3) , c = getchar();
	return negt ? -re : re;
}

const int mon[2][15] = {
	{0,31,28,31,30,31,30,31,31,30,31,30,31},
	{0,31,29,31,30,31,30,31,31,30,31,30,31}
};
struct date {
	int y , d , m;
};
inline date next(date d) {
	if(d.y == 1582 && d.m == 10 && d.d == 4){
		d.d = 15;
		return d;
	}
	
	bool run;
	if(d.y < 0)
		run = ((-d.y - 1) % 4 == 0);
	else if(d.y <= 1582)
		run = (d.y % 4 == 0);
	else
		run = (d.y % 4 == 0 && d.y % 100 != 0 || d.y % 400 == 0);
		
	++d.d;
	if(d.d > mon[run][d.m])
		++d.m , d.d = 1;
	if(d.m > 12)
		++d.y , d.m = 1;
	if(d.y == 0)
		d.y = 1;
	return d;
}

struct query {
	int r , id;
} q[Q];
bool cmp(query a , query b) {
	return a.r < b.r;
}
int qnum;
date ans[Q];
signed main() {
	qnum = read();
	for(int i = 1 ; i <= qnum ; i++)
		q[i].r = read() , q[i].id = i;

	sort(q + 1 , q + qnum + 1 , cmp);

	int cnt = 0;
	date d;
	d.y = -4713 , d.m = 1 , d.d = 1;
	
	int i;
	for(i = 1 ; d.y < 2000 && i <= qnum ;) {
		while(cnt < q[i].r && d.y < 2000)
			++cnt , d = next(d);
		if(d.y < 2000)
			ans[q[i].id] = d , ++i;
	}
	//此时d=2020年1月1日,cnt为这天的儒略日
	int cnt_;//当前儒略日
	date d1;//当前格里高利历日期
	for( ; i <= qnum ; i++) {
		cnt_ = cnt , d1 = d;//从时间基线开始
		
		for(int j = LogR ; j >= 0 ; j--)//400年*2^j 倍增
			if(cnt_ + (DayOf400Y << j) <= q[i].r)
				cnt_ += (DayOf400Y << j) , d1.y += (400ll << j);
		
		while(cnt_ + 366 <= q[i].r) {//年份逼近
			if(d1.y % 4 == 0 && d1.y % 100 != 0 || d1.y % 400 == 0)
				cnt_ += 366;
			else
				cnt_ += 365;
			d1.y += 1;
		}
		while(cnt_ < q[i].r)//日期逼近
			++cnt_ , d1 = next(d1);
		ans[q[i].id] = d1;
	}

	for(int i = 1 ; i <= qnum ; i++) {
		if(ans[i].y < 0) {
			printf("%d %d %d BC\n" , ans[i].d , ans[i].m , -ans[i].y);
		} else {
			printf("%d %d %d\n" , ans[i].d , ans[i].m , ans[i].y);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109