P7075 [CSP-S2020] 儒略日 题解

· · 题解

题目传送门：P7075 [CSP-S2020] 儒略日

前情：第一次在 24 小时内过掉的绿题大模拟（喜）。

Part 1 遇事不决打暴力

我们首先可以写出一个判断某年某月天数的函数：如果是 1582 年 10 月则返回 21 天，否则判断是否是 2 月——如果是再判断是否是闰年，再判断是 30 天的还是 31 天的。

int day(int y,int i){
    if(y==1582&&i==10)return 21;
    if(i==2){
        if(y<0&&(-y)%4==1||y>0&&y<=1582&&y%4==0||y>1582&&(y%4==0&&!(y%100==0&&y%400!=0)))return 29;
        else return 28;
    }
    if(i<8&&(i&1)||i>7&&!(i&1))return 31;
    else return 30;
}

然后打出初版的处理函数：如果当前以处理天数加上当月的所有天数仍不大于目标天数则整月加，否则按日处理。

void doing(long long n){
    int year=-4713,month=1,date=1;
    long long i=0;
    while(i<n){
        int now=day(year,month);
        if(i+now>n){//时间差小于一个月
            date+=n-i;
            i=n;
            break;
        }
        else i+=now;
        if(year==0)year++;//公元零年的判定
        month++;
        if(month>12)year++,month=1;
    }
    cout<<date<<' '<<month<<' '<<abs(year);
    if(year<0)cout<<" BC";
    return;
}

主函数：

int main(){
    int Q;
    for(cin>>Q;Q--;cout<<'\n'){
        long long r;
        cin>>r;
        doing(r);
    }
    return 0;
}

得分：40 pts。

Part 2 按年处理的优化

我们现在是对于每月分块处理的，可以考虑进一步按年分块，则要写出判断整年天数的函数：

int day_year(int y){
    if(y==1582)return 355;
    if(day_month(y,2)==29)return 366;
    return 365;
}

主函数改为先按年处理整块，再按月、再按日的顺序：

void doing(long long n){
    int year=-4713,month=1,date=1;
    long long i=0;
    while(i<n){
        int now=day_year(year);
        if(i+now>n){//时间差小于一年
            while(i<n){
                now=day_month(year,month);
                if(i+now>n){//时间差小于一个月
                    date+=n-i;
                    i=n;
                    break;
                }
                else i+=now;
                if(year==0)year++;
                month++;
                if(month>12)year++,month=1;
            }
            break;
        }
        else i+=now;
        year++;
        if(year==0)year++;
    }
    cout<<date<<' '<<month<<' '<<abs(year);
    if(year<0)cout<<" BC";
    return;
}

得分：50 pts。

Part 3 再优化！取整余零

我们可以考虑：当 n（等同于 r_i）小于到公元 1600 年的天数时，按之前的年块处理方法。否则我们可以算出来每过 400 年所用的天数，然后直接从公元 1600 年起整块增加（直接加到到 n 不足 400 年时），剩下的依旧可以按年月日暴力处理。

为什么选择 1600 呢？因为这样可以有效避免处理一堆复杂的情况。

const long long k=2305448;//从 -4713/1/1 到 1600/1/1
const long long k400=146097;//从 1600/1/1 到 1999/12/31
void doing(long long n){
    int year=-4713,month=1,date=1;
    long long i=0;
    if(n>=k){
        int s400=(n-k)/k400;//包含的 400 年轮回的块数
        i=k+s400*k400;//增加的总天数
        year=1600+s400*400;//增加的年数
    }
    while(i<n){
        long long now=day_year(year);
        if(i+now>n){
            while(i<n){
                long long now2=day_month(year,month);
                if(i+now2>n){
                    date+=n-i;
                    i=n;
                    break;
                }
                else i+=now2;
                month++;
            }
            break;
        }
        else i+=now;
        year++;
        if(year==0)year++;
    }
    cout<<date<<' '<<month<<' '<<abs(year);
    if(year<0)cout<<" BC";
}

得分：90 pts。

Part 4 特殊情况

效果良好，但是好像踩到坑了。

我们发现上述代码对于 1582 年 10 月的处理会出逝，所以我们要判断一下让在公元 1582 年 10 月 4 日至 15 日的日期加 10，之后再处理下进月。

while(i<n){
  long long now=day_year(year);
  if(i+now>n){
    while(i<n){
      long long now2=day_month(year,month);
      if(i+now2>n){
        date+=n-i;
        if(year==1582&&month==10&&date>=5){
          date+=10;
          if(date>31){//进月
            date-=31;
            month++;
          }
        }
        i=n;
        break;
      }
      else i+=now2;
      month++;
    }
    break;
  }
}

得分：100 pts。

Part 5 卡个常

值得一提的是，这种方法可以卡常。上述代码是在关闭同步流加氧气优化的情况下 AC 的，这也体现出了这些优化的重要性。关闭同步流或者 O2 优化都会 TLE 一个点。这时我们还可以再对公元前的年份加以一个判断，具体代码见下（其实与之前讲的差不多，读者可以尝试自己实践一下）：

#include<iostream>
using namespace std;
const long long k=2305448,k0=1721424;//1 1 1600,1 1 1
const long long k400=146097,k400bc=146100;
void doing(long long n){
//……
    if(n>=k){
        int s400=(n-k)/k400;
        i=k+s400*k400;
        year=1600+s400*400;
    }
    else if(n<k0){
        int s400bc=(n)/k400bc;
        i=s400bc*k400bc;
        year+=s400bc*400;
    }
    else{
        i=k0;
        year=1;
    }
//……
}

现在，即使同时关闭同步流与 O2 优化也不会 TLE 了。氨醛苛銬。

其实这道题还可以卡常的地方多的很，读者有兴趣可以去一一实践。