题面

题目描述

为了简便计算，天文学家们使用儒略日（Julian day）来表达时间。所谓儒略日，其定义为从公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数，不满一天者用小数表达。若利用这一天文学历法，则每一个时刻都将被均匀的映射到数轴上，从而得以很方便的计算它们的差值。

现在，给定一个不含小数部分的儒略日，请你帮忙计算出该儒略日（一定是某一天的中午 12 点）所对应的公历日期。

我们现行的公历为格里高利历（Gregorian calendar），它是在公元 1582 年由教皇格里高利十三世在原有的儒略历（Julian calendar）的基础上修改得到的（注：儒略历与儒略日并无直接关系）。具体而言，现行的公历日期按照以下规则计算：

公元 1582 年 10 月 15 日（含）以后：适用格里高利历，每年一月 $31$ 天、二月 $28$ 天或 $29$ 天、三月 $31$ 天、四月 $30$ 天、五月 $31$ 天、六月 $30$ 天、七月 $31$ 天、八月 $31$ 天、九月 $30$ 天、十月 $31$ 天、十一月 $30$ 天、十二月 $31$ 天。其中，闰年的二月为 $29$ 天，平年为 $28$ 天。当年份是 $400$ 的倍数，或日期年份是 $4$ 的倍数但不是 $100$ 的倍数时，该年为闰年。
公元 1582 年 10 月 5 日（含）至 10 月 14 日（含）：不存在，这些日期被删除，该年 10 月 4 日之后为 10 月 15 日。
公元 1582 年 10 月 4 日（含）以前：适用儒略历，每月天数与格里高利历相同，但只要年份是 $4$ 的倍数就是闰年。
尽管儒略历于公元前 45 年才开始实行，且初期经过若干次调整，但今天人类习惯于按照儒略历最终的规则反推一切 1582 年 10 月 4 日之前的时间。注意，公元零年并不存在，即公元前 1 年的下一年是公元 1 年。因此公元前 1 年、前 5 年、前 9 年、前 13 年……以此类推的年份应视为闰年。

输入格式

第一行一个整数 $Q$ ，表示询问的组数。
接下来 $Q$ 行，每行一个非负整数 $r_i$ ，表示一个儒略日。

输出格式

对于每一个儒略日 $r_i$ ，输出一行表示日期的字符串 $s_i$ 。共计 $Q$ 行。 $s_i$ 的格式如下：

若年份为公元后，输出格式为 Day Month Year。其中日（Day）、月（Month）、年（Year）均不含前导零，中间用一个空格隔开。例如：公元
2020 年 11 月 7 日正午 12 点，输出为 7 11 2020。
若年份为公元前，输出格式为 Day Month Year BC。其中年（Year）输出该年份的数值，其余与公元后相同。例如：公元前 841 年 2 月 1 日正午 12
点，输出为 1 2 841 BC。

样例 #1

样例输入 #1

样例输出 #1

11 1 4713 BC
10 4 4713 BC
27 9 4711 BC

样例 #2

样例输入 #2

样例输出 #2

14 9 763
15 8 3501
12 7 6239

样例 #3

样例输入 #3

见附件中的 julian/julian3.in

样例输出 #3

见附件中的 julian/julian3.ans

提示

【数据范围】

测试点编号	$Q =$	$r_i \le$
$1$	$1000$	$365$
$2$	$1000$	$10^4$
$3$	$1000$	$10^5$
$4$	$10000$	$3\times 10^5$
$5$	$10000$	$2.5\times 10^6$
$6$	$10^5$	$2.5\times 10^6$
$7$	$10^5$	$5\times 10^6$
$8$	$10^5$	$10^7$
$9$	$10^5$	$10^9$
$10$	$10^5$	年份答案不超过 $10^9$

思路

没有思路，大模拟。

时间断点：

不存在的公元 0 年。
1582.10.5 ~ 1582.10.14
1583.1.1 ~ 1601.1.1

处理好边界问题分类讨论即可，复杂度为 $O(365q)$

