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.
题意：一个数中所有连续的奇数长度都为偶数，所有连续偶数的长度都为奇数。我们要找一个区间内一共有多少个这样的数。
区间范围（1～9*10^18)所以显然是数位dp搞。设dp[len][count][temp]，temp=1表示偶数，temp=2表示奇数，temp=0表示取首位0时，
count表示到len位置有几个奇数或偶数个。显然简单的搜索，标准数位dp
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll dp[22][22][3];
int dig[20];
ll dfs(int len , int count , int temp , int flag , int first) {
if(len == 0) {
if(temp == 1) {
if(count % 2 != 0) {
return 1;
}
else {
return 0;
}
}
if(temp == 2) {
if(count % 2 == 0) {
return 1;
}
else {
return 0;
}
}
return 0;
}
if(!flag && !first && dp[len][count][temp] != -1) {
return dp[len][count][temp];
}
int n = flag ? dig[len] : 9;
ll sum = 0;
for(int i = 0 ; i <= n ; i++) {
if(first) {
if(i == 0) {
sum += dfs(len - 1 , 0 , 0 , flag && i == n , first && i == 0);
}
else {
if(i % 2 == 0) {
sum += dfs(len - 1 , count + 1 , 1 , flag && i == n , first && i == 0);
}
else {
sum += dfs(len - 1 , count + 1 , 2 , flag && i == n , first && i == 0);
}
}
}
else {
if(i % 2 == 0) {
if(temp == 1) {
sum += dfs(len - 1 , count + 1 , 1 , flag && i == n , first && i == 0);
}
if(temp == 2) {
if(count % 2 == 0) {
sum += dfs(len - 1 , 1 , 1 , flag && i == n , first && i == 0);
}
}
}
else {
if(temp == 1) {
if(count % 2 != 0) {
sum += dfs(len - 1 , 1 , 2 , flag && i == n , first && i == 0);
}
}
if(temp == 2) {
sum += dfs(len - 1 , count + 1 , 2 , flag && i == n , first && i == 0);
}
}
}
}
if(!flag && !first) {
dp[len][count][temp] = sum;
}
return sum;
}
ll Get(ll x) {
int len = 0;
memset(dp , -1 , sizeof(dp));
memset(dig , 0 , sizeof(dig));
if(x == 0)
len = 1;
while(x) {
dig[++len] = x % 10;
x /= 10;
}
return dfs(len , 0 , 0 , 1 , 1);
}
int main()
{
int t;
cin >> t;
int ans = 0;
while(t--) {
ans++;
ll l , r , gg;
cin >> l >> r;
cout << "Case #" << ans << ": " << Get(r) - Get(l - 1) << endl;
}
return 0;
}