odd-even number

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

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(l,pre,con,fz)表示前l位，最后一位是pre，并且此时这个pre所在的连通块已经有con个了，fz来区分是不是前导零。
【AC 代码】

//
//Created by just_sort 2016/10/6
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int digit[20];
LL dp[20][2][2][2];
LL dfs(int l,int pre,int con,int fz,bool jud)
{
    if(l == 0){
        if(pre%2 == 0){
            if(con%2 == 0) return 0;
            else return 1;
        }
        else{
            if(con%2 == 0) return 1;
            else return 0;
        }
    }
    if(!jud && dp[l][pre][con][fz]!=-1) return dp[l][pre][con][fz];
    int nex = jud?digit[l]:9;
    LL ret = 0;
    if(fz){
        for(int i = 0; i <= nex; i++){
            ret += dfs(l-1,i%2,1,fz&&(i==0),jud&&(i==nex));
        }
    }
    else if((pre+con)%2 == 1){
        for(int i = 0; i <= nex; i++){
            if((i+pre)%2 == 0){
                ret += dfs(l-1,i%2,(con+1)%2,fz&&(i==0),jud&&(i==nex));
            }
            else{
                ret += dfs(l-1,i%2,1,fz&&(i==0),jud&&(i==nex));
            }
        }
    }
    else{
        for(int i = 0; i <= nex; i++){
            if((i+pre)%2==0){
                ret += dfs(l-1,i%2,(con+1)%2,fz&&(i==0),jud&&(i==nex));
            }
        }
    }
    if(!jud) dp[l][pre][con][fz] = ret;
    return ret;
}
LL f(LL num){
    int pos = 0;
    while(num){
        digit[++pos] = num%10;
        num /= 10;
    }
    return dfs(pos,0,1,true,true);
}
int main()
{
    int T,ks = 1;
    memset(dp,-1,sizeof(dp));
    scanf("%d",&T);
    while(T--)
    {
        LL l,r;
        scanf("%lld%lld",&l,&r);
        printf("Case #%d: %lld\n",ks++,f(r)-f(l-1));
    }
    return 0;
}