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
1 100
110 220
Sample Output
Case #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代码:
#include<bits/stdc++.h>
using 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;
}