python/TangDou/AcWing/ShuWeiDP/338.cpp

#include <bits/stdc++.h>

using namespace std;
int a, b;

// 统计数字n中存在x=[1,9]的个数情况
// 建议结合题解中 78501示例的流程进行代码理解和记忆
int count_x(int n, int x) {
    int res = 0;  // 结果
    int t = n;    // n的副本
    int base = 1; // base=pow(10,?) 基数
    while (t) {   // 数位分离过程中讨论大小关系
        // ① x大于当前数位
        if (t % 10 < x) res += t / 10 * base; // t:最高位到当前位，t/10:最高位到当前位前一位
        // ② x小于当前位,加1
        else if (t % 10 > x)
            res += (t / 10 + 1) * base;
        // ③ x等于当前位
        else
            res += t / 10 * base + (n % base + 1); // 后面的剩余数字+1

        // 数位分离
        t /= 10;    // 前一位
        base *= 10; // 变基
    }
    return res;
}

/**
对于0，稍作修改，
此时只需分成两类，因为不存在当前为小于0的情况，不过每次的最高位要排除全0的情况。
*/
int count_0(int n) {
    int res = 0;  // 结果
    int t = n;    // n的副本
    int base = 1; // base=pow(10,?)
    while (t) {   // 数位分离过程中讨论大小关系
        // ① 当前位等于0
        if (t % 10 == 0) res += (t / 10 - 1) * base + (n % base + 1);
        // ② 当前位大于0
        else
            res += (t / 10) * base;

        // 数位分离
        t /= 10;    // 前一位
        base *= 10; // 变基
    }
    return res;
}

int main() {
    // 输入多组数据，以a=0,或b=0视为终点
    while (cin >> a >> b, a || b) {
        if (a > b) swap(a, b);                      // 这题还可以输入反着的，无聊~
        cout << count_0(b) - count_0(a - 1) << " "; // 单独计算数字0计算结果
        for (int i = 1; i <= 9; i++)                // 输出数字1~9的计算结果
            cout << count_x(b, i) - count_x(a - 1, i) << " ";
        cout << endl;
    }
    return 0;
}