不要62
题目大意：给你一个区间，算出该区间里不含62或4的数的个数
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089
1 /* 2 // 暴力就可以过了。。。 3 #include<stdio.h> 4 #define N 1000000 5 int sum[N]; 6 bool fun(int x) 7 { 8 bool flag=0; 9 while(x) 10 { 11 int tmp=x%10; 12 if(tmp==4) return 0; 13 else if(tmp==2) flag=1; 14 else if(tmp==6&&flag==1) return 0; 15 else flag=0; 16 x/=10; 17 } 18 return 1; 19 } 20 void Init() 21 { 22 sum[0]=0; 23 for(int i=1;i<N;i++) 24 { 25 if(fun(i)==1) sum[i]=sum[i-1]+1; 26 else sum[i]=sum[i-1]; 27 } 28 } 29 int main() 30 { 31 Init(); 32 int n,m; 33 while(scanf("%d%d",&n,&m)!=EOF) 34 { 35 if(n==0&&m==0) break; 36 printf("%d ",sum[m]-sum[n-1]); 37 } 38 return 0; 39 } 40 */ 41 #include<stdio.h> 42 int dp[10][3]={0}; 43 //dp[i][0] 数的长度为 i ，且不含不吉利数字 ( 不含62和4 ) 44 //dp[i][1] 数的长度为 i ，不含不吉利数字且最高位为2 45 //dp[i][2] 数的长度为 i ，存在不吉利数字 46 47 void Init() 48 { 49 dp[0][0]=1; 50 for(int i=1;i<7;i++) 51 { 52 // i位的不含不吉利数字的数的个数为 i-1位的乘以 9 （去掉4）,再减去 i-1 位时吉利的且最高位为2的数的个数（6） 53 dp[i][0]=dp[i-1][0]*9-dp[i-1][1]; 54 // i位的最高位为2的吉利数个数和i-1位的吉利数的个数相同 55 dp[i][1]=dp[i-1][0]; 56 // i位的不吉利数为 i-1位不吉利数的个数*10 + i-1位吉利数的个数（4）+ i-1位最高位为2的吉利数的个数 57 dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1]; 58 } 59 } 60 int solve(int x) 61 { 62 int c[10],co=1,n=x,s=0; //s为不吉利的数的个数 63 while(x) 64 { 65 c[co++]=x%10; 66 x/=10; 67 } 68 c[co]=0; 69 bool flag=0; 70 // 从最高位往后推 71 for(int i=co-1;i>0;i--) 72 { 73 s+=c[i]*dp[i-1][2]; //后面造成的不吉利数 74 if(flag==1) //前几位已经出现了不吉利现象，也就是说后面不管是啥，都是不吉利的。 75 { 76 s+=c[i]*dp[i-1][0]; 77 continue; 78 } 79 if(c[i]>4) //第i位为4造成的不吉利数 80 s+=dp[i-1][0]; 81 if(c[i+1]==6&&c[i]>2)//第i+1位为6 第i位为2造成的不吉利数 82 s+=dp[i][1]; 83 if(c[i]>6) //第i位为6造成的不吉利数 84 s+=dp[i-1][1]; 85 if(c[i]==4||c[i+1]==6&&c[i]==2) flag=1; 86 } 87 return n-s; 88 } 89 int main() 90 { 91 Init(); 92 int l,r; 93 while(scanf("%d%d",&l,&r)!=EOF) 94 { 95 if(l==0&&r==0) break; 96 printf("%d ",solve(r+1)-solve(l)); 97 } 98 return 0; 99 }