還是數(shù)位DP樊零，還是沒做出來我磁，模型是理解得可以了，編碼的時候姿勢不好驻襟，還是沒辦法通過的十性。
要學多點姿勢，還是要多做題目塑悼。
找出[1,N]當中連續(xù)奇數(shù)位長度為偶數(shù)、連續(xù)偶數(shù)位為奇數(shù)的數(shù)字楷掉。
一般的姿勢肯定想到以末尾段數(shù)位的奇偶性和其長度的奇偶性作為狀態(tài)做記憶化搜索厢蒜，本想著統(tǒng)一一下狀態(tài)分類霞势，降成一維狀態(tài)，結果是自作聰明斑鸦，在處理前導零的時候更加麻煩愕贡。
好的姿勢可以避免重復計算非法的前導零，用一個狀態(tài)位標記當前位前面合法連續(xù)串的長度巷屿，這個長度為0的時候說明要么前面非法了固以，要么前面是前導零，都特殊處理就行了嘱巾。
#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){
//邊界條件憨琳，判斷當前考慮的連續(xù)串的數(shù)位奇偶性和長度奇偶性
//這里因為題目不會問到0，所以0當成非法串
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旬昭，說明前面都是前導零篙螟，特殊處理一下
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的時候
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ā)生變化的時候遍略，記得判斷結束的串的合法性
}
}
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;
}
