P1554 [USACO06DEC] 梦中的统计 Dream Counting B
题目地址
题目背景
Bessie 处于半梦半醒的状态。过了一会儿，她意识到她在数数，不能入睡。
题目描述
Bessie 的大脑反应灵敏，仿佛真实地看到了她数过的一个又一个数。她开始注意每一个数码（\(0 \ldots 9\)）：每一个数码在计数的过程中出现过多少次？
给出两个整数 \(M\) 和 \(N\)，求在序列 \([M, M + 1, M + 2, \ldots, N - 1, N]\) 中每一个数码出现了多少次。
输入格式
第 \(1\) 行：两个用空格分开的整数 \(M\) 和 \(N\)。
输出格式
第 \(1\) 行：十个用空格分开的整数，分别表示数码 \(0 \ldots 9\) 在序列中出现的次数。
输入输出样例 #1
输入 #1
129 137
输出 #1
1 10 2 9 1 1 1 1 0 1
说明/提示
数据保证，\(1 \leq M \leq N \leq 2 \times 10^9\)，\(0 \leq N-M \leq 5 \times 10^5\)。
代码实现
问题理解： 统计从M到N（包含M和N）的所有整数中，每个数字0-9出现的总次数。
核心算法：
- 遍历区间：从M到N遍历每个整数
- 数字拆分：将每个整数转换为字符串，遍历每个字符(也可以不转换，利用数学方法，处理每一位。但是要注意数字
0,这个特例。)
// 遍历区间内的每个数for (int num = M; num <= N; ++num) {int temp = num;// 处理0的特殊情况if (temp == 0) {count[0]++;continue;}// 逐位统计while (temp > 0) {count[temp % 10]++;temp /= 10;}}
- 计数统计：使用数组res记录每个数字出现的次数
- 输出结果：按格式输出统计结果
时间复杂度：
O((N-M+1) × 平均数字位数)
// C++代码
#include <iostream>using namespace std;int M, N;
string temp_str;
int res[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; // 存储最终计数结果int main()
{cin >> M >> N;for (int i = M; i <= N; ++i){temp_str = to_string(i);for (int j = 0; j < temp_str.length(); ++j){res[temp_str[j] - '0']++;}}for (int i = 0; i < 10; ++i)cout << res[i] << (i < 9 ? " " : "\n");return 0;
}
# python代码1——此版本为cpp翻版
def main():M, N = map(int, input().split())res = [0] * 10 # 存储0-9每个数字出现的次数for i in range(M, N + 1):# 将数字转为字符串，遍历每个字符for digit in str(i):res[int(digit)] += 1# 输出结果，数字之间用空格分隔print(' '.join(map(str, res)))if __name__ == "__main__":main()
# python代码2——使用Python高级特性
from collections import Counterdef main():M, N = map(int, input().split())# 将所有数字拼接成字符串all_digits = ''.join(str(i) for i in range(M, N + 1))# 统计每个字符出现的次数counter = Counter(all_digits)# 构建结果列表，确保0-9每个数字都有计数（即使为0）res = [counter.get(str(i), 0) for i in range(10)]# 输出结果print(' '.join(map(str, res)))if __name__ == "__main__":main()