P7075儒略日

Mr_HY43205 · 2021-10-20 00:14:48 · 个人记录

P7075 [CSP-S2020] 儒略日

题意

有 Q 组询问，每组询问给出一个正整数儒略日，求其对应的公历日期。

儒略日：从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数。

公历日期计算：

1. 公元 1582 年 10 月 15 日及以后：格里高利历，即现行历法（当年份是 400 的倍数，或年份是 4 的倍数但不是 100 的倍数时，该年为闰年）。
2. 公元 1582 年 10 月 5 日至 1582 年 10 月 14 日：不存在。
3. 公元 1582 年 10 月 4 日及以前：儒略历（当年份为 4 的倍数时，该年为闰年）。
4. 公元零年不存在，公元前 1 年的下一年是公元 1 年。

数据范围：

关键词：模拟，二分

解题思路

10分：Q=1000,r_i\leq365

询问天数不超过 365 天，则日期就在公元前 4713 年内，可以直接通过循环枚举这一年内的月份和日期进行求解。具体操作可以将每个月的天数存入数组，判断目前的天数是否大于这个月的天数。如果是，则说明该日期不在这一个月内，可以将总天数减去当前月的天数，并继续枚举下一个月。否则，说明所求日期就在这一个月内，且日期就等于剩余的天数，此时可以直接输出日期。在下文中，我们把这种操作称为“按月枚举”。

时间复杂度为 O(Qr_i)。（常数约为 \dfrac{1}{30}，即枚举月份）

40分：Q=10000,r_i\leq3\times10^5

询问天数的范围不止一年了，此时需要考虑闰年和平年天数不同的问题。由于 r_i\leq3\times10^5，年份还在公元前，所以可以不用考虑更多情况，只需要判断每四年一次的闰年即可。如果是闰年，在按月枚举时，对应数组中 2 月的天数要加一天。

时间复杂度为 O(Qr_i)。

80分：Q=10^5,r_i\leq10^7

此时要考虑的情况就复杂了。10^7 的天数，既到达了公元后，又开始使用格里高利历，比之前的情况多不少。同时， O(Qr_i) 的时间复杂度已经不够了，需要进行优化。

首先，在枚举方法上，我们可以采用按年枚举的方法。和按月枚举的思路基本相同，也是判断目前的天数是否大于这一年的天数。如果是，说明日期不在这一年内，减去这一年的天数并继续。否则，就在这一年里进行按月枚举。

值得注意的是，有几个问题需要解决：

首先，公元前后的年份枚举形式不同，会导致实现不方便。我们可以在枚举年份的时候，将公元前的年份对应到负数，并用公元前 1 年补齐 0。也就是说，用 -x+1 来表示公元前 x 年。

其次，对于闰年的判断，涉及到两个不同的历法。于是，我们需要首先判断年份是否小于 1582。如果是，则只判断对 4 取模的结果即可。否则，就需要分别考察对 4,100,400 取模的结果。

还有一个问题在于 1582 年涉及到历法转换。此时，1582 年的天数要减 10，10 月的天数也要减 10，若日期落在 1582 年 10 月 4 日之后还需要特殊处理。

时间复杂度为 O(Qr_i)。（常数约为 \dfrac{1}{365}，即枚举年份）

100分：Q=10^5,\text{答案年份不超过}\ 10^9

由于年份达到 10^9，枚举年份的时间复杂度太高了。考虑到题目中的要求为给定儒略日求公历日期，而公历日期的年份与儒略日之间满足单调关系，可以考虑二分年份进行判断。每次考察某一年 1 月 1 日的儒略日，若结果小于 r_i，说明答案年份应该不小于此年份，反之亦然，由此进行二分。

按照刚才公元前取负的记录方法，年份的范围为 [-4712,10^9+1)。现在的主要问题在于如何对于一个给定的年份，求出其 1 月 1 日的儒略日。

其天数由几个部分组成：年数，闰年数以及是否在公元 1582 年之后。

年数的部分，直接将年数差乘上 365 即可。闰年数需要分两部分计算：一是每四年一闰，闰年数为 \left\lceil\dfrac{year+4712}{4}\right\rceil。二是当年份大于 1582 时，整百年带来的贡献，有 \left\lceil\dfrac{year-1600}{400}\right\rceil-\left\lceil\dfrac{year-1600}{100}\right\rceil。最终的儒略日需要加上闰年数。如果年份在公元 1582 年后，还需要在儒略日中减去 10。

计算出儒略日后，我们就可以对年份进行二分，并在二分得出的年份内进行按月枚举。注意在输出时要考虑公元前后的输出格式。同时要注意，答案年份达到 10^9，说明输入的 r_i 会至少达到 3.65\times10^{11}，需要开 long long。

时间复杂度为 O(Q\log U)，其中 U 为年份的值域范围。

本题完整代码如下：

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;
int Q;
ll ri;
int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

ll cal(ll year) {                                                   //对给定的年数，计算1月1日对应的儒略日
    ll cnt = (year + 4712 + 3) / 4;
    if (year >= 1600)
        cnt += (year - 1600 + 399) / 400 - (year - 1600 + 99) / 100;
    ll res = (year + 4712) * 365 + cnt;
    if (year > 1582) res -= 10;
    return res;
}

void count_date(ll day, ll year) {              //在年内进行按月枚举
    ll month;
    bool is_leap = false;
    if (year < 1600 && year % 4 == 0)
        is_leap = true;
    else if (year >= 1600 && (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)))
        is_leap = true;
    if (is_leap) days[2]++;
    if (year == 1582) days[10] -= 10;
    for (month = 1; month <= 12; month++) {
        if (day > days[month]) day -= days[month];
        else break;
    }
    if (year == 1582 && month == 10 && day >= 5) day += 10;
    if (year <= 0) cout << day << " " << month << " " << -year + 1 << " BC" << endl;
    else cout << day << " " << month << " " << year << endl;
    if (is_leap) days[2]--;
    if (year == 1582) days[10] += 10;
}

int main() {
    freopen("julian.in","r",stdin);
    freopen("julian.out","w",stdout);
    cin >> Q;
    while (Q--) {
        cin >> ri;
        ll l = -4712, r = 1000000001, res = 0;
        while (l < r - 1) {                                 //对年份进行二分，范围为[l,r)左闭右开区间
            ll m = (l + r) >> 1;
            res = cal(m);
            if (res <= ri) l = m;
            else r = m;
        }
        res = cal(l);
        count_date(ri - res + 1, l);
    }
    return 0;
}