【深基5.习1】梦中的统计

解题思路

枚举 M～N，每个数反复取模 10 得到末位数字并计数，然后整除 10 去掉末位。

正确性说明

每次恰好统计一个十进制数位，直到数值变为 0；枚举所有整数得到每个数字出现总次数。

易错点

统计的是出现次数，同一个数内重复数字也要多次累计；不用补前导零。

复杂度

区间长度 k、最大数字位数 D，时间 O(kD)，空间 O(1)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long m, n;
    cin >> m >> n;
    long long cnt[10] = {};
    for (long long i = m; i <= n; i++) {
        long long x = i;
        do {
            cnt[x % 10]++;
            x /= 10;
        } while (x);
    }
    for (int d = 0; d < 10; d++) {
        if (d)
            cout << " ";
        cout << cnt[d];
    }
    cout << "\n";
    return 0;
}