首页 > 代码库 > hdu 5898 odd-even number 数位DP

hdu 5898 odd-even number 数位DP

odd-even number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 716    Accepted Submission(s): 385


Problem Description
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
2 1 100 110 220
 

 

Sample Output
Case #1: 29
Case #2: 36
 
思路:数位DP的递归出口为pos = 0,这时只能判断DP状态末尾的情况,即对于构造一个数来说只能判断最低的奇偶相同的几位,那么如何才能知道中间是否有不符合的情况?
这就需要设置两个变量,一个表示第pos的奇偶性,一个表示以pos位为末尾的中间状态的长度。不过还在中间加上了一个前导0的标识zero.这个只为编码的方便,其实可以特判出是否为前导0的;
ps:说到底还是套路题....
  1 #include<iostream>  2 #include<cstdio>  3 #include<algorithm>  4 #include<queue>  5 #include<set>  6 #include<vector>  7 #include<map>  8 #include<cstring>  9 #include<string> 10 #include<cmath> 11 using namespace std; 12 #define MS1(a) memset(a, -1, sizeof(a)) 13 #define MS0(a) memset(a, 0,sizeof(a)) 14 #define rep1(i,a,b) for(int i = a; i <= b; i++) 15 #define rep0(i,a,b) for(int i = a; i < b; i++) 16 #define rep_0(i,a,b) for(int i = b; i > a; i--) 17 #define rep_1(i,a,b) for(int i = b; i >= a; i--) 18 #define inf 0x3f3f3f3f 19 #define INF 0x3f3f3f3f3f3f3f3f 20 #define bit(p) (1<<p) 21 #define bitnum(a) __builtin_popcount(a) 22 #define lowbit(x) (x&(-x)) 23 #define eps 1e-8 24 #define mod 1000000007 25 typedef pair<int,int> PII; 26 #define ll long long 27 #define ull unsigned long long 28 #define uint unsigned int 29 #define lson l, m, rt << 1 30 #define rson m+1, r, rt << 1|1 31 #define MK make_pair 32 #define A first 33 #define B second 34 #define pb(a) push_back(a) 35 #define zero(x) (((x)>0?(x):-(x))<eps) 36 template<typename T> 37 void read1(T &m) 38 { 39     T x = 0,f = 1;char ch = getchar(); 40     while(ch <0 || ch >9){ if(ch == -) f = -1;ch=getchar(); } 41     while(ch >= 0 && ch <= 9){ x = x*10 + ch - 0;ch = getchar(); } 42     m = x*f; 43 } 44 template<class T1, class T2> 45 void read2(T1 &a,T2 &b){read1(a);read1(b);} 46 template<class T1, class T2, class T3> 47 void read3(T1 &a,T2 &b,T3 &c){read1(a);read1(b);read1(c);} 48  49 template<class T1, class T2> 50 inline void gmax(T1& a, T2 b){ if(a < b) a = b; } 51 template<class T1, class T2> 52 inline void gmin(T1&a , T2& b){ if(a > b) a = b; } 53  54 void debug(ll bug) { cout<<"**** "<<bug<<endl;} 55 void bug(){ puts(" **** bug"); } 56 void ok(){ puts(" **** ok"); } 57 int bit[20]; 58 ll dp[20][2][20][2]; 59 ll dfs(int pos, int odd_even, int len, int zero, int on) 60 { 61     if(pos == 0) return odd_even^(len&1); 62     ll ans = dp[pos][odd_even][len][zero]; 63     if(!on && ans != -1) return ans; 64     int e = on?bit[pos]:9; 65     ans = 0; 66     for(int i = 0; i <= e; i++){ 67         if(zero == 1){ 68             if(i == 0) ans += dfs(pos-1, 0, 0, 1, 0); 69             else ans += dfs(pos-1, i&1, 1, 0, on && i == e); 70             //cout<<i<<" "<<ans<<endl; 71         } else { 72             if(i & 1){ 73                 if(odd_even & 1) ans += dfs(pos-1, odd_even, len+1, 0, on && i == e); 74                 else if(len & 1) ans += dfs(pos-1, odd_even^1, 1, 0, on && i == e); 75             } else { 76                 if(odd_even % 2 == 0) ans += dfs(pos-1, odd_even, len+1, 0, on && i == e); 77                 else if(len % 2 == 0) ans += dfs(pos-1, odd_even^1, 1, 0, on && i == e); 78             } 79         } 80     } 81     if(!on) dp[pos][odd_even][len][zero] = ans; 82     return ans; 83 } 84 ll calc(ll x) 85 { 86     int top = 0; 87     while(x){ 88         bit[++top] = x%10; 89         x /= 10; 90     } 91     return dfs(top, 0, 0, 1, 1); 92 } 93 int main() 94 { 95     MS1(dp); 96     int T, kase = 1; 97     cin >> T; 98     while(T--){ 99         ll L, R;100         read2(L,R);101         printf("Case #%d: %lld\n",kase++,calc(R) - calc(L-1));102     }103     return 0;104 }

 

 

hdu 5898 odd-even number 数位DP