Roundabout Rounding

题意

给定一个整数 $x$ ，令 $P$ 为满足 $10^P \geqslant x$ 的最小整数。

有两种舍入方式：

直接舍入：一次性把 $x$ 舍入到最近的 $10^P$ ；
链式舍入：先舍入到 $10^1$ ，再舍入到 $10^2$ ，一直到 $10^P$ 。

对每个询问 $N$ ，要求统计 $2 \leqslant x \leqslant N$ 中有多少个数，两种舍入结果不同。

思路

暴力模拟

可以先写出直接舍入和链式舍入，然后枚举每个 x 检查。

这个暴力适合小数据，也适合验证最终公式：

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
48
49
50
51
52
53
54
55
56
57
58/**
 * 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-07-11 12:32
 * update_at: 2026-07-11 12:33
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

long long round_to(long long x, long long base) {
    long long rem = x % base;
    if (rem < base / 2) {
        return x - rem;
    }
    return x + base - rem;
}

long long chain_round(long long x, long long target) {
    for (long long base = 10; base <= target; base *= 10) {
        x = round_to(x, base);
    }
    return x;
}

bool is_different(long long x) {
    long long target = 1;
    while (target < x) {
        target *= 10;
    }
    return chain_round(x, target) != round_to(x, target);
}

long long solve_one(long long n) {
    long long ans = 0;
    for (long long x = 2; x <= n; x++) {
        if (is_different(x)) {
            ans++;
        }
    }
    return ans;
}

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

    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        cout << solve_one(n) << '\n';
    }

    return 0;
}

暴力的瓶颈是要枚举 2..N，而 $N$ 最大到 $10^9$ 。

观察规律

先看两位数。

48 链式舍入时：

text

148 -> 50 -> 100

但直接舍入到 100 时，因为十位是 4，结果是 0。

所以 $45 \dots 49$ 都会产生差异，而 44 不会，50 也不会。

三位数时类似：

text

1445..499

四位数时是：

text

14445..4999

也就是说，长度为 $L$ 的有效数正好落在：

text

1(444...4, 499...9]

左端点 444...4 不计入，右端点 499...9 计入。

区间计数

对每一种位数构造：

text

1
2lower = 444...4
upper = 499...9

当前位数对答案的贡献是：

text

1max(0, min(N, upper) - lower)

注意这里没有 +1，因为 lower 本身不计入。

由于 $N \leqslant 10^9$ ，枚举 10 位以内的区间就够了。

代码

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/**
 * 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-07-11 12:32
 * update_at: 2026-07-11 12:33
 */
#include <bits/stdc++.h>
using namespace std;

long long solve_one(long long n) {
    long long ans = 0;
    long long lower = 0; // 当前位数下的 444...4，这个端点本身不算
    long long pow10 = 1;

    for (int len = 1; len <= 10; len++) {
        lower = lower * 10 + 4;
        long long upper = 5 * pow10 - 1; // 当前位数下的 499...9
        long long high = min(n, upper);
        if (high > lower) {
            ans += high - lower;
        }
        pow10 *= 10;
    }

    return ans;
}

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

    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        cout << solve_one(n) << '\n';
    }

    return 0;
}

复杂度

每个询问只枚举常数个十进制位数，时间复杂度 $O(\log N)$ 。

空间复杂度 $O(1)$ 。

总结

这题的核心不是把舍入过程模拟得更快，而是找到会产生差异的数的形态。

链式舍入会从低位把一串 4 推出进位，所以每个位数只需要统计 (444...4,499...9] 这个区间。

目录

题意

思路

暴力模拟

观察规律

区间计数

代码

复杂度

总结