[NOIP 2010 普及组] 数字统计

题意

给定一个区间 [L, R]，要求统计这个区间里所有整数的十进制表示中，数字 2 一共出现了多少次。

例如区间 [2, 22] 中：

2 里有一个 2
12 里有一个 2
20、21 各有一个 2
22 里有两个 2

把这些次数全部加起来就是答案。

思路

先看一个最容易理解的朴素解：

枚举区间里的每一个数，把它转成字符串，然后数一数里面有几个字符 '2'。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int l, r;

int count_two(int x) {
    string s = to_string(x);
    int cnt = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '2') {
            cnt++;
        }
    }
    return cnt;
}

void solve() {
    int ans = 0;
    for (int i = l; i <= r; i++) {
        ans += count_two(i);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> l >> r;
    solve();

    return 0;
}

这份暴力已经可以通过本题，因为数据范围只有 1e5。

正式代码只是在“统计单个数里有几个 2”这一步换成了更贴近数位本质的写法：

用 x % 10 取出当前最后一位
如果这一位等于 2，计数加一
再用 x /= 10 删掉最后一位

这样不断拆位，直到这个数变成 0 为止。

最后把区间 [L, R] 中每个数贡献的 2 的个数累加起来即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#include <bits/stdc++.h>
using namespace std;

int l, r;

// 统计单个整数中数字 2 出现了多少次。
int count_two(int x) {
    int cnt = 0;
    while (x > 0) {
        if (x % 10 == 2) {
            cnt++;
        }
        x /= 10;
    }
    return cnt;
}

void solve() {
    int ans = 0;
    for (int i = l; i <= r; i++) {
        ans += count_two(i);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> l >> r;
    solve();

    return 0;
}

复杂度

设区间长度为 n = R - L + 1，每个数最多处理若干十进制位，所以时间复杂度是 $O(n log R)$ ，空间复杂度是 $O(1)$ 。

总结

这题本质上就是“枚举 + 数位拆分统计”。

重点不是设计复杂算法，而是把“统计一个数里某个数字出现次数”这个子问题写清楚，然后顺着区间累加。

[NOIP 2010 普及组] 数字统计

目录

题意

思路

代码

复杂度

总结