[CSP-S 2020] 儒略日 题解

鄙人第一次写题解，写的不好之处请见谅。

想要代码的，直接往下滑。

1. 题干

题干很长，要耐心读完。

题干大意

给定 $Q$ 个询问，对于第 $i$ 个询问，有儒略日 $r_{i}$，请输出该儒略日对应的公历日期。

关于公历

1. 儒略历（Julian calendar）

月份及日期对应如下：

月份	天数
1	31
2	28 / 29
3	31
4	30
5	31
6	30
7	31
8	31
9	30
10	31
11	30
12	31

闰年判断：满足年份为 $4$ 的倍数即为闰年。

2. 格里高利历（Gregorian calendar）

与儒略历的区别就是闰年的判断：

满足年份为 $4$ 的倍数同时满足非 $100$ 的倍数才是闰年。
或者满足年份为 $400$ 的倍数才是闰年。

3. 日期特判

1. 1582.10.4 的下一天是 1582.10.15
2. 公元 0 年不存在。

   公元前 1 年是闰年，公元前 5 年也是，以此类推。
   开始的公元前 4713 年也是闰年。

2. 解题

开始不要想着拿 $100$，先把你应该拿的分数拿了再说。

0. 模板

注意到结果会特别大，所以需要开 long long。

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
    
    return 0;
}

有 $Q$ 组询问，所以 solve() 函数走起！

#include <bits/stdc++.h>
#define int long long
using namespace std;
int q;
void solve() {
    
}
signed main() {
    cin >> q;
    while (q--) {
        solve();
    }
    return 0;
}

前置定义

int months[] = {29, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

months[i] 表示 $i$ 月的天数，$i = 0$ 表示闰年二月的天数。

bool is_leap_year(int year, bool is_gregorian) {
    int y = year;
    if (y < 0) {
        ++ y;
    }
    if (!is_gregorian) {
        if (y % 4 == 0) {
            return true;
        }
    } else {
        if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) {
            return true;
        }
    }
    return false;
}

判断是否为闰年。

is_gregorian 参数表示是否为格里高利历。

1. 按天模拟（暴力）

这个是最暴力的写法，也是肯定会超时的方法。

实测过 3 个点。

含义打在注释里面了。

void solve() {
    int r;
    cin >> r;
    // 后面会用
    int tr = r;
    // 开始的日期
    int year = -4713, month = 1, day = 1;
    // 是否为格里高利历
    bool gre = false;
    // 时间一天一天地过去
    for (int d = 1; d <= tr; d++) {
        ++ day;
        if (year == 1582 && month == 10 && (day > 4 && day < 15)) { // 1582 年 10 月删掉的 10 天
            day = 15; // 跳到 15 号
            gre = true; // 启用格里高利历
        }
        int m = month;
        int y = year;
        if (is_leap_year(y, gre) && month == 2) { // months[0] 表示闰年 2 月的天数
            m = 0;
        }
        if (day > months[m]) { // 进位
            day -= months[m];
            ++ month;
        }
        if (month > 12) { // 进位
            month -= 12;
            ++ year;
        }
        if (year == 0) { // 公元 0 年不存在
            ++ year;
        }
    }
    // 输出，其中年份为负表示公元前 xx 年，年份为正表示公元 xx 年
    if (year < 0) {
        printf("%lld %lld %lld BC\n", day, month, abs(year));
    } else {
        printf("%lld %lld %lld\n", day, month, abs(year));
    }
}

2. 优化：按年枚举

前面的代码不用删掉。

我们是在上一步的基础上叠加优化，所以留在那里即可。

while ((tr >= 365 && !is_leap_year(year, gre)) || (tr >= 366 && is_leap_year(year, gre))) { // 循环条件，确保还有足够的天数
    int y = year;
    tr -= 365; // 过去了一年
    if (is_leap_year(y, gre)) {
        -- tr; // 闰年多过一天
    }
    if (year == 1582 && !gre) { // 从 1582 - 1583 年，经过了 10 月，把 10 月少掉的 10 天补上来
        tr += 10;
        gre = true; // 启用格里高利历
    }
    ++ year; // 加一年
    if (year == 0) { // 公元 0 年不存在
        ++ year;
    }
}

实测过 6 个点。

void solve() {
    int r;
    cin >> r;
    int tr = r;
    int year = -4713, month = 1, day = 1;
    bool gre = false;
    while ((tr >= 365 && !is_leap_year(year, gre)) || (tr >= 366 && is_leap_year(year, gre))) {
        int y = year;
        tr -= 365;
        if (is_leap_year(y, gre)) {
            -- tr;
        }
        if (year == 1582 && !gre) {
            tr += 10;
            gre = true;
        }
        ++ year;
        if (year == 0) {
            ++ year;
        }
    }
    for (int d = 1; d <= tr; d++) {
        ++ day;
        if (year == 1582 && month == 10 && (day > 4 && day < 15)) {
            day = 15;
            gre = true;
        }
        int m = month;
        int y = year;
        if (is_leap_year(y, gre) && month == 2) {
            m = 0;
        }
        if (day > months[m]) {
            day -= months[m];
            ++ month;
        }
        if (month > 12) {
            month -= 12;
            ++ year;
        }
        if (year == 0) {
            ++ year;
        }
    }
    if (year < 0) {
        printf("%lld %lld %lld BC\n", day, month, abs(year));
    } else {
        printf("%lld %lld %lld\n", day, month, abs(year));
    }
}

