题面太长不放

https://www.luogu.com.cn/problem/P7075

题解

如何优雅地在开考40分钟内完成此题?

首先最重要的一点:发现1600年之前的闰年规律都是每4年一次,而1600又正好是400的倍数,所以以1600作为分界线,分成1600年前后两种情况比较好处理

其次,发现0年不存在也不方便,所以把所有的负数年份+1,输出时再改回来

公元前4913年1月1日是第0天也不方便,所以把 r++

准备工作做好,现在来考虑怎么求解

(一)1600年及以前

如果$r<=M$,那么时间在1600年及以前($M$表示-4713到1600共有多少天)

发现-4713到1600只有6000多年,所以干脆把每一年的天数都算出来(然后求前缀和方便二分)

注意的点:

  1. 由于我们把所有的负数年份+1了,所以现在所有模4余0的年份都是闰年
  2. 1582年只有355天!!!

求出前缀和后(即-4713年到1600年及之前的某一年一共有多少天),就可以二分求出究竟是在哪一年的第几天,然后跳转到**(三)**

(二)1600年之后

如果$r>M$,那么时间在1600年之后,让$r$减去$M$

此时每400年为一个周期,400年一共经过了$36697+365303=146097$天

算出$p=\lfloor\dfrac{r}{146097}\rfloor$表示一共经过了多少个400年

$q=r\bmod 146097$表示剩余多少天

注意!如果$q=0$,为方便后续计算,要让$p$减去1,并将$q$设为$146097$

之后就同**(一)**一样,预处理出400年中每一年的天数和前缀和,就可以二分求出$q$究竟是在最后余下的不到400年中的哪一年,以及是这年的第几天

如果二分求得是最后400年中的第$k$年,那么答案年份就应该是$1600+400p+k$

然后跳转到**(三)**

(三)一年内的判断

现在我们已经确定了答案是哪一年,是这一年的第几天,只需要找出月份和日期即可

发现$Q\le 10^5$,其实可以算出这一年的12个月各有多少天,然后从一月开始枚举,就很容易算出是几月几日

注意前面给负数年份加了1,现在要减回来

注意事项:

  1. 1600年之前的闰年判定和1600年之后不同!注意区分
  2. 1582年的10月只有21天!
  3. 如果你得出的答案是1582年10月521日,给日期加上10!1582.10.51582.10.14不存在!

注意事项3成功导致我100pts -> 40pts /kk

写多几个函数一定会比全部挤在main函数中条理更清晰

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template <typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}

ll ttt, M = 5000; //M作为数组的偏移量,防止数组越界
ll n;
ll months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, nmonth[13];
ll Aday[10005], Bday[10005]; //A:1600之前; B:400年的周期
ll days400 = 146097;

void initrun() {
for (ll i = -4712; i <= 1600; i++) Aday[i+M] = 365;
for (ll i = -4712; i <= 1600; i += 4) {
Aday[i+M] = 366;
}
Aday[1582+M] = 355; //!!!
for (ll i = -4712; i <= 1600; i++) Aday[i+M] += Aday[i+M-1];

for (ll i = 1; i <= 400; i++) {
if ((i % 400 == 0) || (i % 4 == 0 && i % 100 != 0)) Bday[i] = Bday[i-1] + 366;
else Bday[i] = Bday[i-1] + 365;
}
}

void printans(ll y, ll m, ll d) {
if (y < 0) printf("%lld %lld %lld BC\n", d, m, -y);
else printf("%lld %lld %lld\n", d, m, y);
}

void inyear(ll y, ll d) { //y年的第d天
for (ll i = 1; i <= 12; i++) nmonth[i] = months[i];
if (y == 1582) { //in 1582
nmonth[10] = 21;
} else if (y <= 1600) { //before 1600
if (y % 4 == 0) nmonth[2] = 29;
} else { //after 1600
if ((y % 400 == 0) || (y % 4 == 0 && y % 100 != 0)) {
nmonth[2] = 29;
}
}
if (y <= 0) y--; //恢复负数年份
for (ll i = 1; i <= 12; i++) {
if (d <= nmonth[i]) {
if (y == 1582 && i == 10 && d >= 5) d += 10; //100pts->40pts
printans(y, i, d);
break;
} else {
d -= nmonth[i];
}
}
}

void solve1(ll x) { //before 1600
ll l = -4712, r = 1600, mid = 0, ans = 0;
while (l <= r) {
mid = (l + r) >> 1;
if (Aday[mid+M] >= x) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
inyear(ans, x - Aday[ans+M-1]);
}

void solve2(ll x) { //after 1600
ll p = x / days400;
ll q = x % days400;
if (!q) {
p--; q = days400;
}
ll l = 1, r = 400, mid = 0, ans = 0;
while (l <= r) {
mid = (l + r) >> 1;
if (Bday[mid] >= q) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
inyear(1600 + p * 400 + ans, q - Bday[ans-1]);
}

int main() {
read(ttt);
initrun();
while (ttt--) {
read(n); n++;
if (n <= Aday[1600+M]) { //before 1600
solve1(n);
} else { //after 1600
solve2(n - Aday[1600+M]);
}
}
return 0;
}

评论