首页 > 代码库 > BZOJ 2898 模拟

BZOJ 2898 模拟

普及组水题.

按位模拟第一个序列和第二个序列,细节比较多..

仅为部分看后面两位的和,如果大于10就近位小于8就不进位等于9就看下一位.

技术分享
 1 #include <cstdio> 2 #define LL long long 3 LL Bin[20],K,Ten[20],SqrA[20],SqrB[20],Sqr[20]; 4 inline LL Get_A(LL x) 5 { 6     LL Pos; 7     for (LL i=1;i<=19;i++) if (x<=Bin[i]) {Pos=i; break;} 8     x=x-Bin[Pos-1]; 9     LL t=(x-1)/Pos+1;10     x=x-(t-1)*Pos;11     t=Ten[Pos]+t-1;12     for (LL i=1;i<=Pos-x;i++) t=t/10;13     return t%10;14 }15 inline LL Get_B(LL x)16 {17     LL Pos;18     for (LL i=1;i<=19;i++) if (x<=Sqr[i]) {Pos=i; break;}19     x=x-Sqr[Pos-1];20     LL t=(x-1)/Pos+1;21     x=x-(t-1)*Pos;22     t=t+SqrA[Pos]-1;23     t=t*t;24     for (LL i=1;i<=Pos-x;i++) t=t/10;25     return t%10;26 }27 LL Get_F(LL x)28 {29     LL Ret=Get_A(x)+Get_B(x);30     if (Ret>=10) return 1;31     if (Ret<=8) return 0;32     return Get_F(x+1);33 }34 inline void Init()35 {36     Ten[1]=1; for (LL i=2;i<=19;i++) Ten[i]=Ten[i-1]*10;37     Bin[1]=9; for (LL i=2;i<=19;i++) Bin[i]=Bin[i-1]*10;38     for (LL i=1;i<=19;i++) Bin[i]=Bin[i]*i;39     for (LL i=1;i<=19;i++) Bin[i]=Bin[i]+Bin[i-1];40      41     SqrA[1]=1,SqrB[1]=3;42     SqrA[2]=4,SqrB[2]=9;43     SqrA[3]=10,SqrB[3]=31;44     SqrA[4]=32,SqrB[4]=99;45     SqrA[5]=100,SqrB[5]=316;46     SqrA[6]=317,SqrB[6]=999;47     SqrA[7]=1000,SqrB[7]=3162;48     SqrA[8]=3163,SqrB[8]=9999;49     SqrA[9]=10000,SqrB[9]=31622;50     SqrA[10]=31623,SqrB[10]=99999;51     SqrA[11]=100000,SqrB[11]=316227;52     SqrA[12]=316228,SqrB[12]=999999;53     SqrA[13]=1000000,SqrB[13]=3162277;54     SqrA[14]=3162278,SqrB[14]=9999999;55     SqrA[15]=10000000,SqrB[15]=31622776;56     SqrA[16]=31622777,SqrB[16]=99999999;57     SqrA[17]=100000000,SqrB[17]=316227766;58     SqrA[18]=316227767,SqrB[18]=999999999;59     SqrA[19]=1000000000,SqrB[19]=2147483647;60     for (LL i=1;i<=19;i++) Sqr[i]=Sqr[i-1]+(SqrB[i]-SqrA[i]+1)*i;61 }62 int main()63 {64     scanf("%lld",&K);65     Init();66     printf("%lld\n",(Get_A(K)+Get_B(K)+Get_F(K+1))%10);67     return 0;68 }
C++

 

BZOJ 2898 模拟