题解 P7075 儒略日
ShuYuMo
2020-11-13 17:10:11
题目看似很多细节，但是没必要特殊考虑，特殊考虑可能需要浪费很多时间。
考虑如果从头开始一天一天的往后跳，假如跳 $10^7$ 天，如果能预处理得到 $10^7$ 内步的日期，如果询问 $10^7$ 天内的日期，可以 $O(1)$ 回答。
先暴力一天一天的往后跳，预处理出前 $10^7$ 天的日期，年份能到达 $22666$ 年，所有的特殊情况都可以通过预处理的方式算出来。
对于询问分成两类：
- 对于 $r_i \le 10^7$ 直接输出预处理好的日期
- 对于 $r_i > 10^7$ 二分年份是哪一年，这里的日期一定是**格里高利历**，判断闰年只有一种条件，相比于直接二分所有可能的年份，要好写很多很多，基本没有什么细节了。
代码算是比较短的了。
```cpp
#include <cstdio>
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int _ = 1e7 + 100;
const int LIM = 22666;
int Day[2][30] = { {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {-1, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} };
bool pd(int Y){
if(Y < 0) return Y % 4 == -1;
else if(Y <= 1582) return Y % 4 == 0;
else return (Y % 400 == 0) || (Y % 4 == 0 && Y % 100 != 0);
}
int CNTR(int Y){ //求 年份在[1, Y]之间，如果全部按照格里高利日历的闰年判断方法，得到的闰年数量。
int ans = 0;
ans += Y / 400;
ans += (Y / 4 - Y / 100);
return ans;
}
void next(int &Y, int &M, int &D){ // 往下增加一天，得到的日期。
if(Y <= -1){
D++; int md = Day[pd(Y)][M];
if(D > md) D = 1, M ++;
if(M > 12) M = 1, Y ++;
if(Y >= 0) Y = 1;
}
else {
D += (Y == 1582 && M == 10 && D == 4 ? 11 : 1);
int md = Day[pd(Y)][M];
if(D > md) D = 1, M ++;
if(M > 12) M = 1, Y ++;
}
}
struct Date{
int D, Y, M;
Date(int a, int b, int c) { Y = a; M = b; D = c; }
Date(){}
}A[_];
int check(int Y){ // 求出[LIM, Y]年之间有多少天。
int ALL_Y = Y - LIM; // 总共有多少年
int D = ((CNTR(Y) - CNTR(LIM))) * 366; // 闰年的数量 * 366
D += (ALL_Y - (CNTR(Y) - CNTR(LIM))) * 365; // 平年的数量 * 365
// 这里是一个前缀和，求出 [1, Y] 之间的闰年数量 - [1, LIM] 之间的闰年数量 就是[LIM, Y] 之间的闰年数量。
return D;
}
signed main(){ ios::sync_with_stdio(false);
int Y = -4713, M = 1, D = 1;
for(int i = 0; i <= 1e7 + 20; i++){ A[i] = Date(Y, M, D); next(Y, M, D); } // 预处理
int Q; cin >> Q;
while(Q--){
int R; cin >> R;
if(R <= (int)(1e7 + 11)) { printf("%lld %lld %lld", A[R].D, A[R].M, abs(A[R].Y)); if(A[R].Y < 0) puts(" BC"); else puts(""); }
else {
int res = R - (int)(1e7) - 11;
int l = LIM, r = 2e9, Y = l;
while(l < r){
int mid = (l + r) >> 1;
if(check(mid) >= res) r = mid, Y = mid;
else l = mid + 1;
}
res -= check(Y - 1);
int M = 1;
for(int i = 1; i <= 12; i++) {
int md = Day[pd(Y)][i];
if(res - md <= 0) { M = i; break; }
else res -= md;
} int D = res;
printf("%lld %lld %lld\n", D, M, Y);
}
}
return 0;
}
```