P4388 梦中的统计（基础）

解题思路

童童从 m 数到 n，要统计这一串数里数字 0 到 9 各出现了多少次。比如从 15 数到 25，就要把 15、16、17……25 每个数的每一位都看清楚、数一遍。

关键是怎么"拆数"：一个整数怎么一位一位拿出来？办法是用取余和整除：t % 10 得到个位，t / 10 去掉个位。不断重复，直到 t 变成 0，每一位就都拆完了。比如 25：25 % 10 = 5，25 / 10 = 2；2 % 10 = 2，2 / 10 = 0，拆出了 5 和 2。

算法：用一个长度为 10 的计数数组 cnt，对 m 到 n 的每个数做拆位，每拆出一个数字 d 就 cnt[d]++。最后依次输出 cnt[0] 到 cnt[9]。

拿样例验证 m=15、n=25：15 拆出 1 和 5，16 拆出 1 和 6，20 拆出 2 和 0……统计下来 0 出现 1 次、1 出现 6 次、2 出现 7 次……输出 "1 6 7 1 1 2 1 1 1 1"，和样例一致。

边界情况：n 最大是 1000，每个数最多 4 位，计算量很小。注意数字 0 也可能出现在某个数的某一位上（比如 20 的个位是 0），我们统计的是每一位上出现的数字，所以不会漏。m 最小是 1，每个数至少有一位数字。

参考代码

// 程序用途：统计从m到n之间所有整数中数字0~9各出现多少次
#include <iostream>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    int cnt[10] = {0};                // cnt[d]记录数字d出现的次数
    for (int i = m; i <= n; i++) {    // 对每个数i
        int t = i;
        while (t > 0) {               // 把i的每一位都拆出来
            cnt[t % 10]++;            // 个位数字计数加1
            t = t / 10;               // 去掉个位，继续看下一位
        }
    }
    for (int i = 0; i < 10; i++) {    // 依次输出0~9的次数
        if (i > 0) cout << " ";
        cout << cnt[i];
    }
    cout << endl;
    return 0;
}

复杂度分析

从 m 到 n 一共有 n-m+1 个数，每个数最多拆 4 位，所以时间约是 O(n × 4)，也就是 O(n)；计数数组长度固定为 10，额外空间复杂度是 O(1)。