luogu-P1554 梦中的统计
GESP C++三级练习，一维数组/字符串练习，难度★★☆☆☆。
luogu-P1554 梦中的统计
题目要求
题目背景
Bessie 处于半梦半醒的状态。过了一会儿，她意识到她在数数，不能入睡。
题目描述
Bessie 的大脑反应灵敏，仿佛真实地看到了她数过的一个又一个数。她开始注意每一个数码（）：每一个数码在计数的过程中出现过多少次？
给出两个整数 和 ，求在序列 中每一个数码出现了多少次。
输入格式
第 行: 两个用空格分开的整数 和 。
输出格式
第 行: 十个用空格分开的整数，分别表示数码 在序列中出现的次数。
输入输出样例 #1
输入 #1
129 137输出 #1
1 10 2 9 1 1 1 1 0 1说明/提示
数据保证，，。
题目分析
解题思路
本题的解题思路如下：
问题本质：
- 统计从M到N的所有整数中，每个数字（0-9）出现的次数
- 需要处理每个数字的每一位
- 最终输出10个数字的出现频次
解题关键：
- 有两种主要解题方法：字符串处理和数学计算
- 字符串法：将数字转换为字符串后逐位处理
- 数学法：通过取模和除法运算分离每一位
实现思路：
- 方法一（字符串处理）：
- 使用to_string()将数字转换为字符串
- 遍历字符串的每一位，统计数字出现次数
- 方法二（数学计算）：
- 通过不断除以10取余，分离数字的每一位
- 使用数组记录每个数字的出现次数
- 方法一（字符串处理）：
复杂度分析：
- 时间复杂度：
- 空间复杂度：，只需要一个固定大小为10的数组
{% include custom/custom-post-content-inner.html %}
示例代码
方法一：转化成字符串处理
#include <iostream>
int main() {
// 定义变量m和n用于存储输入的区间范围
int m, n;
// 从标准输入读取m和n
std::cin >> m >> n;
// 定义长度为10的数组，用于统计0-9每个数字出现的次数
int result[10] = {0};
// 遍历区间[m,n]中的每个数
for (int i = m; i <= n; i++) {
// 将数字转换为字符串，便于分离每一位
std::string s = std::to_string(i);
// 遍历字符串的每一位
for (int j = 0; j < s.length(); j++) {
// 将字符转换为对应的数字并在结果数组中计数
result[s[j] - '0']++;
}
}
// 输出0-9每个数字出现的次数
for (int i = 0; i < 10; i++) {
std::cout << result[i] << " ";
}
return 0;
}
方法二：数学计算法
#include <iostream>
int main() {
// 定义变量m和n用于存储输入的区间范围
int m, n;
// 从标准输入读取m和n
std::cin >> m >> n;
// 定义长度为10的数组，用于统计0-9每个数字出现的次数
int result[10] = {0};
// 遍历区间[m,n]中的每个数
for (int i = m; i <= n; i++) {
// 将当前数字赋值给临时变量t
int t = i;
// 通过不断除以10取余的方式，分离数字的每一位
while (t) {
// t%10得到最低位数字，并在结果数组中对应位置加1
result[t % 10]++;
// 去掉最低位
t /= 10;
}
}
// 输出0-9每个数字出现的次数
for (int i = 0; i < 10; i++) {
std::cout << result[i] << " ";
}
return 0;
}{% include custom/custom-post-content-footer.md %}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。
GESP/CSP 认证学习微信公众号
Last updated on