不要62
time limit per test 2 second memory limit per test 256 megabytes
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。

传送门:HDU2089

Input

输入的都是整数对n、m(0< n ≤ m< 1000000),如果遇到都是0的整数对,则输入结束。

Output

对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。

Sample Input

1
2
1 100
0 0

Sample Output

1
80

题解

数位dp入门 dp[i][j]:i位以j为最高位满足条件的数的个数 然后求 0-n-1有几个满足的基于这样一个定理 一个数比另一个数小的话,一定有一位比另一个数小 那么我们对每一个数从高位看起 先算第一位比它低的且满足条件的数 然后算第一位不变,第二位比它低的... 感觉还是下面这个讲的好一点 很简单,既然小于,从最高位开始比,必定有一位要严格小于x(前面的都相等)。所以我们就枚举哪一位严格小于(前面的都相等)。 假设我们现在把x分成了a1,a2,...,aL这样一个数组,长度为L,aL是最高位。 那么结果实际上就是这样:长度为L,最高位取[0,aL-1]的所有的符合题意数的和;再加上长度为L-1,最高位取aL,次高位取[0,aL-1-1]的所有符合题意数的和;再加上……;一直到第一位。 上面有一句话之所以标粗体,是因为这句话并不是对的,但是为了好看,就先这样写着。因为我们还需要考虑这种情况:最高位aL如果是4,那么这句话直接就可以终止了,因为粗体这句话前面的那句话“最高位取aL”是不能成立的。还要考虑这种情况:最高位aL如果是6,那么这里并不是能取[0,aL-1-1]的所有(不能取2)。加上这些条件之后就很严谨了。
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.io.*;  
import java.util.*;
public class Main {
static int[][]swdp;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
PrintWriter pw=new PrintWriter(System.out);
int[]dp=new int[1000000];
swdp=new int[10][10];
swdp[0][0]=1;
for(int i=1;i<=7;i++){
for(int j=0;j<=9;j++){
for(int k=0;k<=9;k++){
if(j!=4&&!(j==6&&k==2)){
swdp[i][j]+=swdp[i-1][k];
}
}
}
}
/*dp[0]=1;
for(int i=1;i<1000000;i++){
if(check(i)){
dp[i]=dp[i-1]+1;
}else{
dp[i]=dp[i-1];
}
}*/
while(sc.hasNext()){
int s=sc.nextInt();
int e=sc.nextInt();
if(s==0&&e==0)break;
pw.println(js(e+1)-js(s));
pw.flush();
}
}
static int js(int t){
int count=0;
String s=String.valueOf(t);
for(int i=0;i<s.length();i++){
for(int k=0;k<(s.charAt(i)-'0');k++){
if(k!=4&&!(i>=1&&s.charAt(i-1)=='6'&&k==2))
count+=swdp[s.length()-i][k];
}
if(s.charAt(i)=='4')break;
if(i>=1){
if(s.charAt(i)=='2'&&s.charAt(i-1)=='6')break;
}
}
return count;
}
static boolean check(int t){
String s=String.valueOf(t);
if(s.contains("62")||s.contains("4"))return false;
return true;
}

}