Roundabout Rounding

同题说明

洛谷 P11449 与 USACO 1443 是同一道题，完整题目解析请见：

usaco-1443 Roundabout Rounding

题意

给定正整数 $N$ ，求 $[2, N]$ 中有多少个整数 $x$ ，使得将 $x$ 直接舍入到 $10^P$ 与链式舍入到 $10^P$ 的结果不同。其中 $P$ 是满足 $10^P \geqslant x$ 的最小正整数。

直接舍入到 $10^b$ ：看从右往左第 $b$ 位数字 $d$ ，若 $d \geqslant 5$ 则加 $10^b$ ，然后把最低 $b$ 位全部置 $0$ 。
链式舍入到 $10^b$ ：先舍入到 $10^1$ ，再舍入到 $10^2$ ，……，最后舍入到 $10^b$ 。

思路

先看暴力模拟，帮助理解两种舍入的区别：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71# brute.py：小数据暴力解，模拟 Bessie 舍入和 Elsie 链式舍入，逐个数检查。
import sys
from functools import reduce

# ==========================================
# 原始写法：按题目描述，提取数位，直观易懂
# ==========================================
def round_to_original(a, b):
    """Bessie 舍入原始版本：将 a 四舍五入到最接近的 10^b。"""
    # 提取第 b 位数字（从右往左）
    digit = (a // (10 ** (b - 1))) % 10
    if digit >= 5:
        a += 10 ** b
    # 把最低的 b 位全部置 0
    a = (a // (10 ** b)) * (10 ** b)
    return a

def chain_round_original(a, b):
    """Elsie 链式舍入原始版本：先舍入到 10^1，再 10^2，...，直到 10^b。"""
    for i in range(1, b + 1):
        a = round_to_original(a, i)
    return a

# ==========================================
# Pythonic 写法：数学简化 + 高阶函数
# ==========================================
def round_to_pythonic(a, b):
    """Bessie 舍入：加半取整法
    (a + 10^b // 2) // 10^b * 10^b
    """
    p = 10 ** b
    return (a + p // 2) // p * p

def chain_round_A(a, b):
    """Elsie 链式舍入（方案 A）：递推维护幂次"""
    p = 10
    for _ in range(b):
        a = (a + p // 2) // p * p
        p *= 10
    return a

def chain_round_B(a, b):
    """Elsie 链式舍入（方案 B）：函数式 reduce 写法"""
    return reduce(round_to_pythonic, range(1, b + 1), a)

def get_P(x):
    """P = 满足 10^P >= x 的最小正整数。"""
    p = 0
    v = 1
    while v < x:
        p += 1
        v *= 10
    return p

def solve():
    data = sys.stdin.buffer.read().split()
    T = int(data[0])
    out = []
    for i in range(1, T + 1):
        N = int(data[i])
        ans = 0
        for x in range(2, N + 1):
            P = get_P(x)
            # 在这里，我们可以自由切换原始写法或 Pythonic 写法进行验证
            if round_to_original(x, P) != chain_round_original(x, P):
                ans += 1
        out.append(str(ans))
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    solve()

这个暴力对每个 $x$ 模拟两种舍入过程，时间复杂度 $O(N \log N)$ ，只能跑小数据。

关键观察

手动枚举小数据可以发现规律：

$P$	不同的 $x$ 范围	个数
2	$[45, 49]$	5
3	$[445, 499]$	55
4	$[4445, 4999]$	555

规律：对于 $P = d$ （ $d \geqslant 2$ ），链式舍入与直接舍入不同的数恰好是：

x \in [L_d,\; U_d] = [4\underbrace{44\ldots4}_{d-2\text{ 个}}5,\; 4\underbrace{99\ldots9}_{d-1\text{ 个}}]

个数为 $\dfrac{5 \times (10^{d-1} - 1)}{9}$ 。

为什么是这个区间

直接舍入到 $10^d$ 只看第 $d$ 位（最高位）。最高位 $\geqslant 5$ 则结果为 $10^d$ ，否则为 $0$ 。
链式舍入会从低位向高位逐级进位。当最高位恰好是 $4$ 时，低位的连锁进位可能把它推成 $5$ ，使链式结果变成 $10^d$ ，而直接舍入仍是 $0$ 。
最高位 $< 4$ 时，即使低位全部进位也推不到 $5$ ；最高位 $\geqslant 5$ 时，直接和链式都得到 $10^d$ 。所以只有最高位 $= 4$ 时才可能不同。
低位需要满足"链式舍入能产生进位"的条件，这恰好是一个递归结构： $d-1$ 位低位数 $\geqslant L_{d-1}$ 时才会进位。

最终做法

对每个 $d$ 从 $2$ 到 $10$ ，预计算 $L_d$ 和 $U_d$ ，然后对每个查询 $N$ ：

\text{ans} = \sum_{d=2}^{10} \max(0,\; \min(U_d, N) - L_d + 1)

其中 $L_d = \dfrac{40 \times (10^{d-1} - 1)}{9} + 5$ ， $U_d = 5 \times 10^{d-1} - 1$ 。

Python 知识

本题用到的 Python 模式与优化：

原汁原味的数位提取：提取第 b 位数字的常见写法是 (a // (10 ** (b - 1))) % 10。将尾部归零的常见写法是 (a // (10 ** b)) * (10 ** b)。这在理解题意时最直观（见 brute.py 中的 round_to_original）。
Pythonic 舍入：加半取整法 Python 的自带 round() 使用的是“银行家舍入法”（遇到 5 向偶数舍入），不符合本题意。可以用数学运算代替复杂的“提取数位”逻辑：要对 $10^b$ 进位并把低位置零，只需：(a + p // 2) // p * p（其中 p = 10**b）。这种写法利用了 // 整除不会产生浮点误差的特性，是处理向下/向上取整和进位的最佳范式。
递推优化或函数式编程（reduce） 在 brute.py 的链式舍入中，如果要在循环中多次计算次幂，用 p *= 10 递推维护代替 10**b 会更快（方案 A）。如果追求极致代码简短，可以使用高阶函数 reduce 将链式调用浓缩为一行（方案 B）。
sys.stdin.buffer.read().split()：一次读入全部输入并按空白切分，比逐行 input() 快很多。参见 Python 竞赛输入输出与字符串处理中"按 token 读取整份输入"一节。
'\n'.join(out)：先把所有答案攒到列表，最后一次性拼接输出，避免多次 print 的开销。

C++ → Python 对照：

C++	Python
`scanf` / `cin`	`sys.stdin.buffer.read().split()`
`printf` / `cout`	`sys.stdout.write('\n'.join(...))`
`long long`	`int`（自动大整数）

模仿清单：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# 1. 一次读入全部 token
data = sys.stdin.buffer.read().split()

# 2. 攒答案再一次性输出
out = []
out.append(str(ans))
sys.stdout.write('\n'.join(out) + '\n')

# 3. 直观写法：提取数位与归零
def round_to_original(a, b):
    digit = (a // (10 ** (b - 1))) % 10
    if digit >= 5: a += 10 ** b
    return (a // (10 ** b)) * (10 ** b)

# 4. Pythonic 进位舍入（加半取整，规避自带 round 的坑）
def round_to_pythonic(a, b):
    p = 10 ** b
    return (a + p // 2) // p * p

# 5. 链式操作（函数式写法）
from functools import reduce
def chain_round(a, b):
    return reduce(round_to_pythonic, range(1, b + 1), a)

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24import sys

def main():
    LU = []
    for d in range(2, 11):
        L = 4 * 10 * (10**(d-1) - 1) // 9 + 5
        U = 5 * 10**(d-1) - 1
        LU.append((L, U))

    data = sys.stdin.buffer.read().split()
    T = int(data[0])
    out = []
    for i in range(1, T + 1):
        N = int(data[i])
        ans = 0
        for L, U in LU:
            if N >= L:
                ans += min(U, N) - L + 1
            else:
                break
        out.append(str(ans))
    sys.stdout.write('\n'.join(out) + '\n')

main()

复杂度

时间：预计算 $O(\log N_{\max})$ ，每个查询 $O(\log N)$ ，总计 $O(T \log N)$
空间： $O(\log N_{\max})$ 存查找表 + $O(T)$ 存输出

总结

这道题的核心是发现"链式进位"的递归结构：只有最高位为 $4$ 且低位足够大时，链式舍入才会通过逐级进位把最高位推过 $5$ 的门槛。找到这个区间后，问题退化为简单的区间计数。

目录

同题说明

题意

思路

关键观察

为什么是这个区间

最终做法

Python 知识

代码

复杂度

总结