HDU/4278

摘要

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

（WHU 2014-11-7练习赛）

题意

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

题解

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

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，然后每一位统计累加：

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

代码

4278.cpp代码已折叠 展开折叠内容

#include<cstdio> const int pV[11]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}, msdD[10]={0,0,0,1,1,1,1,1,2,2}; int f[11]={0,2}; void init() { for(int i=2;i<=10;++i) { f[i]=f[1]*pV[i-1]+f[i-1]*10-f[1]*f[i-1]; // printf("[%d]",f[i]) ; } } int main() { init(); while(1) { int n; scanf("%d",&n); if(n==0) return 0; int Missed=0; for(int i=1,u=n,t=1;u;++i,u/=10,t*=10) { int e=u%10; Missed+=f[i-1]*(e-msdD[e])+t*msdD[e]; } printf("%d: %d\n",n,n-Missed); } }