SP3928 MDIGITS - Counting Digits 题解

题目链接：SP3928 MDIGITS - Counting Digits

题意：

给定两个整数 $a$ 和 $b$，求 $a$ 和 $b$ 之间的所有数字中 $0$ ~ $9$ 出现次数。

例如，$a$ = $1024$，$b$ = $1032$，则 $a$ 和 $b$ 之间共有 $9$ 个数如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中 0 出现 $10$ 次，1 出现 $10$ 次，2 出现 $7$ 次，3 出现 $3$ 次等等……

数位dp的基础题

设 $f_i$ 表示满 $i$ 位数字（包括前导零），每种数字的出现次数
$$\begin{gathered} f_1=1 \\ {f}_i=f_{i-1}\times 10+10^{i-1} \end{gathered}$$
其中 $f_{i-1}\times 10$ 是 $i-1$ 位及以下位的贡献

例如 $7000\sim 7999,8000\sim 8999$

显然 $000\sim 999$出现了 $10$ 次

而 $10^{i-1}$ 是第 $i$ 位的贡献，比如 $9000\sim 9999$ ，第 $4$ 位的 $9$ 出现了 $10^3$ 次

然后我们再考虑怎么获得答案

首先 $[l,r]$ 可以拆分为 $[0,l-1],[0,r]$ 两个询问（基本的容斥）

然后考虑一个数 $\overline{\mathtt{A}\mathtt{B}\mathtt{C}}$ ，不难发现，$0$ 到 $\overline{\mathtt{A}00}$ 每个非最高位数都出现了 $\mathtt{A}$ $\times f_2$ 次

而最高位 $0\sim \mathtt{A}-1$ 都各出现了 $10^2$ 次

注：这里 $0$ 是前导零，所以其实不会算进去，这里只是为了方便分析

那么 $\mathtt{A}$ 呢？不难发现它出现了 $\overline{\mathtt{B}\mathtt{C}}+1$ 次

对于 $\mathtt{B}$ ，同样的处理方式。

怎么一股机翻的味道

然后我们就搞定这道题了

时间复杂度 $O(Qlb)$

其中 $l$ 表示最大位数， $b$ 表示进制，这题里为 $10$

代码：（非dfs写法）

#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 a,b,mi[25],cnt1[25],cnt2[25],num[25],f[25];
void clear()
{
    memset(cnt1,0,sizeof(cnt1));
    memset(cnt2,0,sizeof(cnt2));
}
void solve(int x,int *cnt)
{
    int len=0;
    memset(num,0,sizeof(num));
    while(x)
    {
        num[++len]=x%10;
        x/=10;
    }
    for(int i=len; i>=1; i--)
    {
        for(int j=0; j<=9; j++)
            cnt[j]+=f[i-1]*num[i];
        for(int j=0; j<num[i]; j++)
            cnt[j]+=mi[i-1];
        int res=0;
        for(int j=i-1; j>=1; j--)
        {
            res = res * 10 + num[j];
        }
        cnt[num[i]]+=res+1;
        cnt[0]-=mi[i-1];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    mi[0]=1;
    for(int i=1; i<=18; i++)
    {
        f[i]=f[i-1]*10+mi[i-1];
        mi[i]=10*mi[i-1];
    }
    while(cin >> a >> b)
    {
        if(!a&&!b)return 0;
        if(a>b)swap(a,b);
        clear();
        solve(a-1,cnt1);solve(b,cnt2);
        for(int i=0; i<=9; i++)
            cout << cnt2[i]-cnt1[i] << " \n"[i==9];
    }
    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
56
57
58
59
60
61
62
63
64
65
66
67

转载请说明出处