【GESP】C++三级练习 luogu-P1554 梦中的统计

GESP C++三级练习，一维数组/字符串练习，难度★★☆☆☆。

luogu-P1554 梦中的统计

题目要求

题目背景

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$，$N-M \leq 5 \times 10^5$。

---

题目分析

解题思路

本题的解题思路如下：

1. 问题本质：
   • 统计从M到N的所有整数中，每个数字（0-9）出现的次数
   • 需要处理每个数字的每一位
   • 最终输出10个数字的出现频次
2. 解题关键：
   • 有两种主要解题方法：字符串处理和数学计算
   • 字符串法：将数字转换为字符串后逐位处理
   • 数学法：通过取模和除法运算分离每一位
3. 实现思路：
   • 方法一（字符串处理）：
     • 使用to_string()将数字转换为字符串
     • 遍历字符串的每一位，统计数字出现次数
   • 方法二（数学计算）：
     • 通过不断除以10取余，分离数字的每一位
     • 使用数组记录每个数字的出现次数
4. 复杂度分析：
   • 时间复杂度：$O((N-M) \times \log_{10}MAX(M,N))$
   • 空间复杂度：$O(1)$，只需要一个固定大小为10的数组

---

示例代码

方法一：转化成字符串处理

#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;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。