杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。 杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。 不吉利的数字为所有含有4或62的号码。例如： 62315 73418 88914 都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。 你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。 Input 输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。 Output 对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。 Sample Input 1 100 0 0 Sample Output 80
枚举肯定是不行的 ，数位太多 ，会超时
所以用dp递推出以i为首位，位数为j的数字个数dp[i][j]并储存，以空间降低时间
递推过程,高位dp为低位各dp的和，并判断4和62的情况
for (int j=1; j<=9; j++){ for (int i=0; i<=9; i++){ if (j==1) dp[i][j]=1; if (i==4) dp[i][j]=0; else if(i==6){ dp[i][j]=dp[i][j]+dp[0][j-1]+dp[1][j-1]; for (int k=3;k<=9;k++)dp[i][j]+=dp[k][j-1]; } else for (int k=0;k<=9;k++)dp[i][j]+=dp[k][j-1]; } } 或 更简单的 （在函数外定义dp[10][10]） dp[0][0] = 1; for (int i = 1; i <= 7; ++i) for (int j = 0; j <= 9; ++j) for (int k = 0; k <= 9; ++k) { if (j != 4 && !(j == 6 && k == 2)) dp[i][j] += dp[i - 1][k];
注：g++环境下 在函数外定义数组初始值是0，在函数内定义数组初始值是随机值
求出0~n和0~m+1之间的数位，相减即是n~m之间的数位个数
数位统计函数：
long long solve(int x){ int a[10]={0},k,i=0; long long ans=0; while(x){ a[++i]=x%10; x/=10; } for (int j=i;j>=1;j--){ for (int k=0;k<a[j];k++){ if (!( k==2&&a[j+1]==6)) ans+=dp[k][j]; // printf("i %d j %d %lld ",k,j,dp[k][j]); } if(a[j]==4||a[j]==2&&a[j+1]==6)break; } // printf("%d-%lld ",x,ans); return ans; }
（因为随机值的问题，刚开始没有写a【10】={0}，结果a【4】正好随机为6）
#include<bits/stdc++.h> #define ll long long using namespace std; ll dp[10][10]; long long solve(int x){ int a[10]={0},k,i=0; long long ans=0; while(x){ a[++i]=x%10; x/=10; } for (int j=i;j>=1;j--){ for (int k=0;k<a[j];k++){ if (!( k==2&&a[j+1]==6)) ans+=dp[k][j]; // printf("i %d j %d %lld ",k,j,dp[k][j]); } if(a[j]==4||a[j]==2&&a[j+1]==6)break; } // printf("%d-%lld ",x,ans); return ans; } int main(){ // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); memset(dp,0,sizeof(dp)); //num-dig dp for (int j=1; j<=9; j++){ for (int i=0; i<=9; i++){ //1-dig num if (j==1) dp[i][j]=1; if (i==4) dp[i][j]=0; else if(i==6){ dp[i][j]=dp[i][j]+dp[0][j-1]+dp[1][j-1]; for (int k=3;k<=9;k++)dp[i][j]+=dp[k][j-1]; } else for (int k=0;k<=9;k++)dp[i][j]+=dp[k][j-1]; // printf("dp %d %d %lld ",i ,j ,dp[i][j]); } } int n,m; while(scanf("%d%d",&n,&m)!=EOF&&(m||n)){ printf("%lld ",solve(m+1)-solve(n)); } return 0; }