首页 > 代码库 > ZOJ 3950 How Many Nines
ZOJ 3950 How Many Nines
暴力，预处理。
先计算出一个平年有多少$9$，一个闰年有多少$9$。一组数组，头和尾暴力枚举一下，中间的直接算。
#include<bits/stdc++.h>using namespace std;int a[2][20]={ {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},};int leap(int x){ if(x%400==0) return 1; if(x%4==0&&x%100!=0) return 1; return 0;}int c[20000];int x,y;int f[20000];int k[20000];void init(){ for(int i=0;i<=9999;i++) { c[i]=0; int tmp=i; while(tmp) { if(tmp%10==9) c[i]++; tmp=tmp/10; } } int M=1, D=1; x=0;y=0; while(1) { x=x+c[D]+c[M]; D++; if(D>a[0][M]) { M++; D=1; if(M>12) { M=1; } } if(M==12&&D==31) break; } y=x+1; for(int i=2000;i<=9999;i++) f[i] = leap(i) + f[i-1]; for(int i=2000;i<=9999;i++) k[i] = k[i-1] + c[i]*(365+leap(i));}int main(){ init(); int T; scanf("%d",&T); while(T--) { int ans=0; int A1,B1,C1; scanf("%d%d%d",&A1,&B1,&C1); int A2,B2,C2; scanf("%d%d%d",&A2,&B2,&C2); if(A1==A2||A1+1==A2) { int Y=A1, M=B1, D=C1; while(1) { ans=ans+c[Y]+c[M]+c[D]; if(Y==A2&&M==B2&&D==C2) break; D++; if(D>a[leap(Y)][M]) { M++; D=1; if(M>12) { M=1;Y++; } } } } else { int Y=A1, M=B1, D=C1; while(1) { ans=ans+c[Y]+c[M]+c[D]; if(Y==A1&&M==12&&D==31) break; D++; if(D>a[leap(Y)][M]) { M++; D=1; if(M>12) { M=1;Y++; } } } Y=A2, M=1, D=1; while(1) { ans=ans+c[Y]+c[M]+c[D]; if(Y==A2&&M==B2&&D==C2) break; D++; if(D>a[leap(Y)][M]) { M++; D=1; if(M>12) { M=1;Y++; } } } ans=ans+k[A2-1]-k[A1]+x*(A2-A1-1)+f[A2-1]-f[A1]; } printf("%d\n",ans); } return 0;}
ZOJ 3950 How Many Nines
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。