hdu 2089 不要62

http://acm.hdu.edu.cn/showproblem.php?pid=2089

和hdu 3555 一样，先预处理，从最高位处理。然后减去不符合要求的，就是所求的。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define ll int
 5 using namespace std;
 6 
 7 ll dp[30][3];
 8 int num[30];
 9 
10 void inti()
11 {
12     memset(dp,0,sizeof(dp));
13     dp[0][0]=1;
14     dp[0][1]=0;
15     dp[0][2]=0;
16     for(int i=1; i<30; i++)
17     {
18         dp[i][0]=dp[i-1][0]*9-dp[i-1][1];
19         dp[i][1]=dp[i-1][0];
20         dp[i][2]=dp[i-1][2]*10+dp[i-1][1]+dp[i-1][0];
21     }
22 }
23 
24 
25 ll get(int n)
26 {
27     int cnt=0;
28     while(n)
29     {
30         num[++cnt]=n%10;
31         n=n/10;
32     }
33     num[cnt+1]=0;
34     bool flag=false;
35     ll ans=0;
36     for(int i=cnt; i>=1; i--)
37     {
38         ans+=dp[i-1][2]*num[i];
39         if(flag) ans+=dp[i-1][0]*num[i];
40         if(!flag&&num[i]>4)
41         {
42             ans+=dp[i-1][0];
43         }
44         if(!flag&&num[i]>6)
45         {
46             ans+=dp[i-1][1];
47         }
48         if(!flag&&num[i+1]==6&&num[i]>2)
49         {
50             ans+=dp[i][1];
51         }
52         if(num[i]==4||(num[i+1]==6&&num[i]==2))
53         {
54             flag=true;
55         }
56     }
57     if(flag) ans++;
58     return ans;
59 }
60 int main()
61 {
62     inti();
63     ll n,m;
64     while(scanf("%d%d",&n,&m)!=EOF)
65     {
66         if(n==0&&m==0) break;
67         ll ans=get(m)-get(n-1);
68         printf("%d
",m-n+1-ans);
69     }
70     return 0;
71 }

View Code