HDU 5898 odd-even number 2016年沈阳网络赛 (数位dp)

HDU 5898 odd-even number 2016年沈阳网络赛 (数位dp)

odd-even number

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

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: 29Case #2: 36

Source

​​2016 ACM/ICPC Asia Regional Shenyang Online​​

Recommend

wange2014   |   We have carefully selected several similar problems for you:  ​​5899​​​ ​​5897​​​ ​​5896​​​ ​​5895​​​ ​​5894​​

题意：一个数字，它每个数位上的奇数都形成偶数长度的段，偶数位都形成奇数长度的段他就是好的。问[L , R]中符合的数的个数。 题解：裸的数位dp, 从高到低考虑每个数位, 状态里存下到当前位为止的值的奇偶性和长度奇偶性即可。

设dp[ i ][ j ][ k ]为考虑当前的第 i 位，上一位是奇(1)偶(0)性为 j ，已经连续 k位 。并且考虑有没有前导零。好像数据里没有前导零。flag表示枚举后面的数是否可以任意值（0-9）。

AC代码:

#includeusing namespace std;typedef long long ll;const int N=1010;ll dig[20];//考虑当前的第 i 位，上一位是奇(1)偶(0)性为 j ，已经连续 k位 ，考虑有没有前导零 ll dp[21][2][21];ll dfs(ll now_pos,int parity = 0,int contius = 0,int flag=1, int first_0=1){ if(now_pos==0){ if(parity==1 && (contius&1)) return 0; else if(parity==1 && (contius&1)==0)return 1; else if(parity==0 && (contius&1) ) return 1; else return 0; } //已经搜索过了 if(flag==0 && dp[now_pos][parity][contius] != -1 ) return dp[now_pos][parity][contius]; int n = flag ? dig[now_pos] : 9; ll ans =0; for(int i=0;i<=n;i++) { if(i&1)//奇数 { if(first_0){ //有前导 0 if(i==0) ans+=dfs(now_pos-1,0,0,flag&&i==n, 1); else ans+=dfs(now_pos-1,1,1,flag&&i==n,0); } else if(parity==0)//上一位是偶数 { //连续奇数位 if(contius&1) ans+=dfs(now_pos-1,1,1,flag&&i==n,first_0); } else if(parity==1) //上一位是奇数 { ans+=dfs(now_pos-1,1,contius+1,flag&&i==n,first_0); } } else { if(first_0) { if(i==0) ans+=dfs(now_pos-1,0,0,flag&&i==n, 1); else ans+=dfs(now_pos-1,0,1,flag&&i==n, 0); } else if(parity==0){ ans+=dfs(now_pos-1,0,contius+1,flag&&i==n,first_0); } else if(parity==1){ if((contius&1)==0) ans+=dfs(now_pos-1,0,1,flag&&i==n,first_0); } } } if(flag==0) dp[now_pos][parity][contius] = ans; return ans;}int main(){ int t; int cas=1; ll l ,r; scanf("%d",&t); while(t--) { memset(dp,-1,sizeof(dp)); memset(dig,0,sizeof(dig)); ll ans1=0,ans2=0; ll len1=0,len2=0; scanf("%I64d%I64d",&l,&r),l--; for( len1=0; l ; l/=10) dig[++len1]=l%10; ans1=dfs(len1); for( len2 = 0; r; r/=10) dig[++len2]=r%10; ans2=dfs(len2); printf("Case #%d: %I64d\n",cas++, ans2 - ans1); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。