2.5 关键日期

观察样例 2：

3
> 2000000
> 3000000
4000000

> 14 9 763
> 15 8 3501
12 7 6239

1582 年绝对在这之间！

通过二分，关键时间如下：

• $2299160$ = 1582.10.4
• $2299161$ = 1582.10.15

暴力的程序即可测试出来。

同时，可以得到：

• $2298884$ = 1582.1.1

3. 再次优化：四年（四百年）一组

除了一年，就只有四年一组的优化了。

1582.10.4 以前的四年总共有 1461 天（$365 \times 4 + 1 = 1461$），所以得到以下优化：

while (year <= 1580 && tr >= 1461) { // 1580 是闰年，我们只能止步于此
    tr -= 1461; // 减去四年
    bool is_minus = year < 0; // 是否是公元前
    year += 4; // 时间过去了四年
    if (year > 0 && is_minus) { // 四年的开始是公元前
        ++ year; // 公元 0 年需要跳过
    }
}

然后后面的代码帮你处理了不足四年的日期。

那 1582 年后的呢？

Python 闪亮登场！

def is_leap_year(year):
    if (year % 4 == 0 and year % 100 != 0) or year % 400 == 0:
        return True
    return False
days = 0
for i in range(1, 401):
    days += 365
    if is_leap_year(i):
        days += 1
print(days)

输出：

146097

格里高利历中四百年一共 146097 天。

于是，可以得到以下优化代码：

// 前置代码
if (r >= 2298884) {
    tr -= 2298884;
    year = 1582;
}
// 省略
// 如果天数足够到 1582 年，并且能到下一年……
if (r >= 2298884 && tr >= 355) {
    // 过去一年
    ++ year;
    tr -= 355; // 减去一年的天数 + 补回 10 天
    gre = true; // 启用格里高利历
    while (year <= 1584 && ((tr >= 365 && !is_leap_year(year, gre)) || (tr >= 366 && is_leap_year(year, gre)))) { // 以年份为单位把年份补到 1584 年
        tr -= 365;
        if (is_leap_year(year, gre)) {
            -- tr;
        }
        ++ year;
    }
    while (year <= 1600 && tr >= 1461) { // 按四年一组补到 1600 年。注：下一组是从 1601 - 2000 年。
        tr -= 1461;
        year += 4;
    }
    while (tr >= 146097) { // 400 年一组
        year += 400;
        tr -= 146097;
    }
}

实测过 9 个点。

void solve() {
    int r;
    cin >> r;
    int tr = r;
    int year = -4713, month = 1, day = 1;
    bool gre = false;
    if (r >= 2298884) {
        tr -= 2298884;
        year = 1582;
    }
    while (year <= 1580 && tr >= 1461) {
        tr -= 1461;
        bool is_minus = year < 0;
        year += 4;
        if (year > 0 && is_minus) {
            ++ year;
        }
    }
    if (r >= 2298884 && tr >= 355) {
        ++ year;
        tr -= 355;
        gre = true;
        while (year <= 1584 && ((tr >= 365 && !is_leap_year(year, gre)) || (tr >= 366 && is_leap_year(year, gre)))) {
            tr -= 365;
            if (is_leap_year(year, gre)) {
                -- tr;
            }
            ++ year;
        }
        while (year <= 1600 && tr >= 1461) {
            tr -= 1461;
            year += 4;
        }
        while (tr >= 146097) {
            year += 400;
            tr -= 146097;
        }
    }
    while ((tr >= 365 && !is_leap_year(year, gre)) || (tr >= 366 && is_leap_year(year, gre))) {
        int y = year;
        tr -= 365;
        if (is_leap_year(y, gre)) {
            -- tr;
        }
        if (year == 1582 && !gre) {
            tr += 10;
            gre = true;
        }
        ++ year;
        if (year == 0) {
            ++ year;
        }
    }
    for (int d = 1; d <= tr; d++) {
        ++ day;
        if (year == 1582 && month == 10 && (day > 4 && day < 15)) {
            day = 15;
            gre = true;
        }
        int m = month;
        int y = year;
        if (is_leap_year(y, gre) && month == 2) {
            m = 0;
        }
        if (day > months[m]) {
            day -= months[m];
            ++ month;
        }
        if (month > 12) {
            month -= 12;
            ++ year;
        }
        if (year == 0) {
            ++ year;
        }
    }
    if (year < 0) {
        printf("%lld %lld %lld BC\n", day, month, abs(year));
    } else {
        printf("%lld %lld %lld\n", day, month, abs(year));
    }
}

4. 最后的小细节

观察 julian/julian3.in（julian.zip）发现数字都很大。

那么怎么做呢？

while (tr >= 146097) { // 400 年一组
    year += 400;
    tr -= 146097;
}

这个，其实可以用 $O(1)$ 的做法做出来。

