摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
Faulty Odometer ★★☆☆☆ 答案正确 100 2014-11-07 13:50:44 编译错误(编译器位数导致)(0)

(WHU 2014-11-7练习赛)

题意

一个有bug的里程表盘,会自动跳过带数字3和8的数,问显示数字为N时,实际里程数有多少。

题解

还是递推的思路,先计算出10^i以下一共会跳过多少数,于是有

显示/移除行号
  1. f[i]=f[1]*pV[i-1]+f[i-1]*10-f[1]*f[i-1];//pV[n]表示10^n

然后再去统计每一位,比如3012可以抽象成3000+000+10+2,然后每一位统计累加:

显示/移除行号
  1. Missed+=f[i-1]*(e-msdD[e])+t*msdD[e];//msdD[e]表示数字e以下的被忽略的数有几个,e表示当前位的数字,i是位数

代码

4278.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<cstdio>
  2. const int pV[11]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000},
  3. msdD[10]={0,0,0,1,1,1,1,1,2,2};
  4. int f[11]={0,2};
  5. void init()
  6. {
  7. for(int i=2;i<=10;++i)
  8. {
  9. f[i]=f[1]*pV[i-1]+f[i-1]*10-f[1]*f[i-1];
  10. // printf("[%d]",f[i]) ;
  11. }
  12. }
  13. int main()
  14. {
  15. init();
  16. while(1)
  17. {
  18. int n;
  19. scanf("%d",&n);
  20. if(n==0)
  21. return 0;
  22. int Missed=0;
  23. for(int i=1,u=n,t=1;u;++i,u/=10,t*=10)
  24. {
  25. int e=u%10;
  26. Missed+=f[i-1]*(e-msdD[e])+t*msdD[e];
  27. }
  28. printf("%d: %d\n",n,n-Missed);
  29. }
  30. }

著作权声明[编辑]

关于[编辑]