题解 P7075 【儒略日（洛谷民间数据）】

· · 题解

给一种考场上最不用脑子也最不会写挂的做法吧(现场写加调1h左右,删了没有必要的行大概也就1k左右)

考虑二分年份mid,考察mid.1.1距离\text{BC}\ 4713.1.1的距离,剩余的日期我们暴力跳

问题转化为了算mid年到\text{BC}\ 4713年的总天数

这里有一个trick就是我们先把公元前的年份往前平移一年,即把\text{BC}\ 4713到\text{BC}\ 1年,平移到-4712到0年,最后算完年份再减一下,这样计算会方便很多

那么则有 总天数=365\times年数(也就是mid+4712)+闰年数量-10\times\left[mid>1582\right]

对于闰年数量,首先先算4的倍数的年份数量\left\lceil\dfrac{mid+4712}{4}\right\rceil

对于1600年后的整百年,贡献是\left\lceil\dfrac{mid-1600}{400}\right\rceil-\left\lceil\dfrac{mid-1600}{100}\right\rceil

那就算完了,注意long long以及二分边界即可.

复杂度O(Q\log年份值域)的

给一个考场上的代码(删了调试语句)

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
inline ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}

const int dom[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int y=-4737,m=1,d=1;
int isRUN(int y){
    if(y<=0){
        y=-y;
        return y%4==1;
    }
    if(y<=1582)return y%4==0;
    return (y%400==0)||((y%4==0)&&(y%100!=0));
}
void getnxtday(){
    d++;
    if(y==1582&&m==10&&d==5)d=15;
    if(d>dom[m]+(m==2&&isRUN(y)))m++,d=1;
    if(m>12)y++,m=1;
}
ll checkday(int x){
    ll day=1ll*(x+4712)*365;
    if(x>1582)day-=10;
    day+=1ll*(x+4712+3)/4;
    if(x>=1600){
        x-=1601;
        day-=(ll)x/100ll;
        day+=(ll)x/400ll;
    }
    return day;
}
int main(){
    int T;
    T=read(); 
    while(T--){
        y=0;m=d=1;
        ll n=readll();
        int l=-4712,r=1e9+1;
        while(l<=r){
            int mid=(l+r)/2;
            if(checkday(mid)<=n){
                y=mid;
                l=mid+1;
            }else r=mid-1;
        }
        n-=checkday(y);
        if(y<=0)y--;
        while(n--)getnxtday();
        printf("%d %d ",d,m);
        if(y<=0)printf("%d BC\n",-y);
        else printf("%d\n",y);
    }
    return 0;
}