HDU 5898 odd-even number - dblank

# HDU 5898 odd-even number

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

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
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

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
const int N = 300+10, inf = 0x3f3f3f3f;
typedef long long ll;
int digit[25], cnt;
ll dp[25][25][2][2];
ll dfs(int pos, int pre, int len, int lim, int zero)
{
if(pos<=0) return (pre&1)!=(len&1);
if(!lim && dp[pos][len][pre][zero]!=-1) return dp[pos][len][pre][zero];
int End = lim ? digit[pos] : 9;
ll res = 0;
for(int i = 0; i<=End; i++)
{
if(zero)
{
if(i == 0)
res += dfs(pos-1, 0, 0, lim && i == End, 1);
else res += dfs(pos-1, i&1, 1, lim && i ==End, 0);
}
else
{
if(i & 1)
{
if(pre & 1)
{
res += dfs(pos-1, 1, len+1, lim && i == End, 0);
}
else if(len&1)
{
res += dfs(pos-1, 1, 1, lim && i == End, 0);
}
}
else
{
if(!(pre & 1))
{
res += dfs(pos-1, 0, len+1, lim && i == End,0);
}
else if(!(len & 1))
{
res += dfs(pos-1, 0, 1, lim && i == End, 0);
}
}
}
}
if(!lim) dp[pos][len][pre][zero] = res;
return res;
}
ll solve(ll x)
{
//  int cnt = 0
cnt = 0;
//  if(x == 0)
//   return 1;
while(x)
{
digit[++cnt] = x%10;
x/=10;
}
return dfs(cnt, 0, 0, 1, 1);
}
int main()
{
memset(dp, -1, sizeof(dp));
int t;
ll n, m;
cin>>t;
for(int cas = 1; cas<=t; cas++)
{
scanf("%I64d%I64d", &n, &m);
printf("Case #%d: ",cas);
printf("%I64d\n",solve(m)-solve(n-1));
}
return 0;
}