题意：求n~m间的数中，多少不带4和62的数。
思路：数位dp
#include<iostream> #include<stdio.h> using namespace std; long long dp[10][3]; /* dp[i][0]，不含有不吉利数字 dp[i][1]，不含有不吉利数字，最高位为2 dp[i][2]，含有不吉利数字 */ void init(){ dp[0][0]=1; dp[0][1]=dp[0][2]=0; int i; for(i=1;i<=6;++i){ dp[i][0]=9*dp[i-1][0]-dp[i-1][1];//不含不吉利数字前面加除4外9个数，减掉2前面加6 dp[i][1]=dp[i-1][0];//不含不吉利数字前面加2 dp[i][2]=10*dp[i-1][2]+dp[i-1][0]+dp[i-1][1];//含不吉利数字前面加0~9，加上不含不吉利数字前加4，加上2前面加6 } } int bit[10]; int calc(int n){ int len=0,i,tmp=n; while(n){ bit[++len]=n%10; n/=10; } bit[len+1]=0; bool flag=false; long long ans=0; for(i=len;i>=1;--i){ ans+=dp[i-1][2]*bit[i];//注意这个位置，求的是前缀+当前位置 if(flag)ans+=dp[i-1][0]*bit[i]; else{//有3中情况 if(bit[i]>4)ans+=dp[i-1][0]; if(bit[i+1]==6&&bit[i]>2)ans+=dp[i][1]; if(bit[i]>6)ans+=dp[i-1][1]; } if(bit[i]==4||bit[i+1]==6&&bit[i]==2)flag=true; } if(flag)++ans;//加上n本身 return tmp-ans; } int main(){ init(); int n,m; while(scanf("%d%d",&n,&m)){ if(n==0&&m==0)break; printf("%d ",calc(m)-calc(n-1)); } return 0; }