[NOIP2010-普及] 数字统计

题目描述

给定区间 $[L, R]$ ，统计其中所有整数的十进制表示里数码 $2$ 出现的总次数。 $1 \le L \le R \le 100000$ 。

思路

设 $f(n)$ 为 $[0,n]$ 中数码 $2$ 的出现次数，答案为 $f(R)-f(L-1)$ 。对每一位把 $n$ 分成高位、当前位、低位三段：前缀小于高位时贡献 高位×权重，前缀等于高位时按当前位与 $2$ 的大小补 权重 / 低位+1 / 0。

参考代码

Python 版：

python

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
35#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 08:45
# update_at: 2026-10-02 08:45

import sys

DIGIT = 2  # 要统计的数字


def count_upto(n: int) -> int:
    """[0, n] 中数字 2 出现的总次数：按位分段计数。"""
    total = 0
    w = 1
    while w <= n:
        # 该位把 [0, n] 分成三段：前缀 higher、当前位 cur、后缀 lower
        higher, cur, lower = n // (w * 10), n // w % 10, n % w
        # 前缀每取一个值，该位贡献整段 w 个 2（前缀 < higher）；
        # 前缀 == higher 时：cur>2 补满 w，cur==2 只到 lower+1，cur<2 没有
        add = w if cur > DIGIT else lower + 1 if cur == DIGIT else 0
        total += higher * w + add
        w *= 10
    return total


def solve() -> None:
    L, R = map(int, sys.stdin.buffer.read().split())
    # 区间计数用前缀差： [L, R] = [0, R] - [0, L-1]
    print(count_upto(R) - count_upto(L - 1))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
35
36
37
38
39
40
41
42
43
44
45
46
47/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:26
 * update_at: 2026-10-06 14:26
 */

#include <iostream>
using namespace std;

typedef long long ll;

const ll DIGIT = 2; // 要统计的数码

// [0, n] 中数码 DIGIT 出现的总次数，按位分段计数
ll count_upto(ll n) {
    ll total = 0;
    for (ll w = 1; w <= n; w *= 10) {
        ll higher = n / (w * 10); // 当前位的高位部分
        ll cur = (n / w) % 10;    // 当前位数字
        ll lower = n % w;         // 当前位的低位部分
        // 前缀 < higher 时该位贡献 w 个 DIGIT
        // 前缀 == higher 时：cur>DIGIT 补 w，cur==DIGIT 只到 lower+1，否则 0
        ll add;
        if (cur > DIGIT) {
            add = w;
        } else if (cur == DIGIT) {
            add = lower + 1;
        } else {
            add = 0;
        }
        total += higher * w + add;
    }
    return total;
}

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

    ll L, R;
    cin >> L >> R;
    // 区间 [L, R] 用前缀差转化为单点求值
    cout << count_upto(R) - count_upto(L - 1) << "\n";
    return 0;
}

[NOIP2010-普及] 数字统计

目录

题目描述

思路

参考代码