2016 ShenYang regional online 1007||hdu 5898 odd-even number （数位dp）
题意：题意说得一点页不清楚。。。意思在询问在区间[l,r]中满足某条件的数。该条件是，该数的任何一段数字是奇数组成的数串必须有偶数长度，任何一段数字是偶数组成的数串必须由奇数长度。
对于样例1，满足条件的29个数字分别是： 2,4,6,8,11,13,15,17,19,31,33,35,37,39,51,53,55,57,59,71,73,75,77,79,91,93,95,97,99.
对于样例2，满足条件的36的数字分别是：
110,112,114,116,118,
130,132,134,136,138
150,152,154,156,158
170,172,174,176,178
190,192,194,196,198
200,202,204,206,208,220
211,213,215,217,219
思路：数位dp.dp[i][j][k]表示长度为i，奇偶性相同的连续由j个，上一个的奇偶性为k.
注意不允许前导0.
其他就是细节了，太久没写数位dp调了好久啊QAQ
1/* ***********************************************
2Author :111qqz
3Created Time :Sun 18 Sep 2016 01:11:37 PM CST
4File Name :code/net/2016/shenyang/1007.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31int digit[40];
32LL dp2[30][30][5];
33LL dfs2(int pos,int cnt,int lst,bool limit,bool prehasnonzero)
34{
35 if (pos==0)
36 {
37 if (lst==1&&cnt%2==0) return 1;
38 if (lst==2&&cnt%2==1) return 1;
39 return 0;
40 }
41 if (prehasnonzero&&!limit&&dp2[pos][cnt][lst]!=-1) return dp2[pos][cnt][lst];
42 int mx = limit?digit[pos]:9;
43 LL res = 0 ;
44 if (!prehasnonzero)
45 {
46 for ( int i = 0 ; i <= mx ; i++)
47 {
48 res+=dfs2(pos-1,i==0?0:1,i==0?0:2-i%2,limit&&i==mx,i==0?false:true);
49 }
50 }
51 else
52 {
53 for ( int i = 0 ; i <= mx ; i++)
54 {
55 if (lst==1&&cnt>0&&cnt%2==0&&i%2==1&&pos==1) continue;
56 if (lst==1&&cnt%2==1&&i%2==0) continue;
57 if (lst==2&&cnt>0&&cnt%2==0&&i%2==1) continue;
58 if (lst==2&&cnt%2==1&&i%2==0&&pos==1) continue;
59 res+=dfs2(pos-1,((i%2==1&&lst==1)||(i%2==0&&lst==2))?cnt+1:1,2-i%2,limit&&i==mx,true);
60 }
61 }
62 if (prehasnonzero&&!limit) dp2[pos][cnt][lst] = res;
63 return res;
64}
65/*
66LL dfs( int pos,int odd,int even,int lst,bool limit, bool prehasnonzero)
67{
68 if (pos==0) return 1;
69 if (prehasnonzero&&!limit&&dp[pos][odd][even][lst]!=-1) return dp[pos][odd][even][lst];
70 int mx = limit?digit[pos]:9;
71 LL res = 0;
72 if (prehasnonzero)
73 {
74 for ( int i = 0 ; i <= mx ; i++)
75 {
76 if (lst==1)
77 {
78 if (odd%2==0&&i%2==1) continue;
79 if (odd%2==1&&i%2==0) continue;
80 }else if (lst==2)
81 {
82 if (even%2==1&&i%2==0) continue;
83 if (even%2==0&&i%2==1) continue;
84 }
85 cout<<"pos:"<<pos<<" i:"<<i<<endl;
86 res += dfs(pos-1,i%2==1?odd+1:0,i%2==0?even+1:0,i%2==0?2:1,limit&&i==mx,true);
87 }
88 }
89 else
90 {
91 for ( int i = 0 ; i <= mx ; i++)
92 {
93 cout<<"pos::"<<pos<<" i:"<<i<<endl;
94 res += dfs(pos-1,i%2==1?1:0,i%2==0?1:0,0,limit&&i==mx,i==0?false:true);
95 }
96 }
97 if (prehasnonzero&&!limit) dp[pos][odd][even][lst] = res;
98 return res;
99} */
100LL solve(LL n)
101{
102 ms(digit,0);
103 int len = 0 ;
104 while (n)
105 {
106 digit[++len] = n;
107 n /= 10;
108 }
109 return dfs2(len,0,0,true,false);
110}
111int main()
112{
113 #ifndef ONLINE_JUDGE
114 freopen("code/in.txt","r",stdin);
115 #endif
116 int T;
117 cin>>T;
118 ms(dp2,-1);
119 int cas = 0 ;
120 while (T--)
121 {
122 LL l,r;
123 scanf("%lld%lld",&l,&r);
124 LL ans = solve(r) - solve(l-1);
125 printf("Case #%d: ",++cas);
126 printf("%lld\n",ans);
127 }
128 #ifndef ONLINE_JUDGE
129 fclose(stdin);
130 #endif
131 return 0;
132}