囧仙 的博客

囧仙 的博客

题解 P7075 【儒略日】

posted on 2020-11-07 22:37:33 | under 题解 |

$\stackrel{\text{废话}}{\textbf{前言}}$

  • 这条题目成功加冕成为新一代毒瘤题我是没想到的。但 $\frak{u1s1}$ ,个人感觉这题不是很难,主要考的选手的细心程度。

  • 个人总结,只要不贪,这题还是挺容易做的。

题解

让我们首先解决一些题面中给出的特殊情况。

  • 起始时间为公元前 $4713$ 年 $1$ 月 $1$ 日。

  • 公元 $1582$ 年 $10$ 月 $4$ 日以前,当一个年份被四整除时为闰年。但是如果一个年份在公元前,则应当将这个年份减去 $1$ 后进行闰年判定。

  • 公元 $1582$ 年 $10$ 月 $5$ 日至 $10$ 月 $14$ 日被删除。

  • 公元 $1582$ 年 $10$ 月 $15$ 日以后,一个年份为闰年,当且仅当它被四百整除或者能被四整除但不能被一百整除。

  • 公元前一年的下一年,就是公元元年。

让我们先把闰年判定写出来。为了区分公元前后,我们用数字的正负进行区分。

bool chk(i64 y){
    if(y<=1582ll){
        if(y<0ll) y=-y-1ll; return y%4ll==0ll;
    }
    return (y%400ll==0ll)||(y%4ll==0ll&&y%100ll!=0ll);
}

题目给了相当多的信息,尤其是非常多的时段分类……但是,如果你仔细思考时段的长度,你能发现,

$$\textbf{4713.1.1 BC 至 1582.10.15 一共不超过 2.5}\boldsymbol{\times 10^6 }\textbf{天}$$

所以,我们能非常简单的写出这样一份代码,直接枚举这所有天的情况。

up(1,2305447,i){
    Y[i]=Y[i-1],M[i]=M[i-1],D[i]=D[i-1]+1;
    if(M[i]==12ll&&D[i]==32ll){
        if(Y[i]==-1) Y[i]=1; else ++Y[i];
        M[i]=1,D[i]=1;
    } else if(Y[i]==1582ll&&M[i]==10ll&&D[i]==5ll){
        Y[i]=1582ll,M[i]=10ll,D[i]=15ll;
    } else if(M[i]==2ll&&chk(Y[i])&&D[i]==29ll){
        continue;
    } else if(D[i]>MD[M[i]]) ++M[i],D[i]=1;
}
//其中Yi,Mi,Di分别为第i天的年份、月份、日数。
//chk(Yi) 是检查Yi年是否是闰年。
  • 经过一些暴力计算,我们能发现, $1600.1.1$ 的儒略日是 $2305448$ 。

好了,我们已经砍掉这题一半的难度了。下面考虑 $1600$ 年之后的事情。

要注意的是,从天数推日期总是比从日期推天数难

这里启发我们二分年份,计算它和 $1600.1.1$ 的日期之差。(为什么是差值?因为差值可以忽略掉一些可能导致的错误,因为两个错误相减后会互相消去,可以大大提升调对的概率)。月份和日期都可以直接枚举。这题就做完了。

//计算绝对日期
#define f(x) ((x)/4-(x)/100+(x)/400)
i64 clc(i64 y,i64 m,i64 d){
    return 365ll*(y-1ll)+f(y-1ll)+((chk(y)&&m>=3ll)?1ll:0ll)+S[m-1ll]+d;
//这部分并不需要非常严格,因为我们只需要计算日期和1600.1.1的差值。
}

//主程序片段
dn(qread(),1,Q){
    i64 t=qread(); if(t<=2305447ll){
        i64 y=Y[t],m=M[t],d=D[t];   //直接从表中获取答案
        if(y<0) printf("%lld %lld %lld BC\n",d,m,-y);   //公元前
        else    printf("%lld %lld %lld\n",d,m, y);      //公元后
    } else {
        t-=2305448ll; i64 y=0,m=1,d=1;
        dn(30,0,i){ //二分
            if(clc(y|(1<<i),m,d)-clc(1600,1,1)<=t) y|=1<<i;
        }
        up(1,12,i) if(clc(y,i,d)-clc(1600,1,1)<=t) m=i; //枚举月
        up(1,31,i) if(clc(y,m,i)-clc(1600,1,1)<=t) d=i; //枚举日
        printf("%lld %lld %lld\n",d,m,y);
    }
}

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef unsigned int u32;
typedef long long    i64;
typedef unsigned long long u64;
i64 qread(){
    i64 r=0,w=1,c=0;
    for(c=getchar();!isdigit(c);c=getchar()) w=(c=='-'?-1:1); r=c-'0';
    for(c=getchar(); isdigit(c);c=getchar()) r=r*10+c-'0';
    return r*w;
}
const int MD[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
const int MAXN =2400000+3;
int Y[MAXN],M[MAXN],D[MAXN],S[13];
bool chk(i64 y){
    if(y<=1582ll){
        if(y<0ll) y=-y-1ll; return y%4ll==0ll;
    }
    return (y%400ll==0ll)||(y%4ll==0ll&&y%100ll!=0ll);
}
#define f(x) ((x)/4-(x)/100+(x)/400)
i64 clc(i64 y,i64 m,i64 d){
    return 365ll*(y-1ll)+f(y-1ll)+((chk(y)&&m>=3ll)?1ll:0ll)+S[m-1ll]+d;
}
int main(){
    freopen("julian.in","r",stdin);
    freopen("julian.out","w",stdout);
    Y[0]=-4713ll,M[0]=1ll,D[0]=1ll; up(1,12,i) S[i]=S[i-1]+MD[i];
    up(1,2305447,i){
        Y[i]=Y[i-1],M[i]=M[i-1],D[i]=D[i-1]+1;
        if(M[i]==12ll&&D[i]==32ll){
            if(Y[i]==-1) Y[i]=1; else ++Y[i];
            M[i]=1,D[i]=1;
        } else if(Y[i]==1582ll&&M[i]==10ll&&D[i]==5ll){
            Y[i]=1582ll,M[i]=10ll,D[i]=15ll;
        } else if(M[i]==2ll&&chk(Y[i])&&D[i]==29ll){
            continue;
        } else if(D[i]>MD[M[i]]) ++M[i],D[i]=1;
    }
    dn(qread(),1,Q){
        i64 t=qread(); if(t<=2305447ll){
            i64 y=Y[t],m=M[t],d=D[t];
            if(y<0) printf("%lld %lld %lld BC\n",d,m,-y);
            else    printf("%lld %lld %lld\n",d,m, y);
        } else {
            t-=2305448ll; i64 y=0,m=1,d=1;
            dn(30,0,i){
                if(clc(y|(1<<i),m,d)-clc(1600,1,1)<=t) y|=1<<i;
            }
            up(1,12,i) if(clc(y,i,d)-clc(1600,1,1)<=t) m=i;
            up(1,31,i) if(clc(y,m,i)-clc(1600,1,1)<=t) d=i;
            printf("%lld %lld %lld\n",d,m,y);
        }
    }
    return 0;
}
//这是赛时代码,马蜂可能比较丑,请见谅。