【題目來源】
https://www.acwing.com/problem/content/3713/
【題目描述】
給定兩個整數 l，r（l≤r），請問 [l, r] 範圍內，滿足數字的任意相鄰兩位差值都恰好為 1，且數字至少有兩位的數有多少個。
【輸入格式】
第一行包含整數 T，表示共有 T 組測試數據。
每組數據佔一行，包含兩個整數 l 和 r。
【輸出格式】
每組數據輸出一行，一個結果。
【輸入樣例】
14 2023
【輸出樣例】
1
17
【數據範圍】
1≤T≤100，
0≤l≤r≤3×10^8
【算法分析】
● 設 f[i][j] 表示長度為 i 最高位為 j 的滿足條件的數字個數。
● 由 for(int i=0; i<=9; i++) f[1][i]=1; 知，長度為 1 且分別以 0~9 開頭的一位數都滿足“任意相鄰兩位差值都恰好為 1”條件。這看起來似乎難以理解。這是因為，從邏輯上講，這個條件描述的是“任意兩個相鄰數字之差為1”。對於一位數來説，它只包含一個數字，不存在“相鄰數字”這個概念，因此條件中的前提“相鄰”並不成立。在數理邏輯中，一個前提為假的命題，其整體可以被視為真（這在邏輯學中稱為“空真”或“虛真”）。所以，在數位DP的初始化中，將一位數視為滿足條件是符合常規處理方式的。
● 計算所有長度為 i 最高位為 j 的“相鄰數字之差恰好為1”的數字個數。
for(int i=2; i<N; i++) {
for(int j=0; j<=9; j++) {
if(j==0) f[i][j]=f[i-1][1];
else if(j==9) f[i][j]=f[i-1][8];
else f[i][j]=f[i-1][j-1]+f[i-1][j+1];
}
}此代碼具體含義如下：
當 j==0 時，f[i][j]=f[i-1][1]，因為數字 0 後面只能接數字 1 才能滿足相鄰數字差為1的條件。
當 j==9 時，f[i][j]=f[i-1][8]，因為數字 9 後面只能接數字 8 才能滿足條件。
對於其他數字 j（1 ~ 8），f[i][j]=f[i-1][j-1]+f[i-1][j+1]，因為 j 後面可以接 j-1 或 j+1 來滿足條件。
● 在本題的數位 DP 解法代碼中，if(n<=0) return 0; 這一邊界條件確實至關重要，它確保了程序在處理非正數輸入時的正確性。
● 核心邏輯解析
（1）變量初始化
cnt：用於累計符合條件的數字個數。
pre：記錄上一位數字的值，初始化為 -1 表示尚未處理任何位。
（2）循環條件與位處理
循環 for(int i=v.size()-1; v.size()>=2 && i>=0; i--) 表示從最高位向最低位遍歷數字的每一位。
條件 v.size()>=2 表明此循環僅處理兩位數及以上的情況，一位數會通過其他邏輯單獨處理。
（3）當前位處理
代碼 int x=v[i]; 表示獲取當前位的實際值。
代碼 int start=(i==v.size()-1)?1:0; 表示確定當前位可以填的數字起始值。如果是最高位，不能為 0，所以 start=1；否則，start=0。
（4）統計當前位小於 x 的情況
for(int j=start; j<x; j++) {
if(pre==-1 || abs(pre-j)==1) {
cnt+=f[i+1][j];
}
}遍歷當前位所有小於 x 的可能值 j。
如果 pre==-1（即當前是第一位），或者當前位 j 與前一位 pre 的差值為 1，則這是一個合法的數字開頭或延續。
f[i+1][j] 表示以 j 作為當前位，剩餘 i+1 位數字的所有合法組合數，並將其累加到 cnt 中。
（5）固定當前位為原數字值 x
if(abs(pre-x)==1 || pre==-1) pre=x;
else break;檢查原數字在當前位的值 x 是否與前一位 pre 滿足差值條件（或 pre==-1 表示是第一位）。
如果滿足，則將 pre 更新為 x，繼續處理下一位。
如果不滿足，説明原數字 n 本身從這一位開始已經不滿足“相鄰數字差為1”的條件，後續所有位也必然不滿足，因此直接 break 退出循環。
（6）統計原數字 n 本身
if(i==0) cnt++;當循環成功處理到最後一位（i==0）且沒有因不滿足條件而 break 時，説明原數字 n 本身也滿足條件，因此 cnt++。
（7）統計所有位數小於原數字 n 的合法數字個數
for(int i=2; i<=v.size()-1; i++) {
for(int j=1; j<=9; j++) cnt+=f[i][j];
}遍歷所有可能的數字長度 i（從 2 到 v.size()-1）。
對於每個長度 i，遍歷所有可能的最高位 j（從 1 到 9，因為最高位不能為 0）。
累加 f[i][j] 的值到 cnt 中，f[i][j] 表示長度為 i 最高位為 j 的“相鄰數字之差恰好為 1”的數字個數。
【算法代碼】
#include <bits/stdc++.h>
using namespace std;
const int N=12;
int f[N][10]; //f[i][j]表示長度為i最高位為j的滿足條件的數字個數
void init() {
for(int i=0; i<=9; i++) f[1][i]=1;
for(int i=2; i<N; i++) {
for(int j=0; j<=9; j++) {
if(j==0) f[i][j]=f[i-1][1];
else if(j==9) f[i][j]=f[i-1][8];
else f[i][j]=f[i-1][j-1]+f[i-1][j+1];
}
}
}
int dp(int n) {
if(n<=0) return 0; //vip
vector<int> v;
while(n) {
v.push_back(n%10);
n/=10;
}
int cnt=0,pre=-1;
for(int i=v.size()-1; v.size()>=2 && i>=0; i--) {
int x=v[i];
int start=(i==v.size()-1)?1:0;
for(int j=start; j<x; j++) {
if(pre==-1 || abs(pre-j)==1) {
cnt+=f[i+1][j];
}
}
if(abs(pre-x)==1 || pre==-1) pre=x;
else break;
if(i==0) cnt++;
}
for(int i=2; i<=v.size()-1; i++) {
for(int j=1; j<=9; j++) cnt+=f[i][j];
}
return cnt;
}
int main() {
init();
int T,le,ri;
cin>>T;
while(T--) {
cin>>le>>ri;
cout<<dp(ri)-dp(le-1)<<endl;
}
}
/*
in:
4
1 10
10 10
1 100
0 300000000
out:
1
1
17
1992
*/
