[暑假集训--数位dp]hdu5898 odd-even number

For a number,if the length of continuous odd digits is even and the length of continuous even digits is odd,we call it odd-even number.Now we want to know the amount of odd-even number between L,R(1<=L<=R<= 9*10^18).

Input

First line a t,then t cases.every line contains two integers L and R.

Output

Print the output for each case on one line in the format as shown below.

Sample Input

  
100    
220 

Sample Output

Case #1: 29
Case #2: 36

题意是要找x，x当中所有连续的奇数段长度是偶数，连续的偶数段长度是奇数，比如1357246

记一下当前这段是奇数还是偶数，这段已经有多长，有没有前导零。如果有前导零那么0可以也出现奇数次

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #include<deque>
 9 #include<set>
10 #include<map>
11 #include<ctime>
12 #define LL long long
13 #define inf 0x7ffffff
14 #define pa pair<LL,LL>
15 #define mkp(a,b) make_pair(a,b)
16 #define pi 3.1415926535897932384626433832795028841971
17 using namespace std;
18 inline LL read()
19 {
20     LL x=0,f=1;char ch=getchar();
21     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
22     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
23     return x*f;
24 }
25 int len;
26 LL l,r;
27 LL f[20][10][20][2];
28 int d[110];
29 inline LL dfs(int now,int dat,int lst,int lead,int fp)
30 {
31     if (now==1)return (lst&1)^(dat&1);
32     if (!fp&&f[now][dat][lst][lead]!=-1)return f[now][dat][lst][lead];
33     LL ans=0;
34     int mx=fp?d[now-1]:9;
35     for (int i=0;i<=mx;i++)
36     {
37         if (i==0)
38         {
39             if (lead)
40             {
41                 if (lead&&now-1!=1)ans+=dfs(now-1,0,0,1,fp&&mx==0);
42                 else if (lead&&now-1==1)ans+=dfs(now-1,0,1,0,fp&&mx==0);
43                 continue;
44             }
45         }
46         if ((i&1)==(dat&1))ans+=dfs(now-1,i,lst+1,0,fp&&i==mx);
47         else if ((dat&1)^(lst&1)||lead)
48         {
49             ans+=dfs(now-1,i,1,0,fp&&i==mx);
50         }
51     }
52     if (!fp)f[now][dat][lst][lead]=ans;
53     return ans;
54 }
55 inline LL calc(LL x)
56 {
57     if (x==-1)return 0;
58     if (x==0)return 1;
59     LL xxx=x;
60     len=0;
61     while (xxx)
62     {
63         d[++len]=xxx%10;
64         xxx/=10;
65     }
66     LL sum=0;
67     sum+=dfs(len,0,len==1,len!=1,d[len]==0);
68     for (LL i=1;i<=d[len];i++)
69     {
70         sum+=dfs(len,i,1,0,i==d[len]);
71     }
72     return sum;
73 }
74 int main()
75 {
76     LL T=read();int cnt=0;
77     memset(f,-1,sizeof(f));
78     while (T--)
79     {
80         l=read();
81         r=read();
82         if (r<l)swap(l,r);
83         printf("Case #%d: %lld
",++cnt,calc(r)-calc(l-1));
84     }
85 }

hdu 5898