题面太长不放
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了，所以现在所有模4余0的年份都是闰年
- 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，现在要减回来
注意事项：
- 1600年之前的闰年判定和1600年之后不同！注意区分
- 1582年的10月只有21天！
- 如果你得出的答案是1582年10月5
21日，给日期加上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;
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];
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) {
for (ll i = 1; i <= 12; i++) nmonth[i] = months[i];
if (y == 1582) {
nmonth[10] = 21;
} else if (y <= 1600) {
if (y % 4 == 0) nmonth[2] = 29;
} else {
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;
printans(y, i, d);
break;
} else {
d -= nmonth[i];
}
}
}
void solve1(ll x) {
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) {
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]) {
solve1(n);
} else {
solve2(n - Aday[1600+M]);
}
}
return 0;
}
|
