還是數(shù)位DP，還是沒做出來，模型是理解得可以了，編碼的時(shí)候姿勢不好，還是沒辦法通過的。
要學(xué)多點(diǎn)姿勢，還是要多做題目。

找出[1,N]當(dāng)中連續(xù)奇數(shù)位長度為偶數(shù)、連續(xù)偶數(shù)位為奇數(shù)的數(shù)字。
一般的姿勢肯定想到以末尾段數(shù)位的奇偶性和其長度的奇偶性作為狀態(tài)做記憶化搜索，本想著統(tǒng)一一下狀態(tài)分類，降成一維狀態(tài)，結(jié)果是自作聰明，在處理前導(dǎo)零的時(shí)候更加麻煩。
好的姿勢可以避免重復(fù)計(jì)算非法的前導(dǎo)零，用一個(gè)狀態(tài)位標(biāo)記當(dāng)前位前面合法連續(xù)串的長度，這個(gè)長度為0的時(shí)候說明要么前面非法了，要么前面是前導(dǎo)零，都特殊處理就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
using namespace std;

long long dp[25][10][25];
int bit[25];
long long dfs(int pos, int istop, int p, int x){
    if (pos==-1){ 
        //邊界條件，判斷當(dāng)前考慮的連續(xù)串的數(shù)位奇偶性和長度奇偶性
        //這里因?yàn)轭}目不會(huì)問到0，所以0當(dāng)成非法串
        if (x && x%2!=p%2) return 1;
        else return 0;
    }
    if (!istop && dp[pos][p][x]!=-1) return dp[pos][p][x];

    int lastbit = istop ? bit[pos] : 9;
    long long ans = 0;
    for (int i=0;i<=lastbit;i++){
        if (x==0){ 
            //如果考慮的串長度是0，說明前面都是前導(dǎo)零，特殊處理一下
            if (i==0) ans += dfs(pos-1, istop&&i==lastbit, i, 0); //長度還是0
            else ans += dfs(pos-1, istop&&i==lastbit, i, 1); //遇見非零數(shù)位，長度置1
        }
        else { 
            //長度不為0的時(shí)候
            if (p%2 == i%2) ans += dfs(pos-1, istop&&i==lastbit, i, x+1); 
            //如果數(shù)位奇偶性不變，長度加1
            else if (x%2 != p%2) ans += dfs(pos-1, istop&&i==lastbit, i, 1); 
            //數(shù)位奇偶性發(fā)生變化的時(shí)候，記得判斷結(jié)束的串的合法性
        }
    }

    if (!istop) dp[pos][p][x] = ans;
    return ans;
}

long long calc(long long n){
    if (n==0) return 0;
    int cnt = 0;
    while(n){
        bit[cnt++] = n%10;
        n /= 10;
    }
    memset(dp,-1,sizeof(dp));
    return dfs(cnt-1, 1, 0, 0);
}

int main()
{
    int t,kase=0;
    scanf("%d",&t);
    while(t--){
        long long l,r;
        scanf("%I64d%I64d",&l,&r);
        printf("Case #%d: %I64d\n",++kase, calc(r)-calc(l-1));
    }
    return 0;
}