hdu2089 不要62 两解

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxn=1e6+5;
 6 int n,m;
 7 int c[10][10];
 8 int tot,e[10];
 9 template<class t>void red(t &x)
10 {
11     int w=1;
12     x=0;
13     char ch=getchar();
14     while(ch>'9'||ch<'0')
15     {
16         if(ch=='-')
17             w=-1;
18         ch=getchar();
19     }
20     while(ch>='0'&&ch<='9')
21     {
22         x=(x<<3)+(x<<1)+ch-'0';
23         ch=getchar();
24     }
25     x*=w;
26 }
27 void input()
28 {
29     freopen("input.txt","r",stdin);
30     //freopen("output.txt","w",stdout);
31 }
32 void dv(int x)
33 {
34     tot=0;
35     while(x)
36     {
37         e[++tot]=x%10;
38         x/=10;
39     }
40     e[tot+1]=0;
41 }
42 int solve(int x)
43 {
44     dv(x);
45     int ans=0;
46     for(int i=tot;i>=1;--i)
47     {
48         for(int j=0;j<e[i];++j)
49             if(e[i+1]!=6||j!=2)
50                 ans+=c[i][j];
51         if(e[i]==4||(e[i+1]==6&&e[i]==2))
52             break; 
53     }
54     return ans;
55 }
56 int main()
57 {
58     input();
59     c[0][0]=1;
60     for(int i=1;i<=7;++i)
61         for(int j=0;j<=9;++j)
62             for(int k=0;k<=9;++k)
63                 if(j!=4&&!(j==6&&k==2))
64                     c[i][j]+=c[i-1][k]; 
65     while(scanf("%d%d",&n,&m)==2)
66     {
67         if(!n&&!m)
68             break;
69         //memset(c,0,sizeof(c));
70         printf("%d
",solve(m+1)-solve(n));
71     }
72     return 0;
73 }

递推

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+5;
 4 int tot,e[20];
 5 long long c[20][20][2];
 6 int n,m;
 7 template<class t>void red(t &x)
 8 {
 9     int w=1;
10     x=0;
11     char ch=getchar();
12     while(ch>'9'||ch<'0')
13     {
14         if(ch=='-')
15             w=-1;
16         ch=getchar(); 
17     }
18     while(ch>='0'&&ch<='9')
19     {
20         x=(x<<3)+(x<<1)+ch-'0';
21         ch=getchar();
22     } 
23     x*=w;
24 } 
25 void input()
26 {
27     freopen("input.txt","r",stdin);
28 }
29 void dv(int x)
30 {
31     tot=0;
32     while(x)
33     {
34         e[++tot]=x%10;
35         x/=10;
36     }
37     e[tot+1]=0;
38 }
39 long long dfs(int pos,bool limit,bool zero,bool dc,int pre)
40 {
41     if(pos==0)
42         return dc;
43     if(!limit&&zero&&~c[pos][pre][dc])
44         return c[pos][pre][dc];
45     int up=limit?e[pos]:9;
46     int ans=0;
47     for(int i=0;i<=up;++i)
48         ans+=dfs(pos-1,limit&&(i==up),zero||i,dc||i==4||(pre==6&&i==2),i);
49     if(!limit&&zero)
50         c[pos][pre][dc]=ans;
51     return ans; 
52 }
53 long long solve(int x)
54 {
55     dv(x);
56     memset(c,-1,sizeof(c));
57     return dfs(tot,1,0,0,0);
58 }
59 int main()
60 {
61     //input();
62     while(scanf("%d%d",&n,&m)==2&&n&&m)
63         printf("%lld
",m-n+1-solve(m)+solve(n-1));
64     return 0;
65 }

dfs