计数问题-数位统计DP

问题描述

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

输入格式

输入包含多组测试数据。

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

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

输出格式

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

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

解答

#include<bits/stdc++.h>
using namespace std;

// 将数字序列从第l位到第r位转换为一个整数
int toInt(vector<int>& digits, int l, int r) {
    int result = 0;
    for (int i = l; i >= r; --i)
        result = result * 10 + digits[i];
    return result;
}

// 计算10的x次方
int pow10(int x) {
    int result = 1;
    while (x--) result *= 10;
    return result;
}

// 计算在0到n范围内数字x出现的次数
int countX(int n, int x) {
    if (!n) return 0; // 如果n为0，直接返回0
    vector<int> digits; // 存储n的每一位数字
    while (n) { // 分解n到digits向量中
        digits.push_back(n % 10);
        n /= 10;
    }
    n = digits.size();

    int cnt = 0; // 用于累计数字x出现的次数
    for (int i = n - 1 - !x; i >= 0; --i) {
        // 不考虑最高位为0的情况（当x=0时）
        if (i < n - 1) {
            // 当前位之前的数字组合成的数对结果的贡献
            cnt += toInt(digits, n - 1, i + 1) * pow10(i);
            // 如果x为0，需要减去当前位为0时的情况
            if (!x) cnt -= pow10(i);
        }
        // 如果当前位等于x，加上当前位右侧数字组成的数+1
        if (digits[i] == x)
            cnt += toInt(digits, i - 1, 0) + 1;
        // 如果当前位大于x，加上10的i次方
        else if (digits[i] > x)
            cnt += pow10(i);
    }
    return cnt;
}

int main() {
    int a, b;
    while (cin >> a >> b && (a || b)) { // 循环直到输入0 0
        if (a > b) swap(a, b); // 确保a<=b
        for (int i = 0; i < 10; ++i)
            cout << countX(b, i) - countX(a - 1, i) << " \n"[i == 9];
    }
    return 0;
}