首页 > 代码库 > 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 }
BZOJ 2898 模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。