数数 题解

题目分析

本题要求统计在区间 $[L, R]$ 中有多少个正整数，其十进制表示中恰好包含 3 个 数字 $2$。例如 $24122$ 含有三个 $2$，是美丽的；$132$ 只有一个 $2$，不是美丽的。

数据范围：$1 \leq L \leq R \leq 10^6$。由于范围不大，我们可以直接遍历 $L$ 到 $R$ 的每一个数，逐个判断是否满足条件。

解题思路

1. 读入 $L$ 和 $R$。
2. 初始化答案计数器 $ans = 0$。
3. 使用 for 循环从 $L$ 到 $R$，对每一个整数 $i$：
   • 统计 $i$ 的十进制表示中数字 $2$ 的出现次数。
   • 如果次数恰好等于 $3$，则 $ans$ 加 $1$。
4. 输出 $ans$。

核心部分在于如何统计一个整数中数字 $2$ 的个数。通常有两种方法：

• 整数拆分法：反复对 $10$ 取模得到个位，判断是否为 $2$，然后将数字除以 $10$ 丢弃个位，直到数字变为 $0$。
• 字符串法：将数字转换为字符串，遍历字符统计 '2' 的个数。

两种方法在本数据范围下都可以轻松通过，代码实现中通常采用整数拆分法，因为不需要额外的类型转换。

算法说明

以整数拆分法为例，伪代码如下：

function count_two(x):
    count = 0
    while x > 0:
        if x % 10 == 2:
            count = count + 1
        x = x / 10   // 整除
    return count

对于每个数字 $i$，我们调用该函数，若返回值为 $3$，则答案加一。

需要注意一点：当 $i = 0$ 时循环不会进入，但题目保证 $L \geq 1$，所以无需考虑 $0$ 的情况。

时间复杂度分析

• 对于 $L$ 到 $R$ 的每个数，我们需要提取其每一位。一个数最多有 $7$ 位（$10^6$ 是 $7$ 位数），所以单次统计操作最多循环 $7$ 次。
• 总操作次数约为 $(R - L + 1) \times 7$，在最坏情况下（$L = 1, R = 10^6$）大约为 $7 \times 10^6$ 次循环，对于 C++ 等语言完全可以在 1 秒内完成。
• 空间复杂度为 $O(1)$，仅使用了少量变量。

因此该算法简单直接，非常适合初学者理解和实现。

参考代码

下面给出 C++ 代码实现，代码中包含了详细的注释以便理解。

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    int l, r, ans = 0;
6    cin >> l >> r;               // 读入区间左右端点
7
8    for (int i = l; i <= r; i++) {
9        int cnt = 0;             // 统计当前数字中 2 的个数
10        int t = i;               // 用临时变量 t 来拆分，避免改变 i
11        while (t) {
12            if (t % 10 == 2)     // 个位是 2 则计数加一
13                cnt++;
14            t /= 10;             // 丢弃个位
15        }
16        if (cnt == 3)            // 恰好有 3 个 2
17            ans++;
18    }
19
20    cout << ans;                 // 输出答案
21    return 0;
22}

代码解释

• cnt 变量用于记录当前数字 $i$ 中数字 $2$ 的个数，每处理一个新数字时重置为 $0$。
• t 临时保存 $i$ 的值，因为后续需要不断除以 $10$，不能破坏循环变量 $i$。
• while(t) 循环会一直执行直到 t 变为 $0$。在循环体内：
  • t % 10 取出 t 的个位数字，判断是否等于 $2$。
  • t /= 10 将 t 右移一位（十进制下），相当于去掉个位。
• 循环结束后，若 cnt == 3，说明该数字是一个美丽数，答案 ans 加一。
• 最后输出累计结果。

思考与扩展

虽然本题直接枚举即可，但如果数据范围扩大到 $10^9$ 甚至更大，就需要使用数位动态规划（数位 DP）来高效统计。本题作为基础练习，重点在于掌握数位拆分和循环统计的基本技巧，这也是信息学竞赛中非常常用的操作。