CF1036C Classy Numbers 题解

题目链接：CF1036C Classy Numbers

题意：定义一个数字是“好数”，当且仅当它的十进制表示下有不超过$3$个数字$1\sim 9$

举个例子：$4,200000,10203$是“好数”，然而$4231,102306,7277420000$不是

给定$[l,r]$，问有多少个$x$使得$l\le x\le r$，且$x$是“好数”

一共有$T(1\le T\le 10^4)$组数据，对于每次的询问，输出一行一个整数表示答案

$1\le l_i\le r_i\le 10^{18}$

一般数位dp可以用来解决 ${\sum }_{i=l}^{r}f(i)$ 的问题，

其中 $f(i)$ 为与 $i$ 的数位有关的某个函数或判定式

这题稍微变形了一下，那我们就理所当然地记录一下出现数字的情况

设 $f_{i,j}$ 表示满 $i$ 位数，有 $j$ 个非 $0$ 位

采用记忆化搜索，详见代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()
int num[25],f[25][5];
// u表示当前位数，st表示当前的j，limit表示是否有高位限制
int dfs(int u,int st,bool limit)
{
    if(!u)return 1;
    if(!limit&&f[u][st]!=INF)
        return f[u][st]; // 记忆化
    int up=limit?num[u]:9,ans=0;
    for(int i=0; i<=up; i++)
    {
        if(!i)ans+=dfs(u-1,st,limit&&num[u]==i);
        else if(st!=3)ans+=dfs(u-1,st+1,limit&&num[u]==i);
    }
    if(!limit) f[u][st]=ans; // 只需记录无高位限制的
    return ans;
}
int solve(int x)
{
    int len=0;
    while(x>0)
    {
        num[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,1);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(f,0x3f,sizeof(f));
    int Q;cin >> Q;
    while(Q--)
    {
        int l,r;
        cin >> l >> r;
        cout << solve(r)-solve(l-1) << '\n';
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

参考文献

[1] https://www.luogu.com.cn/blog/rated/solution-cf1036c

转载请说明出处