题解：P7075 [CSP-S2020] 儒略日
2huk
·
·
题解
题意
特别的：
- 公元 1582 年 10 月 15 日（含）以后：与现在相同。
- 公元 1582 年 10 月 5 日（含）至 10 月 14 日（含）：不存在，这些日期被删除。
- 公元 1582 年 10 月 4 日（含）以前：年份是 $4$ 的倍数就是闰年。
- 公元零年并不存在，因此公元前 1 年、前 5 年、前 9 年、前 13 年……以此类推的年份应视为闰年。
## 做法
从公元前 4713 年 1 月 1 日到公元 1582 年 10 月 4 日，总共的天数不超过 $3 \times 10^6$。因此我们可以预处理。注意处理公元零年和闰年。
从公元 1582 年 10 月 15 日以后，注意到每 400 年都是一个循环。因此再预处理从公元 1582 年 10 月 15 日以后 400 年的日期与公元 1582 年 10 月 15 日的**偏移量**。查询时求 $r \bmod (365 \times 400 + 97)$ 即可。
```cpp
// Problem:
// P7075 [CSP-S2020] 儒略日
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7075
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2299160, M = 365 * 400 + 97;
struct Day {
int y, m, d;
Day() {}
Day(int a, int b, int c) {
y = a;
m = b;
d = c;
}
bool operator ==(const Day &h) const {
return y == h.y && m == h.m && d == h.d;
}
bool operator !=(const Day &h) const {
return y != h.y || m != h.m || d != h.d;
}
bool operator <(const Day &h) const {
return y < h.y || y == h.y && m < h.m || y == h.y && m == h.m && d < h.d;
}
}res[N + 114514], delta[M + 114514];
bool leap(int x) {
if (x > 1582) return x % 4 == 0 && x % 100 || x % 400 == 0;
return (x + (x < 0)) % 4 == 0;
}
const int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
Day add(Day t) {
if (t == Day(-1, 12, 31)) return Day(1, 1, 1);
if (t == Day(1582, 10, 4)) return Day(1582, 10, 15);
int y = t.y, m = t.m, d = t.d;
if (m == 12 && d == 31) return Day(y + 1, 1, 1);
d ++ ;
if (d > days[m] + (m == 2 && leap(y))) {
d = 1, m ++ ;
}
if (m > 12) {
m = 1, y ++ ;
}
return Day(y, m, d);
}
void initN() {
Day d = {-4713, 1, 1};
int cnt = 0;
while (d != Day(1582, 10, 15)) {
res[cnt ++ ] = d;
d = add(d);
}
}
void initM() {
Day d = {1582, 10, 15};
int cnt = 0;
while (cnt < M) {
delta[cnt ++ ] = Day(d.y - 1582, d.m, d.d);
d = add(d);
}
}
void print(Day t) {
cout << t.d << ' ' << t.m << ' ' << abs(t.y);
if (t.y < 0) cout << " BC";
cout << '\n';
}
signed main() {
initN();
initM();
int q;
cin >> q;
while (q -- ) {
int r;
cin >> r;
if (r <= N) print(res[r]);
else {
r -= N;
-- r;
// 1582.10.15 后的第 r 天（10.15 是第 0 天）
Day t = delta[r % M];
t.y += r / M * 400;
t.y += 1582;
print(t);
}
}
return 0;
}
```