不要62
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 26743 Accepted Submission(s): 9385
Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有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最基础的题目。。
首先我们设数组f[i][j]代表第i位是j有f[i][j]种情况。
然后我们用预处理出10位以下的f[i][j].
转移大约是f[i][j]=f[i-1][k](k!=4&&j!=4&&!(j==6&&k==2))
然后求出这个以后,我们可以认为答案=1-R之间的数字个数-1-L之间的数字个数
大约是对于一个数字，先把它存入一个数组
然后对于最高位,可以是0-num[len].
这里分三种情况:
1.是0的情况,这是我们推向更低位。
2.是num[len]，我们也推向更低位。
3.其他情况直接加f数组。
对于1情况，我们直接把len-1到1的位数的每一位设为1-9然后加上f[i][j].这样处理完了所有位的所有情况。
对于2情况，就是下一位的3种情况和。
3情况不用说。
注意考虑合法情况。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm> using namespace std; int f[][]; void DP()
{
for(int i=;i<=;i++)
if(i!=)f[][i]=;
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(j!=)
for(int kk=;kk<=;kk++)
if(kk!=&&!(j==&&kk==))
f[i][j]+=f[i-][kk];
} int get(int x)
{
int num[],len=,res=;
while(x)
{
num[++len]=x%;
x/=;
}
for(int i=;i<num[len];i++)
res+=f[len][i];
for(int i=;i<=len-;i++)
for(int j=;j<=;j++)
res+=f[i][j];
if(num[len]==)return res;
for(int i=len-;i>=;i--)
{
for(int j=;j<num[i];j++)
{
if(j== || (j== && num[i+]==) )continue;
res+=f[i][j];
}
if(num[i]== || (num[i+]== && num[i]==) )break;
}
return res;
} int main()
{
DP();
int l,r,num,snum,ans=;
while()
{
scanf("%d%d",&l,&r);
if(!(l&&r))break;
printf("%d\n",get(r+)-get(l));
}
return ;
}