1 100 0 0
80
//0MS 1148K #include<stdio.h> #include<string.h> using namespace std; int dp[10][3],a[10]; void init() { memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=7;i++) { dp[i][0]=dp[i-1][0]*9-dp[i-1][1];//不存在不吉利数字情况是上一次不存在*9-开头为2的情况 dp[i][1]=dp[i-1][0];//存在不吉利数字且高位为2情况是上一次开头只放2 dp[i][2]=dp[i-1][2]*10+dp[i-1][1]+dp[i-1][0];//存在不吉利数字情况是上一次所有情况 } } int solve(int num) { int k=0,ans=0,sum=num,flag=0; while(num) { a[++k]=num%10; num/=10; } a[k+1]=0; for(int i=k;i>=1;i--) { ans+=dp[i-1][2]*a[i]; if(flag)ans+=dp[i-1][0]*a[i]; if(!flag&&a[i]>4)ans+=dp[i-1][0];//首位大于4,可以有放4的情况 if(!flag&&a[i+1]==6&&a[i]>2)ans+=dp[i][1];//后一位为6,此位大于2 if(!flag&&a[i]>6)ans+=dp[i-1][1];//此位大于6,可能的62状况 if(a[i]==4||(a[i+1]==6&&a[i]==2))flag=1; } return sum-ans; } int main() { init(); int l,r; while(scanf("%d%d",&l,&r),l|r) printf("%d\n",solve(r+1)-solve(l)); }
原文:http://blog.csdn.net/crescent__moon/article/details/43455757