数据结构与算法学习笔记----数位统计DP

数据结构与算法学习笔记----数位统计DP

@@ author: 明月清了个风
@@ first publish time: 2025.2.16

ps⭐️一道数位统计DP题目，比较复杂，代码中需要注意的点比较多，关键的思路是分情况讨论

Acwing 338. 计数问题

[原题链接](338. 计数问题 - AcWing题库)

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

例如，$a=11024,b=1032$，则$a$和$b$之间的$9$个数如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032

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

输入格式

输入包含多组测试数据。

每组测试数据占一行，包含两个整数$a$和$b$。

当读入一行为0 0时，表示输入终止，且该行不作处理。

输出格式

每组数据输出一个结果，每个结果占一行。

每个结果包含十个用空格隔开的数字，第一个数字表示 0出现的次数，第二个数字表示1出现的次数，以此类推。

数据范围

$0<a,b<100000000$

思路

很明显不能直接暴力做，数据范围太大了，这题都关键思路是分情况讨论，并且用到了类似前缀和的思想，对于$[a,b]$中某个数$x$出现的次数，可以通过计算$[1,b]$中出现次数-$[1,a-1]$中出现次数计算。

计算的思路是求出数$x$在每一位上出现的次数，然后进行下面的分情况讨论：

假设我们的$n$是$abcdefg$，统计的数是$x>0$，当前统计其在第四位的数的数量

1. 高位$000\sim abc-1$，第四位取$x$，那么后面的$efg$可以随便取，因此这一类中共有$abc\ast 1000$个
2. 当前三位等于$abc$，对$n$的第四位进行讨论
   1. 若$d<x$，那么范围内不可能有数在这一位是$x$，因此为$0$。
   2. 若$d=x$，则后三位就可以取到$000\sim efg$，共$efg+1$种。
   3. 若$d>x$，则后三位可以取到$000\sim 999$，也就是$1000$种。

还有一种特殊的就是要统计的是$0$的出现次数，这时第一类情况就有变化，因为不能有前导$0$，否则就会出现$0000efg$，因此需要将高位从$001$开始枚举。

当然如果统计的是数$x$在第一位出现的次数，第一类就不存在了，因此需要判断，代码中需要注意。

同时，如果统计的是$0$，那么枚举需要从第二位开始。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int get(vector<int> num, int r, int l)
{
    int res = 0;
    for(int i = r; i >= l; i --)
    {
        res = res * 10 + num[i];
    }
    return res;
}

int pow10(int x)
{
    int res = 1;
    while(x --)
        res *= 10;
    
    return res;        
}

int count(int n, int x)
{
    if(!n) return 0;
    
    vector<int> num;
    while(n)
    {
        num.push_back(n % 10);
        n /= 10;
    }
    
    n = num.size();
    
    int res = 0;
    for(int i = n - 1 -!x; i >= 0; i --) // 枚举这个数在哪一位上，从高位开始
    {
        if(i < n - 1) // 只有不在最高位的时候才有第一类情况
        {
            res += get(num, n - 1, i + 1) * pow10(i);
            if(!x) res -= pow10(i);
        }
        
        if(num[i] == x) res += get(num, i - 1, 0) + 1;
        else if(num[i] > x) res += pow10(i);
    }
    
    return res;
}

int main()
{
    int a, b;
    while(cin >> a >> b, a || b)
    {
        if(a > b) swap(a,b);
        
        for(int i = 0; i < 10; i ++)
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }
    
    return 0;
}