题解 | # C. Classy Numbers #

$[数位DP]$

定义 $dp[i][j]$ 表示当前已经填了 $i$ 个数字，并且非 $0$ 数字为 $j$ 时的总方案数。显然 $i$ 的大小不会超过 $25$ ，最多 $3$ 个非零数字，所以 $j$ 不会超过 $3$

求区间 $[l,r]$ 的上等数字，等价于求区间 $[1,r]$ 的个数减去 $[1,l-1]$ 的个数

核心代码：

$pos$ 表示现在已经遍历到第几个位置了，因为 $p[]$ 数组将 $x$ 给一个个拆分了，此时 $p[]$ 从小到大对应的是 $x$ 的个位，十位，百位.....，然后遍历时就只能将 $pos$ 从大到小枚举，这样先枚举高位然后枚举低位

当 $pos=-1$ 时说明数字已经枚举完，显然是一个升等数字，所以返回 $1$ 。

$cnt$ 表示现在存在非 $0$ 数字的个数

$state$ ：枚举上限，因为 $dfs$ 中是先枚举高位，然后枚举低位；例如 $77$ ，如果现在最高位十位枚举的数字是 $7$ ，那么个位就只能枚举 $[0,7]$ ，不能超过原数，若十位枚举的数字是 $6$ ，那么个位就可以是 $[0,9]$ 。显然需要用 $state$ 来判断现在枚举这一位的数字的枚举范围：如果 $state = 1$ ，就可以枚举 $[0,9]$ ，否则只能枚举 $[0,p[pos]]$

这里的 $dp$ 是数位 $dp$ ，记录当前的状态, $dp[][]$ 一开始初始化为 $-1$ ，采用记忆化搜索：如果当前 $state = 1$ 并且 $dp[][]\ne -1$ ，则说明后面的状态已经搜索过了，现在直接使用即可

int dfs(int pos, int cnt, int state){
    if(pos == -1) return 1;
    if(state && dp[pos][cnt] != -1) return dp[pos][cnt];
    int up = (state ? 9 : p[pos]);
    int ans = 0;
    for(int i = 0; i <= up; i ++){
        if(cnt + (i != 0) >= 4) break;
        ans += dfs(pos - 1, cnt + (i != 0), state || (i < up));
    }
    if(state) dp[pos][cnt] = ans;
    return ans;
}

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 25;
int dp[N][5], p[N];


int dfs(int pos, int cnt, int state){
    if(pos == -1) return 1;
    if(state && dp[pos][cnt] != -1) return dp[pos][cnt];
    int up = (state ? 9 : p[pos]);
    int ans = 0;
    for(int i = 0; i <= up; i ++){
        if(cnt + (i != 0) >= 4) break;
        ans += dfs(pos - 1, cnt + (i != 0), state || (i < up));
    }
    if(state) dp[pos][cnt] = ans;
    return ans;
}
int work(int x){
    int pos = 0;
    while(x){
        p[pos ++] = x % 10;
        x /= 10;
    }
    return dfs(pos - 1, 0, 0);
}
void solve(){

    memset(dp, -1, sizeof(dp));
    int l, r; cin >> l >> r;
    cout << work(r) - work(l - 1) << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    cin >> tt;
    while(tt --) solve();
    return 0;
}