做的时候先打了个暴力，方便找边界的值，一起附上。

坑点：

过了零天应当还在今年。
剩余要经过的天数检查下是否为负数。
while(x--) 后， $x$ 的值为 -1
询问值记得开 long long

代码

暴力

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int D[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int year, month, day;

bool isr()
{
    if(year < 1582)
    {
        if(year < 0)
        {
            if((-year - 1) % 4 == 0)
                return true;
        } 
        else if(year % 4 == 0) return true;
    }
    else // G
    {
        if(year % 400 == 0 || (year % 4 == 0 && year % 100 != 0))
            return true;
    }
    return false;
}

int main()
{
    // freopen("E:\\下载\\julian\\julian\\ julian3.in", "r", stdin);
    int t;
    scanf("%d", &t);
    while(t--)
    {
        LL r;
        year = -4713, month = 1, day = 1;
        scanf("%lld", &r);
        if(r >= 2299161)
        {
            r -= 2299161;
            year = 1582;
            month = 10;
            day = 15;
        }
        else if(r >= 1721424)
        {
            r -= 1721424;
            year = month = day = 1;
        }
        while(r--)
        {
            int permon = D[month];
            if(isr() && month == 2) // G 历
            {
                permon = 29;
            }
            if(day == permon)
            {
                if(month == 12)
                {
                    if(year != -1)
                    {
                        year++;
                    }
                    else year = 1;
                    month = 1;
                }
                else
                {
                    month++;
                }
                day = 1;
            }
            else day++;
            if(year == 1582 && month == 10 && day == 5)
            {
                day = 15;
            }
        }
        if(year < 0)
        {
            printf("%d %d %d BC\n", day, month, -year);
        }
        else
        {
            printf("%d %d %d\n", day, month, year);
        }
    }
    return 0;
}

原屎山

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int YEAR = -4713;
const int MONTH = 1;
const int DAY = 1;
const int D[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 年对应天的前缀和
int gy[405]; // gregorian
int ggy[40];
int jy[405]; // julian
int year = YEAR, month = MONTH, day = DAY;
// 天对应着多少年
unordered_map<int, int> mpg;
unordered_map<int, int> mpj;
unordered_map<int, int> mpgg;

inline LL read()
{
    LL x = 0, y = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-') y = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar();
    }
    return x * y;
}
void init()
{
    for(int i = 1; i <= 400; i++)
    {
        if(i % 4 == 0) jy[i] = jy[i - 1] + 366;
        else jy[i] = jy[i - 1] + 365;
        if(i % 400 == 0 || (i % 4 == 0 && i % 100 != 0)) gy[i] = gy[i - 1] + 366;
        else gy[i] = gy[i - 1] + 365;
        // cout << gy[i] << ' ' << jy[i] << endl;
    }
    for(int i = 1; i <= 18; i++) //[383, 400]
    {
        int x = i + 1582;
        if(x % 400 == 0 || (x % 4 == 0 && x % 100 != 0))
        {
            ggy[i] = ggy[i - 1] + 366;
        }
        else ggy[i] = ggy[i - 1] + 365;
    }
    for(int i = 1; i <= 400; i++)
    {
        // cout << jy[i] - jy[i - 1] << endl;
        for(int j = 1; j <= jy[i] - jy[i - 1]; j++)
        {
            mpj[j + jy[i - 1]] = i;
        }
    }
    for(int i = 1; i <= 400; i++)
    {
        // cout << gy[i] - gy[i - 1] << endl;
        for(int j = 1; j <= gy[i] - gy[i - 1]; j++)
        {
            mpg[j + gy[i - 1]] = i;
        }
    }
    for(int i = 1; i <= 18; i++)
    {
        for(int j = 1; j <= ggy[i] - ggy[i - 1]; j++)
        {
            mpgg[j + ggy[i - 1]] = i;
        }
    }
    // cout << ggy[10] << endl;
    mpj[0] = 1; // 
    mpg[0] = 1; //
    mpgg[0] = 1;
    // cout << gy[400] << endl;
    // cout << jy[400] << endl;
}
bool isr()
{
    if(year < 1582)
    {
        if(year < 0)
        {
            if((-year - 1) % 4 == 0)
                return true;
        } 
        else if(year % 4 == 0) return true;
    }
    else // G
    {
        if(year % 400 == 0 || (year % 4 == 0 && year % 100 != 0))
            return true;
    }
    return false;
}
void get(LL x)
{
    while(x)
    {
        x--;
        int permon = D[month];
        if(isr() && month == 2) // G 历
        {
            permon = 29;
        }
        if(day == permon)
        {
            if(month == 12)
            {
                if(year != -1)
                {
                    year++;
                    if(year == 1600) break;
                }
                else year = 1;
                month = 1;
            }
            else
            {
                month++;
            }
            day = 1;
        }
        else day++;
        if(year == 1582 && month == 10 && day == 5)
        {
            day = 15;
        }
    }
    if(year < 0)
    {
        printf("%d %d %d BC\n", day, month, -year);
    }
    else
    {
        printf("%d %d %d\n", day, month, year);
    }
    return;
}
void solve2(LL x)
{
// 1582 ~ 1601.1.1
    while(x)
    {
        x--;
        int permon = D[month];
        if(isr() && month == 2) // G 历
        {
            permon = 29;
        }
        if(day == permon)
        {
            if(month == 12)
            {
                if(year != -1)
                {
                    year++;
                }
                else year = 1;
                month = 1;
            }
            else
            {
                month++;
            }
            day = 1;
        }
        else day++;
        if(year == 1582 && month == 10 && day == 5)
        {
            day = 15;
        }
        if(year == 1583)
        {
            // cout << "Yes" << endl;
            break;
        }
    }
    // cout << x << endl;
// 1583.1.1 ~ 1601.1.1
    if(x < 6575) // 到不了 1601
    {
        year += mpgg[x] - 1;
        // cout << mpgg[x] - 1 << endl;
        x -= ggy[mpgg[x] - 1];
        // cout << x << endl; // 多了一个
        return get(x);
    }
    else // 1583.1.1 -> 1601.1.1
    {
        x -= gy[400] - gy[382];
        year = 1601;
    }
// ------
    // cout << gy[400] - gy[382] << endl;
    year += x / gy[400] * 400;
    x %= gy[400];
    // 能处于之后第 can 年，所以跳到 can - 1
    year += mpg[x] - 1;
    x -= gy[mpg[x] - 1];
    return get(x);
}
void solve(LL x)
{
    year = YEAR, month = MONTH, day = DAY;
    if(x >= 2299161) // 从 G 历发行开始
    {
        x -= 2299161;
        year = 1582;
        month = 10;
        day = 15;
        return solve2(x);
    }
    else if(x >= 1721424) // 从公元 1.1.1 开始
    {
        x -= 1721424;
        year = month = day = 1;
    }
    else // 走不出公元前的
    {
        if(x <= 366) return get(x);
        else
        {
            x -= 366;
            year++;
        }
        year += x / jy[400] * 400;
        x %= jy[400];
        // cout << x << endl;
        int can = mpj[x];
        year += can - 1;
        x -= jy[can - 1];
        // cout << can << endl;
        // cout << year << endl;
        // cout << x << endl;
        return get(x);
    }
    if(x <= 365 || (isr() && x == 366)) // 还剩一年以内暴力处理
    {
        return get(x);
    }
    // 剩下的，要么就是 1.1.1 ~ 1582.10.4 要么就是 1582.10.15 ~ inf
    // 变成闰整年开始 400 年的跳
    if(year == 1)
    {
        year++;
        x -= 365;
    }
    while((year - 1) % 4 != 0)
    {
        if(x <= 365 || (isr() && x == 366)) // 还剩一年以内暴力处理
        {
            return get(x);
        }
        if(isr()) x -= 366;
        else x -= 365;
        year++;
    }
    int can = x / jy[400] * 400 + mpj[x % jy[400]] - 1;
    if(year + can < 1582)
    {
        year += can;
        x %= jy[400];
        x -= jy[mpj[x] - 1];
        return get(x);
    }
    // 如果能到 1582 年的话
    x -= (1200 - year + 1) / 4 * jy[4];
    // cout << year << ' ' << month << ' ' << day << endl;
    // cout << x << endl;
    x -= jy[381];
    year = 1582; // 1201 + 381
    // cout << x << endl;
    // if(x <= 365 || (isr() && x == 366)) // 还剩一年以内暴力处理
    // {
    //     // cout << 'Y' << endl;
    //     return get(x);
    // }
    // cout << x << endl;
// 达到 1600.1.1 此时正式为 G 历
// 以下为 G 历
    // cout << x << endl;
    // cout << "---" << endl;
// 可以开始跳了
    // if(x <= 365 || (isr() && x == 366)) // 还剩一年以内暴力处理
    // {
    //     cout << 'Y' << endl;
    //     return get(x);
    // }
    return solve2(x);
}

// geligaoli: (x % 400 == 0 || (x % 4 == 0 && x % 100 != 0))
// rulue: (x < 0 ? x + 1 : x) % 4 == 0)

int main()
{
    // freopen("E:\\下载\\julian\\julian\\julian3.in", "r", stdin);
    // freopen("E:\\下载\\julian\\julian\\julian3.out", "w", stdout);
    init();
    int q;
    scanf("%d", &q);
    while(q--)
    {
        LL r;
        r = read();
        year = YEAR, month = MONTH, day = DAY;
        solve(r);
        // get(r);
    }
    return 0;
}

舒适版

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int YEAR = -4713;
const int MONTH = 1;
const int DAY = 1;
const int D[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

// 年对应天的前缀和
int gy[405]; // gregorian
int ggy[40];
int jy[405]; // julian
int year = YEAR, month = MONTH, day = DAY;
// 天对应着多少年
unordered_map<int, int> mpg;
unordered_map<int, int> mpj;
unordered_map<int, int> mpgg;

inline LL read()
{
    LL x = 0, y = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-') y = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar();
    }
    return x * y;
}
void init()
{
    for(int i = 1; i <= 400; i++)
    {
        if(i % 4 == 0) jy[i] = jy[i - 1] + 366;
        else jy[i] = jy[i - 1] + 365;
        if(i % 400 == 0 || (i % 4 == 0 && i % 100 != 0)) gy[i] = gy[i - 1] + 366;
        else gy[i] = gy[i - 1] + 365;
    }
    for(int i = 1; i <= 18; i++) //[383, 400]
    {
        int x = i + 1582;
        if(x % 400 == 0 || (x % 4 == 0 && x % 100 != 0))
        {
            ggy[i] = ggy[i - 1] + 366;
        }
        else ggy[i] = ggy[i - 1] + 365;
    }
    for(int i = 1; i <= 400; i++)
    {
        for(int j = 1; j <= jy[i] - jy[i - 1]; j++)
        {
            mpj[j + jy[i - 1]] = i;
        }
    }
    for(int i = 1; i <= 400; i++)
    {
        for(int j = 1; j <= gy[i] - gy[i - 1]; j++)
        {
            mpg[j + gy[i - 1]] = i;
        }
    }
    for(int i = 1; i <= 18; i++)
    {
        for(int j = 1; j <= ggy[i] - ggy[i - 1]; j++)
        {
            mpgg[j + ggy[i - 1]] = i;
        }
    }
    mpj[0] = 1; // 
    mpg[0] = 1; //
    mpgg[0] = 1;
}
bool isr()
{
    if(year < 1582)
    {
        if(year < 0)
        {
            if((-year - 1) % 4 == 0)
                return true;
        } 
        else if(year % 4 == 0) return true;
    }
    else // G
    {
        if(year % 400 == 0 || (year % 4 == 0 && year % 100 != 0))
            return true;
    }
    return false;
}
void get(LL x)
{
    while(x)
    {
        x--;
        int permon = D[month];
        if(isr() && month == 2) // G 历
        {
            permon = 29;
        }
        if(day == permon)
        {
            if(month == 12)
            {
                if(year != -1)
                {
                    year++;
                    if(year == 1600) break;
                }
                else year = 1;
                month = 1;
            }
            else
            {
                month++;
            }
            day = 1;
        }
        else day++;
        if(year == 1582 && month == 10 && day == 5)
        {
            day = 15;
        }
    }
    if(year < 0)
    {
        printf("%d %d %d BC\n", day, month, -year);
    }
    else
    {
        printf("%d %d %d\n", day, month, year);
    }
    return;
}
void solve2(LL x)
{
// 1582 ~ 1601.1.1
    while(x)
    {
        x--;
        int permon = D[month];
        if(isr() && month == 2) // G 历
        {
            permon = 29;
        }
        if(day == permon)
        {
            if(month == 12)
            {
                if(year != -1)
                {
                    year++;
                }
                else year = 1;
                month = 1;
            }
            else
            {
                month++;
            }
            day = 1;
        }
        else day++;
        if(year == 1582 && month == 10 && day == 5)
        {
            day = 15;
        }
        if(year == 1583)
        {
            break;
        }
    }
// 1583.1.1 ~ 1601.1.1
    if(x < 6575) // 到不了 1601
    {
        year += mpgg[x] - 1;
        x -= ggy[mpgg[x] - 1];
        return get(x);
    }
    else // 1583.1.1 -> 1601.1.1
    {
        x -= gy[400] - gy[382];
        year = 1601;
    }
    year += x / gy[400] * 400;
    x %= gy[400];
    // 能处于之后第 can 年，所以跳到 can - 1
    year += mpg[x] - 1;
    x -= gy[mpg[x] - 1];
    return get(x);
}
void solve(LL x)
{
    year = YEAR, month = MONTH, day = DAY;
    if(x >= 2299161) // 从 G 历发行开始
    {
        x -= 2299161;
        year = 1582;
        month = 10;
        day = 15;
        return solve2(x);
    }
    else if(x >= 1721424) // 从公元 1.1.1 开始
    {
        x -= 1721424;
        year = month = day = 1;
    }
    else // 走不出公元前的
    {
        if(x <= 366) return get(x);
        else
        {
            x -= 366;
            year++;
        }
        year += x / jy[400] * 400;
        x %= jy[400];
        int can = mpj[x];
        year += can - 1;
        x -= jy[can - 1];
        return get(x);
    }
    if(x <= 365 || (isr() && x == 366)) // 还剩一年以内暴力处理
    {
        return get(x);
    }
    // 剩下的，要么就是 1.1.1 ~ 1582.10.4 要么就是 1582.10.15 ~ inf
    // 变成闰整年开始 400 年的跳
    if(year == 1)
    {
        year++;
        x -= 365;
    }
    while((year - 1) % 4 != 0)
    {
        if(x <= 365 || (isr() && x == 366)) // 还剩一年以内暴力处理
        {
            return get(x);
        }
        if(isr()) x -= 366;
        else x -= 365;
        year++;
    }
    int can = x / jy[400] * 400 + mpj[x % jy[400]] - 1;
    if(year + can < 1582)
    {
        year += can;
        x %= jy[400];
        x -= jy[mpj[x] - 1];
        return get(x);
    }
    // 如果能到 1582 年的话
    x -= (1200 - year + 1) / 4 * jy[4];
    x -= jy[381];
    year = 1582; // 1201 + 381
    return solve2(x);
}

int main()
{
    init();
    int q;
    scanf("%d", &q);
    while(q--)
    {
        LL r;
        r = read();
        year = YEAR, month = MONTH, day = DAY;
        solve(r);
    }
    return 0;
}

2023-10-18 19:42:47 # OI # Problem #模拟