numberCalc

2021-11-12

字数统计: 1k字 | 阅读时长≈ 4分

数字计数

题目大意

给定两个正整数 $a$ 和 $b$，求在 $[a,b]$中的所有整数中，每个数码($0,1,2,…,8,9$)各出现了多少次。

思路

其实就是算从$0$到$n$中，每个数出现的次数，再用前缀和的方式去计算区间$[a, b]$。
那么重点就是去计算每个数的出现次数。

Step1

我们用$dp[i]$表示$0$到有$i$个$9$的数中，每个数码的出现个数(考虑前导$0$)，比如$i = 3$，$dp[i]$表示的就是$0$到$999$中，每个数的出现次数。

显然$dp[1] = 1$ ($0$ ~ $9$每个数都出现了一次)
对于$i \ge 2$:

对于一个$i$位数,我们先考虑$[1,i-1]$位的贡献,因为第$i$位数可以选择$0$~$9$中任意一个数，相当于多了$10$种方案,所以$dp[i] += 10 * dp[i-1]$。
我们再考虑第$i$位数的贡献，对于每个数码$x \in [0, 9]$后面$i-1$位都可以任意选择，构成一个$i$位数,故有$10^{i-1}$中选择，所以$dp[i] = 10 * dp[i - 1] + 10^{i - 1}$

我们就~~轻而易举地~~得到了$dp$的递推式。

Step2

那么第二步就是用这个$dp$式去推结果。
我们先举一个例子，比如$7432$这个数.

我们来尝试去构造每个在$[0,7432]$之间的数,依次作为媒介来计算。

如果我们在第四位上选择了$[0,6]$之间的数，那么剩下的三位数就可以任选了，那么剩下的三位数的贡献就是$7 * dp[3]$
假如我们选择了$7$这个数，那么剩下的数就不能任选了，最多选到$432$这个数，在此条件上，我们来计算第四位数的贡献,那么显然如果选择$[0,6]$中数码,那么后面每一位上的数都可以任选,那么显然就有$10^2$种,而选择了$7$,那么后面三位最多选到$432$,所以有$433$种(因为可以全部选$0$)
此时$4$位数已经计算过了,那么就是要计算三位数，就变成了求$[0,432]$之间的数了，所以重复上述过程即可。
处理前导$0$，四位数时,含有前导$0$的数是$[0000,0999]$，共有$10^3$种,$3$位数时,有$[000,099]$,共有$10^2$种,以此类推…

那么具体地到一般情况，假设我们计算$[0,n]$中，每个数码的出现数量。
设$ans[i]$表示数码$i$的出现数量。
我们从$n$的最高位(设之为$cnt$位)开始算，设它的第$i$位为$a[i]$

对于每一位$a[i]$(与上述例子类似):

计算第$[1, i-1]$位数的贡献:第$i$位可选$[0, a[i]]$，剩下位数任选,所以剩下的位数的贡献是$\forall j \in [0, 9]$,$ans[j] += a[i] * dp[i-1]$
计算第$i$位数对答案的贡献:当第$i$位选择$[0, a[i]-1]$之间的数时，后面的所有数位都可以任选,所以答案可以直接计算(即不需要用$dp$数组了),即$\forall j \in [0, a[i] - 1]$,$ans[j] += 10^(i-1)$;当第$i$位选择$a[i]$时,那么后面的数就只能从$0$选到后面几位构成的数了(可以参考下上面的例子),设之为$tmp$,那么$ans[a[i]] += tmp + 1$。

代码

#include <cstdio>
#include <iostream>
#include <map>
#include <cstring>
#include <vector>
using namespace std;

const int maxN = 1005;

long long l, r, dp[maxN], mi[maxN], ans1[maxN], ans2[maxN], a[maxN];

void solve(long long n, long long *ans)
{
    long long tmp = n;
    int cnt = 0;
    while(tmp) {
        a[++cnt] = tmp % 10;
        tmp /= 10;
    }
    for(int i = cnt; i >= 1; --i) {
        for(int j = 0; j <= 9; ++j)
            ans[j] += a[i] * dp[i - 1];
        for(int j = 0; j < a[i]; ++j)
            ans[j] += mi[i - 1];
        n -= mi[i - 1] * a[i];
        ans[a[i]] += n + 1;
        ans[0] -= mi[i - 1];
    }
}

int main()
{
    scanf("%lld%lld", &l, &r);
    mi[0] = 1;
    for(int i = 1; i <= 13; ++i) {
        dp[i] = 10LL * dp[i - 1] + mi[i - 1];
        mi[i] = mi[i - 1] * 10LL;
    }
    solve(r, ans1);
    solve(l - 1, ans2);
    for(int i = 0; i <= 9; ++i)
        printf("%lld ", ans1[i] - ans2[i]);
    return 0;
}

本文作者： 水蓝络合物
本文链接： https://miku39393939.github.io/2021/11/12/numberCalc/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！