2020 儒略日 · 方案二分段整块跳

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 3163 字
按纪元整块跳跃，剩余不足一年再逐日收尾
2020
模拟
正文

// CSP-S 2020 复赛 T1 · 儒略日（方案二：分段整块跳 + 逐日收尾，满分）
// 原题：https://oj.yecheng.tv/p/CSPS2020A
// 题意：同方案一（Q ≤ 1e5，r ≤ 1e9，需满分）。
// 思路（整块跳跃）：
//   逐天模拟慢在"一天一天走"。改成按年/块跳：
//   1. 儒略历段（r < 2299161，即 1582-10-04 之前）：每 4 年一个周期，
//      天数 = 1461，周期内 3 平年 + 1 闰年。先按 4 年块整块减，再在
//      块内逐天收尾；
//   2. 格里高利段（r ≥ 2299161）：先扣掉 2299160 天落到 1582-10-15，
//      之后每 400 年 = 146097 天整块减（400 年 97 闰），再按 4 年块，
//      最后逐天收尾；
//   3. 注意 1582-10-15 是星期几无关紧要，只管天数映射。
//   每次询问 O(块数) = O(r / 1461) 仍可能慢 → 用整除直接求块数：
//   块数 = r / 周期天数，一次除法到位，剩余 r %= 周期天数再逐段收尾，
//   每询问 O(1) 级别（收尾最多几百年）。
// 复杂度：O(Q · 常数)。
// 易错点：
//   1. 2299161 = 1582-10-15 的儒略日编号（分界值要算准）；
//   2. 公元段用天文纪年（含 0 年），输出时 y ≤ 0 转 BC；
//   3. 整块跳后别忘了处理"块内闰年位置"（周期第一年是闰年起点）；
//   4. 月长表收尾阶段与方案一共用。
#include <cstdio>

int q;
long long r;
const int md[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool leapJulian(long long y) { return ((y % 4) + 4) % 4 == 0; }

int monthLenJ(long long y, int m) {
    if (m == 2 && leapJulian(y)) return 29;
    return md[m];
}

int monthLenG(long long y, int m) {
    if (m == 2 && ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0)) return 29;
    return md[m];
}

int main() {
    freopen("julian.in", "r", stdin);
    freopen("julian.out", "w", stdout);
    scanf("%d", &q);
    while (q--) {
        scanf("%lld", &r);
        long long y;
        int m, d;
        if (r < 2299161) {
            // 儒略历段：从 -4713(天文) 年 1 月 1 日起
            y = -4713;
            long long blocks = r / 1461;   // 每 4 年 1461 天
            y += blocks * 4;
            r %= 1461;
            m = 1;
            d = 1;
            // 块内按年跳
            while (true) {
                long long len = leapJulian(y) ? 366 : 365;
                if (r >= len) {
                    r -= len;
                    y++;
                } else break;
            }
            while (r >= monthLenJ(y, m)) {
                r -= monthLenJ(y, m);
                m++;
            }
            d = (int)r + 1;
        } else {
            // 格里高利段：r -= 2299161 → 0 = 1582-10-15
            r -= 2299161;
            y = 1582;
            m = 10;
            d = 15;
            long long blocks = r / 146097; // 每 400 年 146097 天
            y += blocks * 400;
            r %= 146097;
            // 按 4 年块（格里高利 4 年 = 1461 天，除非跨百不闰）
            while (true) {
                bool big = (y % 100 == 0); // 世纪年块长度不同，逐 4 年判
                long long len = 0;
                for (int i = 0; i < 4; i++) {
                    long long yy = y + i;
                    len += (yy % 4 == 0 && (yy % 100 != 0 || yy % 400 == 0)) ? 366 : 365;
                }
                if (r >= len) {
                    r -= len;
                    y += 4;
                } else break;
            }
            while (true) {
                long long len = monthLenG(y, m);
                if (r >= len) {
                    r -= len;
                    m++;
                    if (m > 12) { m = 1; y++; }
                } else break;
            }
            d = (int)r + 1;
        }
        if (y <= 0) printf("%d %d %lld BC\n", d, m, 1 - y);
        else printf("%d %d %lld\n", d, m, y);
    }
    return 0;
}
2020 儒略日 · 方案二 分段整块跳

正文

CSP-S 标程 · 复赛真题的其它内容

2020 儒略日 · 方案二分段整块跳
