题面太长不放
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; }
|