嘘~ 正在从服务器偷取页面 . . .

CF1036C Classy Numbers 题解

发布日期: 2022-07-05

更新日期: 2022-07-21

文章字数: 480

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;
}