【题目来源】
【题目描述】
猫要破除一切障碍，走出光轨区。目前摆在他面前的就有一道难题。
他面前有从 l 到 r 共 r-l+1 个数，光轨区规定，如果一个数的相邻位上的数字之差的绝对值均不超过 k，那么这个数被叫做 AI 数。
光轨区要求猫找出 AI 数的个数，才能放猫离开。请你帮猫解决这个问题。
【输入格式】
输入包含三个整数 l，r，k，含义见上文。
【输出格式】
输出一个整数，表示 Al 数的个数。
【输入样例】
1 13 1
【输出样例】
12
【数据范围】
对于所有评测数据，1≤l≤r≤10^18，0≤k≤8。
【算法分析】
● 本题“暴力法”代码如下所示。
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
LL le,ri,k;
LL cnt;bool cal(string s) {for(int i=1; i<s.size(); i++) {LL t=s[i]-'0'-(s[i-1]-'0');if(abs(t)>k) return false;}return true;
}int main() {cin>>le>>ri>>k;for(LL i=le; i<=ri; i++) {string t=to_string(i);if(cal(t)) cnt++;}cout<<cnt<<endl;return 0;
}/*
in:1 13 1
out:12
*/
由于暴力法时间复杂度达 O(nlogn)，而本题问题规模达 10^18，故求解只过了 1 个样例，得 20 分，其他 4 个样例 TLE。因此，可以考虑“数位DP”算法求解。
● 数位DP（Digit Dynamic Programming）是一种用于解决数字数位相关计数问题的动态规划算法。其核心思想是将数字按位拆解，通过递归或递推的方式处理每一位的选择，并利用记忆化搜索来避免重复计算，从而高效统计满足特定条件的数字数量。
● 数位DP通过记录前导零、数位限制等状态，将问题复杂度降低至 O(log n)，能够处理非常大的数字范围（如 10^18）。其实现通常是将统计 [le, ri] 的问题转化为统计 [1, ri] 和 [1, le-1] 的结果相减。
● 数位DP题型的特点：求某个区间 [le, ri] 内，满足某种性质的数的个数。
● 数位DP问题中经常用到的“组合数”公式：C(i, j)=C(i-1, j-1)+C(i-1, j)
● 状态及状态转移方程
（1）状态：f[i][j] 表示 i 位数的最高位为 j 的 AI 数的个数。
（2）状态转移方程：f[i][j]+=f[i-1][t]
边界：f[1][j]=1（表示所有一位数 0~9 均是 AI 数，计数为 1）。
递推：f[i][j]+=f[i-1][t]（表示 i-1 位数的最高位为 t 的 AI 数个数。）。
【算法代码】
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=20;
LL f[N][N]; //i位数的最高位为j的AI数的个数
LL le,ri,k;void init() {for(int j=0; j<=9; j++) f[1][j]=1; //一位数均是AI数for(int i=2; i<N; i++) //枚举位数for(int j=0; j<=9; j++) //枚举最高位for(int t=0; t<=9; t++) //枚举次高位if(abs(j-t)<=k) f[i][j]+=f[i-1][t];
}LL dp(LL n) {if(n<1) return 0;vector<int> v;while(n) {v.push_back(n%10);n/=10;}reverse(v.begin(), v.end());//统计位数小于v.size()的正整数LL cnt=0,pre=-1;for(int i=1; i<v.size(); i++) {for(int j=1; j<=9; j++) { //最高位非0cnt+=f[i][j];}}//统计位数等于v.size()的合法数bool flag=true; //前缀是否合法for(int i=0; i<v.size() && flag; i++) {int x=v[i];for(int j=(i==0 ? 1:0); j<x; j++) {if(i>0 && abs(j-pre)>k) continue;cnt+=f[v.size()-i][j];}if(i>0 && abs(x-pre)>k) flag=false;else pre=x;}if(flag) cnt++;return cnt;
}int main() {cin>>le>>ri>>k;init();cout<<dp(ri)-dp(le-1)<<endl;return 0;
}/*
in:1 13 1
out:12
*/
【参考文献】