假设现在还剩下 tr 天，那么组数（一组 146097 天）就是 tr $\div 146097$。
那么剩下多少天呢？tr $\mod 146097$。

if (tr >= 146097) {
    year += 400 * (tr / 146097);
    tr %= 146097;
}

Good! 10 个全部过！

void solve() {
    int r;
    cin >> r;
    int tr = r;
    int year = -4713, month = 1, day = 1;
    bool gre = false;
    if (r >= 2298884) {
        tr -= 2298884;
        year = 1582;
    }
    while (year <= 1580 && tr >= 1461) {
        tr -= 1461;
        bool is_minus = year < 0;
        year += 4;
        if (year > 0 && is_minus) {
            ++ year;
        }
    }
    if (r >= 2298884 && tr >= 355) {
        ++ year;
        tr -= 355;
        gre = true;
        while (year <= 1584 && ((tr >= 365 && !is_leap_year(year, gre)) || (tr >= 366 && is_leap_year(year, gre)))) {
            tr -= 365;
            if (is_leap_year(year, gre)) {
                -- tr;
            }
            ++ year;
        }
        while (year <= 1600 && tr >= 1461) {
            tr -= 1461;
            year += 4;
        }
        if (tr >= 146097) {
            year += 400 * (tr / 146097);
            tr %= 146097;
        }
    }
    while ((tr >= 365 && !is_leap_year(year, gre)) || (tr >= 366 && is_leap_year(year, gre))) {
        int y = year;
        tr -= 365;
        if (is_leap_year(y, gre)) {
            -- tr;
        }
        if (year == 1582 && !gre) {
            tr += 10;
            gre = true;
        }
        ++ year;
        if (year == 0) {
            ++ year;
        }
    }
    for (int d = 1; d <= tr; d++) {
        ++ day;
        if (year == 1582 && month == 10 && (day > 4 && day < 15)) {
            day = 15;
            gre = true;
        }
        int m = month;
        int y = year;
        if (is_leap_year(y, gre) && month == 2) {
            m = 0;
        }
        if (day > months[m]) {
            day -= months[m];
            ++ month;
        }
        if (month > 12) {
            month -= 12;
            ++ year;
        }
        if (year == 0) {
            ++ year;
        }
    }
    if (year < 0) {
        printf("%lld %lld %lld BC\n", day, month, abs(year));
    } else {
        printf("%lld %lld %lld\n", day, month, abs(year));
    }
}

3. 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int q;
int months[] = {29, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool is_leap_year(int year, bool is_gregorian) {
    int y = year;
    if (y < 0) {
        ++ y;
    }
    if (!is_gregorian) {
        if (y % 4 == 0) {
            return true;
        }
    } else {
        if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) {
            return true;
        }
    }
    return false;
}
void solve() {
    int r;
    cin >> r;
    int tr = r;
    int year = -4713, month = 1, day = 1;
    bool gre = false;
    if (r >= 2298884) {
        tr -= 2298884;
        year = 1582;
    }
    while (year <= 1580 && tr >= 1461) {
        tr -= 1461;
        bool is_minus = year < 0;
        year += 4;
        if (year > 0 && is_minus) {
            ++ year;
        }
    }
    if (r >= 2298884 && tr >= 355) {
        ++ year;
        tr -= 355;
        gre = true;
        while (year <= 1584 && ((tr >= 365 && !is_leap_year(year, gre)) || (tr >= 366 && is_leap_year(year, gre)))) {
            tr -= 365;
            if (is_leap_year(year, gre)) {
                -- tr;
            }
            ++ year;
        }
        while (year <= 1600 && tr >= 1461) {
            tr -= 1461;
            year += 4;
        }
        if (tr >= 146097) {
            year += 400 * (tr / 146097);
            tr %= 146097;
        }
    }
    while ((tr >= 365 && !is_leap_year(year, gre)) || (tr >= 366 && is_leap_year(year, gre))) {
        int y = year;
        tr -= 365;
        if (is_leap_year(y, gre)) {
            -- tr;
        }
        if (year == 1582 && !gre) {
            tr += 10;
            gre = true;
        }
        ++ year;
        if (year == 0) {
            ++ year;
        }
    }
    for (int d = 1; d <= tr; d++) {
        ++ day;
        if (year == 1582 && month == 10 && (day > 4 && day < 15)) {
            day = 15;
            gre = true;
        }
        int m = month;
        int y = year;
        if (is_leap_year(y, gre) && month == 2) {
            m = 0;
        }
        if (day > months[m]) {
            day -= months[m];
            ++ month;
        }
        if (month > 12) {
            month -= 12;
            ++ year;
        }
        if (year == 0) {
            ++ year;
        }
    }
    if (year < 0) {
        printf("%lld %lld %lld BC\n", day, month, abs(year));
    } else {
        printf("%lld %lld %lld\n", day, month, abs(year));
    }
}
signed main() {
    cin >> q;
    while (q--) {
        solve();
    }
    return 0;
}

4. 彩蛋

• 冷知识：1582.10.15 到 2020.11.7（CSP-S 2020 比赛日期）正好 $160000$ 天。
  • 不信输入 2459161 试一下。