吐槽这个题各种特判！
简直比后缀数组还难写！（尽管还未写过后缀数组……）
所幸1A了……要不调试都懒得调试
时间复杂度是O(logN)，以10为底，这意味着复杂度近乎O(1)……
题目链接：右转进入题目
题目大意：给定[l,r]，问其中有多少个数字不包含4和连在一起的62？
很明显就是数位DP嘛
为了学习数位DP，我们先看一个简单题：
给定[l,r]，问其中有多少个数字？
学长我有O(1)的做法！(⊙﹏⊙)我们先假定我不会……
发现我们只要用[1,r]的答案减去[1,l-1]的答案即可。
设R=a1a2...ai...alen。
用f[len][0/1]表示当前从左到右处理到第i位了，且前i位是否和R的前i位相等。0表示现在考虑的前i位小于R的i位（这意味着之后无论怎么填数，数字都是小于R的），1表示相等。
我们采用“刷表”的状态转移方法，依次考虑f[i][0]和f[i][1]能转移到哪里去。
先看f[i][0]，由于前i位已经<R的前i位了，那么第i+1位无论怎么放，前i+1位一定是<R的前i+1位的。
所以只能转移到f[i+1][0]。具体来说，第i+1位可以放0,1,...,9这十个数中的任意一个数，所以f[i+1][0]+=10*f[i][0]。
再看f[i][1]，这时如果第i+1位也等于R的第i+1位，那么可以转移到f[i+1][1]，具体来说f[i+1][1]+=f[i][1]（系数为1是因为第i+1为了紧贴上界只能填a(i+1)）。
当然也可以填0,1,...,a(i+1)-1这a(i+1)个数字中的某一个转移到f[i+1][0]。具体来说f[i+1][0]+=a[i+1]*f[i][1]。
这样最后f[len][0]+f[len][1]-1就是答案啦（为什么要减一呢？留给大家思考！）！
边界：f[1][0]=a1，f[1][1]=1。
这个代码如下：
//求1~n中有多少整数 #include<iostream> #include<cstdio> #include<cstring> #define MAXLEN 10 using namespace std; int f[MAXLEN][2],a[MAXLEN],len; int main() { int n;scanf("%d",&n);len=0; while(n) a[++len]=n,n/=10; for(int i=1;i<=len/2;i++) swap(a[i],a[len-i+1]); f[1][0]=a[1]; f[1][1]=1; for(int i=1;i<len;i++) { f[i+1][0]+=10*f[i][0]+a[i+1]*f[i][1]; f[i+1][1]+=f[i][1]; } printf("%d\n",f[len][0]+f[len][1]-1);//f[len][0]+f[len][1] includes 00...00. return 0; }那么不要62这个题类似，用f[i][0/1][0/1]表示考虑到了第i为，第一个0/1表示</=前i位，第二个0/1表示第i位=/!=6.状态转移方程十分显然，但是十分繁琐，注意各种特判再次不作说明。
仅供代码参考：
//HDU 2089 #include<iostream> #include<cstdio> #include<cstring> #define MAXLEN 8 using namespace std; int f[MAXLEN][2][2],a[MAXLEN],len; //f[i][</=][=6/!=6] int tonum(int x) { len=0; while(x) a[++len]=x,x/=10; for(int i=1;i<=len/2;i++) swap(a[i],a[len-i+1]); return 0; } int dp() { if(!len) return 1; for(int i=1;i<=len;i++) f[i][0][0]=f[i][0][1]=f[i][1][0]=f[i][1][1]=0; if(a[1]>6) f[1][0][0]=1; f[1][0][1]=a[1]; if(a[1]>4) f[1][0][1]--; if(a[1]>6) f[1][0][1]--; if(a[1]==6) f[1][1][0]=1; if(a[1]!=4&&a[1]!=6) f[1][1][1]=1; for(int i=1;i<len;i++) { f[i+1][0][0]+=f[i][0][0]; f[i+1][0][1]+=7*f[i][0][0]; f[i+1][0][0]+=f[i][0][1]; f[i+1][0][1]+=8*f[i][0][1]; if(a[i+1]==6) f[i+1][1][0]+=f[i][1][0]; if(a[i+1]!=2&&a[i+1]!=4&&a[i+1]!=6) f[i+1][1][1]+=f[i][1][0]; if(a[i+1]>6) f[i+1][0][0]+=f[i][1][0]; f[i+1][0][1]+=a[i+1]*f[i][1][0]; if(a[i+1]>2) f[i+1][0][1]-=f[i][1][0]; if(a[i+1]>4) f[i+1][0][1]-=f[i][1][0]; if(a[i+1]>6) f[i+1][0][1]-=f[i][1][0]; if(a[i+1]>6) f[i+1][0][0]+=f[i][1][1]; f[i+1][0][1]+=a[i+1]*f[i][1][1]; if(a[i+1]>4) f[i+1][0][1]-=f[i][1][1]; if(a[i+1]>6) f[i+1][0][1]-=f[i][1][1]; if(a[i+1]==6) f[i+1][1][0]+=f[i][1][1]; if(a[i+1]!=4&&a[i+1]!=6) f[i+1][1][1]+=f[i][1][1]; } return f[len][0][0]+f[len][0][1]+f[len][1][0]+f[len][1][1]; } int main() { int l,r,ans; while(scanf("%d%d",&l,&r)!=EOF&&(l||r)) { tonum(r);ans=dp(); tonum(l-1);ans-=dp(); printf("%d\n",ans); } return 0; }