尽管是一道简单的模拟题,但是却能反映出我和高水平选手的差距。
注:本文日期将由 YY/MM/DD 的形式描述。例如 2020 年 11 月 20 日为 2020/11/20,公元前将加上后缀 BC。如公元前 4713 年 1 月 1 日为 4713/1/1 BC
首先贴出三分将要被分析的代码:
#include<bits/stdc++.h>
typedef long long ll;
const int U=24e5,aa[14]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int Q,a[14],D[U],M[U],Y[U],d,m,y,L,bc;bool BC[U];
ll r;
int main(){
freopen("julian.in","r",stdin);freopen("julian.out","w",stdout);
d=1;m=1;y=4713;bc=1;
for(;;){
if(bc || y!=1582 || m!=10 || d<=4 || d>=15){
D[L]=d;M[L]=m;Y[L]=y;BC[L]=bc;++L;
}
if(d==31 && m==12 && y==1582 && !bc)break;
if(d==28 && m==2 && (bc?y%4==1:y%4==0))d=29,m=2;else{
if(d==31 && m==12){
d=m=1;
if(bc)--y,y==0?y=1,bc=0:0;else ++y;
}else if(d>=aa[m])d=1,++m;else ++d;
}
}
for(scanf("%d",&Q);Q--;){
scanf("%lld",&r);
if(r<L){
printf("%d %d %d %s\n",D[r],M[r],Y[r],BC[r]?"BC":"");
}else{
r-=L;d=m=1;y=1583;
int z=365*400+97,x;
y+=r/z*400;r%=z;
for(;x=y%4==0 && (y%100 || y%400==0)?366:365,r>=x;r-=x,++y);
for(;x=m==2 && y%4==0 && (y%100 || y%400==0)?29:aa[m],r>=x;r-=x,++m);
printf("%d %d %d\n",d+(int)r,m,y);
}
}
}
// source ZJ-00783
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"----------------"#x"----------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = "; For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned uint;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef pair <int,int> pii;
LL read(){
LL x=0,f=0;
char ch=getchar();
while (!isdigit(ch))
f=ch=='-',ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
const int N=7000*400;
struct date{
int y,m,d,tp;
date(){}
date(int _y,int _m,int _d,int _tp){
y=_y,m=_m,d=_d,tp=_tp;
}
friend bool operator == (date a,date b){
return a.y==b.y&&a.m==b.m&&a.d==b.d&&a.tp==b.tp;
}
}a[N],sd(1582,10,15,1),ed(1982,10,14,1),wtf(1582,10,4,1);
int sp,ep;
int md[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
date nxtday(date v){
int y=v.y,m=v.m,d=v.d,tp=v.tp;
if (tp==0){
d++;
int mxd=m==2&&y%4==1?29:md[m];
if (d>mxd){
d=1;
m++;
if (m>12){
m=1;
y--;
if (y==0)
return date(1,1,1,1);
}
}
return date(y,m,d,0);
}
else if (v==wtf){
return sd;
}
else {
d++;
int mxd=m==2&&(y%4==0&&(y<=1582||y%100!=0||y%400==0))?29:md[m];
if (d>mxd){
d=1;
m++;
if (m>12){
m=1;
y++;
}
}
return date(y,m,d,1);
}
}
int main(){
#ifndef zzd
freopen("julian.in","r",stdin);
freopen("julian.out","w",stdout);
#endif
date v=a[0]=date(4713,1,1,0);
//0..ep-1
for (int &i=ep=1;!(v==ed);i++){
a[i]=v=nxtday(v);
if (v==sd)
sp=i;
}
int T=read();
while (T--){
LL x=read();
if (x<sp){
printf("%d %d %d%s\n",a[x].d,a[x].m,a[x].y,a[x].tp==0?" BC":"");
}
else {
int rd=(x-sp)/(ep-sp);
LL xx=x-rd*(ep-sp);
printf("%d %d %d\n",a[xx].d,a[xx].m,a[xx].y+rd*400);
}
}
return 0;
}
// source ZJ-00792
#include<bits/stdc++.h>
using namespace std;
bool Ka;
int Mon[]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
int _1=365,_4=_1*4+1,_100=_4*25-1,_400=_100*4+1,lim=107660;
int n,x,y,z,now;
long long a;
bool Bar;
int Chk(int x){
return x%4==0&&(x<1582||x%100||x%400==0);;
}
int main() {
// printf("%lf\n",(&Ka-&Bar)/1024.0/1024.0);
freopen("julian.in","r",stdin);
freopen("julian.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; ++i) {
x=-4712,y=z=1;
scanf("%lld",&a);
while(a>=(_4*100)&&x+400<1582)x+=400,a-=_4*100;
if(x==1288&&a>lim)a+=10;//,printf("++ ");
while(a>=(now=(_1+(x%4==0)))&&x!=1582)a-=now,++x;
x+=(a/_400)*400,a%=_400;
while(a>=(now=(_1+Chk(x))))a-=now,++x;
Mon[2]+=Chk(x);
while(a>=Mon[y])a-=Mon[y],++y;
Mon[2]=28;
z+=a;
printf("%d %d ",z,y);
if(x<=0)printf("%d BC\n",-x+1);
else printf("%d\n",x);
}
return 0;
}
// source ZJ-00127
这三份代码中,前两份代码的思路相似:通过一天一天地推到某个分界点。回答询问时,对询问在分界点前后进行讨论并回答。最后一份的代码思路是直接模拟地跳,但是运用了一些手段使得代码长度非常简单。
下面将对这两种思路分开进行分析。
思路一:一天一天地推再回答询问
前两份代码思路都是这种。
如果对于所有答案都一天一天推,那么复杂度将会是
注意到在预处理范围之外的日期,其实一定存在一个预处理范围之内的日期 xx
(如第二份代码中命名),满足询问日期与 xx
仅在年份上差若干个 400 年。这样可以更简单地实现回答预处理范围之外的答案。
那么思路就非常清晰了,先递推,然后回答询问。因为是一天一天地推,细节非常少,实现非常简单。
自己在考后写的代码:
const int MAXN = 5e6 + 10;
const int month[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
#define chk(_) (tag ? (!(_.Y % 4) && ((_.Y % 100) || !(_.Y % 400))) : !(_.Y % 4))
bool tag;
struct Date {
ll Y; int D, M;
bool operator <(const Date& _) { return (Y < _.Y) || (Y == _.Y && M < _.M) || (Y == _.Y && M == _.M && D < _.D); }
bool operator ==(const Date& _) { return (Y == _.Y) && (D == _.D) && (M == _.M); }
Date() {}
Date(int y, int m, int d) { Y = y, D = d, M = m; }
void out() { IO::write(D), IO::write(M); (Y <= 0) ? IO::write(-Y + 1), puts("BC"), void() : IO::write(Y, '\n'), void(); }
} ans[MAXN];
ll st, ed;
Date St(1582, 10, 15);
Date BB(1582, 10, 4);
Date Ed(1982, 10, 15);
Date nxt(const Date& xx) {
Date ret = xx;
if (ret == BB) ret = St;
else {
bool tag = !(ret < St);
ret.D++;
if (ret.D > month[ret.M] + (ret.M == 2 && chk(ret))) ret.D = 1, ret.M++;
if (ret.M > 12) ret.M = 1, ret.Y++;
}
return ret;
}
int main() {
freopen("julian.in", "r", stdin);
freopen("julian.out", "w", stdout);
Date cur(-4712, 1, 1);
ans[0] = cur;
int idx = 1;
while(cur < Ed) {
ans[idx] = nxt(cur);
if (ans[idx] == St) st = idx;
if (ans[idx] == Ed) ed = idx;
cur = ans[idx]; idx++;
}
int t; IO::read(t);
rep(_, 1, t) {
ll x; IO::read(x);
if (x <= idx) ans[x].out();
else {
ll cnt = (x - st) / (ed - st);
Date Ans = ans[x - cnt * (ed - st)]; Ans.Y += cnt * 400;
Ans.out();
}
}
return 0;
}
只要想到了这个思路,就可以非常快速地实现与调试。我认为在考场上选择这种思路是最优秀的。
思路二:模拟
第三份代码或许是一步一步从暴力讨论合并下来的,具体而言:
整个时间轴被 4713/1/1 BC,1/1/1,1582/10/4 分成了三部分,如果要对这三部分分开讨论,会非常麻烦。
如果能合并这三段就好了。
考虑到第一段(4713/1/1 BC - 1/1/1)和第二段(1/1/1 - 1582/10/4)的差距仅仅是在判断闰年是,第一段的闰年年份
第三段和第二段有两个区别:
- 判断闰年。第三段时格里高利历。为了合并,我们只需要维护一个标记,看答案是否是在第三段内。是的话就用格里高利历,否则就用儒略历。
- 跳过 1582/10/5 - 1582/10/14,同样的,如果答案是在第三段内,就给剩下未跳的天数加上
10 ,来保证跳过 1582/10/5 - 1582/10/14。
容易发现这两个步骤都只需要判断答案是否在 1582/10/4 之后。具体而言,先将时间推到 1582/1/1,然后判断剩下的天数是否超过了从 1 月 1 日到 10 月 4 日所需天数即可。
之后,先以
自己在考后写的代码:
typedef long long ll;
const int month[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
const int year = 365, fourYrs = year * 4 + 1, fourCtrs[] = { 100 * fourYrs, fourYrs * 100 - 3 };
int t, cur; bool tag;
ll Y; int D, M;
#define chk (tag ? (!(Y % 4) && ((Y % 100) || !(Y % 400))) : !(Y % 4))
void solve() {
ll x; scanf("%lld", &x); tag = false;
Y = -4712, D = M = 1;
while ((x >= fourCtrs[tag]) && Y + 400 <= 1582) x -= fourCtrs[tag], Y += 400;
while (x >= (cur = year + chk) && Y + 1 <= 1582) x -= cur, Y++;
if (Y == 1582 && x >= 277) x += 10, tag = true;
Y += 1ll * 400 * (x / fourCtrs[tag]), x %= fourCtrs[tag];
while (x >= (cur = year + chk)) x -= cur, Y++;
while (x >= (month[M] + (M == 2 && chk))) x -= month[M] + (M == 2 && chk), M++;
D += x;
printf("%d %d ", D, M);
if (Y <= 0) printf("%lld BC\n", -Y + 1);
else printf("%lld\n", Y);
}
int main() {
freopen("julian.in", "r", stdin);
freopen("julian.out", "w", stdout);
scanf("%d", &t); while (t--) solve();
return 0;
}
这个方法的代码非常短,经过一些压行,目前该代码是 LOJ 上最短的。但是该代码细节较之第一种思路略多,可能需要写的时候头脑清醒,不要一不留神就犯下错误。
对比两种思路
综合来看,我认为三份代码中一二份代码最优,不需要考虑太多细节,并且易于实现。但需要一些思维的基础,如果以前没有做过类似的题或许很难想到“先模拟一部分的答案”这个思路(例如我确实考场上就没想到)。而第三份代码则是基于暴力的讨论与模拟,这是更容易想到的。但是这种方法虽然思维含量相对不高,但细节较多。容易写错。如果不能理清思路,考虑完全,会像我一样得到很低地分数。
对比我和他们的差距
贴上考场写的代码:
typedef long long ll;
int q;
ll DD, MM, YY, x;
const ll month_days[2][14] = {{ 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }, { 0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }};
const ll centry_days[5] = { 36525, 36524, 36524, 36524 };
void get_DD_MM(bool tag) {
for (int idx = 1; idx <= 12; ++idx) {
if (x < month_days[tag][idx]) {
DD += x;
return ;
} else MM++, x -= month_days[tag][idx];
}
}
void get_YY(int flg) {
if (x < 366) {
get_DD_MM(true);
} else {
YY += flg; x -= 366;
YY += x / 365 * flg; x = x % 365;
get_DD_MM(false);
}
}
void solve() {
YY = DD = MM = 0;
IO::read(x);
if (x == 2299160) {
DD = 4, MM = 10, YY = 1582;
IO::write(DD, ' '), IO::write(MM, ' '), IO::write(YY, '\n');
return ;
} else if (x == 2299161) {
DD = 15, MM = 10, YY = 1582;
IO::write(DD, ' '), IO::write(MM, ' '), IO::write(YY, '\n');
return ;
}
if (x < 1721424) { // Julian B.C.
DD = 1, MM = 1, YY = 4713;
YY -= x / 1461 * 4; // now its 1 1 ansYY
x = x % 1461;
get_YY(-1);
IO::write(DD, ' '), IO::write(MM, ' '), IO::write(YY, ' '), puts("BC");
} else if (1721424 <= x && x < 2299161) {
x -= 1721424;
YY = DD = MM = 1;
YY += x / 1461 * 4; // now its 1 1 ansYY
x = x % 1461;
if (x < 1095) {
YY += x / 365; x = x % 365;
get_DD_MM(false);
} else {
x -= 1095;
YY += 3, x = x % 365;
get_DD_MM(true);
}
IO::write(DD, ' '), IO::write(MM, ' '), IO::write(YY, '\n');
} else {
YY = 1582, DD = 15, MM = 10;
x -= 2299162;
if (x < 6286) {
if (x < 16) DD += x;
else if (x < 77) {
DD = 1, MM = 11; x -= 16;
rep(i, 11, 12) {
if (x >= month_days[false][i]) x -= month_days[false][i], MM++;
else {
DD += x; break;
}
}
} else {
x -= 77; YY = 1583; DD = MM = 1;
YY += x / 1461 * 4;
x = x % 1461;
if (x < 365) {
get_DD_MM(false);
} else if (x < 731) {
YY++; x -= 365, get_DD_MM(true);
} else {
YY += 2, x -= 731;
YY += x / 365; x = x % 365;
get_DD_MM(false);
}
}
} else {
x -= 6286;
YY = 1600, DD = MM = 1;
YY += x / 146097 * 400; x = x % 146097;
rep(i, 0, 3) {
if (x >= centry_days[i]) YY += 100, x -= centry_days[i];
else {
if (i == 0) {
YY += x / 1461 * 4;
x = x % 1461;
get_YY(1);
} else {
if (x < 1460) {
YY += x / 365; x = x % 365;
get_DD_MM(false);
} else {
x -= 1460; YY += 4;
YY += x / 1461 * 4;
x = x % 1461;
get_YY(1);
}
}
break;
}
}
}
IO::write(DD, ' '), IO::write(MM, ' '), IO::write(YY, '\n');
}
}
int main() {
// freopen("julian.in", "r", stdin);
// freopen("julian.out", "w", stdout);
IO::read(q);
while (q--) solve();
return 0;
}
直观的感受是,这份代码非常冗长。
虽然这份代码与第三份代码都是从暴力讨论出发,但是我没有进行合并等操作,导致需要分开处理三段。而且在计算
总之,我的考场代码是“能讨论就不枚举”,总是想自己手算完所有情况呢,不把一些计算量较小的任务交给程序来做,而这恰恰是程序最擅长的。
题做少了,代码写少了,基础薄弱了,思路狭窄了。
接下来很长的一段时间里,我会着重强化自己的基础,提高自己的实现能力。
继续努力!
orz
llf GKJY!