当前位置：网站首页>Cf1036c class numbers solution

Cf1036c class numbers solution

2022-07-06 07:29:00 【q779】

CF1036C Classy Numbers Answer key

The question ： Define a number as “ Good number ”, If and only if its decimal representation does not exceed $3$ A digital $\sim 9$
for instance ： $4, 200000, 10203$ yes “ Good number ”, However $4231, 102306, 7277420000$ No
Given $[l, r]$ , Ask how many $x$ bring $\le x \le r$ , And $x$ yes “ Good number ”
Altogether $\le T \le 10^{4})$ Group data , For each inquiry , Output an integer on a line to represent the answer
$\le l_i \le r_i \le 10^{18}$

General figures dp It can be used to solve $\sum _{i=l}^{r} f(i)$ The problem of ,

among $f (i)$ As with the $i$ A function or determinant related to the digits of

This question is slightly distorted , Then we will naturally record the occurrence of figures

set up $f_{i,j}$ It means full $i$ digit , Yes $j$ A non $0$ position

Using memory search , See the code for details.

#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 Indicates the current number of digits ,st Represents the current j,limit Indicates whether there is a high limit 
int dfs(int u,int st,bool limit)
{
    
    if(!u)return 1;
    if(!limit&&f[u][st]!=INF)
        return f[u][st]; //  Memorize 
    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; //  Just record what has no upper limit 
    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;
}