第 26 章 工程实现纪律

12 道真题编程题里有 4 道属于"题面把公式和规则写全、照着实现"的题型，不考算法设计，分数全部落在浮点怎么比、怎么舍入、怎么读输入、怎么输出上。这类错误的共同特征是程序照样跑完，只是答案错——静默失败比崩溃危险得多。

学习目标

读完本章，你应当能够：

1. 说明浮点误差的三个来源，并按 数量级 × 运算次数 × 2.2e−16 估算给定数据范围内的噪声量级；
2. 按"大于累加噪声、小于真实可分辨间隙"两条约束选定 EPS，并说明三种容差用途为何不可混用；
3. 写出浮点比较的三种规范写法（判等、判阈值、判严格更优），并说出各自的适用场景与配套遍历顺序；
4. 区分 half-up 舍入与银行家舍入，实现"恰为 .5 时向上取整"，并判断负数下的行为差异；
5. 处理负零 -0.00，并按题面控制组间空行、分隔符、行尾空格与末尾换行；
6. 实现"按空白取词"的输入解析器，应用五条 Python 性能技巧，并判断何时该停止压常数、改为换算法；
7. 按六步流程完成一道规则实现题。

前置知识检查

26.1 浮点表示与误差来源

0.1 + 0.2 得 0.30000000000000004，0.1 + 0.2 == 0.3 为 False。这不是 Python 的缺陷，而是 IEEE 754 双精度的固有性质：64 位被切成 1 位符号、11 位指数、52 位尾数，值为 (−1)^s × 1.f × 2^(e − 1023)，有效精度 53 位二进制位，能精确表示的只有形如 m / 2^k 的二进制小数。0.1 = 1/10 的分母含因子 5，不是 2 的幂，只能存成最接近的近似（真值约 0.10000000000000000555），故相加后显示为 0.30000000000000004。

相减抵消最危险，因为它放大的是相对误差。取 a = 1.0000000000000002（真实值 1 + 2×10⁻¹⁶）、b = 1.0000000000000000，则 a − b = 2.220446049250313e-16。结果本身是精确的，但若 a、b 各有 10⁻¹⁶ 的误差，a − b 的真实值可能是 0，也可能是 4×10⁻¹⁶——结果的相对误差达到 100%。这就是 σ² = E[X²] − μ² 可能算出负数的根因：数据几乎恒定时两项是相近的大数，相减后有效位几乎丢失，连符号都可能翻转。两遍法（偏差平方和）绕开了它——偏差本就落在均值附近，不再有大数相减：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import math


def safe_std(values):
    """两遍法：先求均值，再对偏差求平方和；偏差已在均值附近，不再有大数相减"""
    n = len(values)
    mu = sum(values) / n
    var = sum((x - mu) ** 2 for x in values) / n
    return math.sqrt(max(var, 0.0))                # 浮点下 var 仍可能略负，开方前截断


def naive_std(values):
    """一遍法：常数更小，但数据接近常数时失去精度"""
    n = len(values)
    mu = sum(values) / n
    ex2 = sum(x * x for x in values) / n
    return math.sqrt(max(ex2 - mu * mu, 0.0))

选择依据是"要算几次"：前缀和用一遍法换来 O(1) 的窗口查询，代价是必须为负方差做截断兜底；全局标准差只算一次，用两遍法更稳。

选 EPS 前先估噪声量级，经验公式为 绝对误差量级 ≈ 数量级 × 运算次数 × 2.2e−16。坐标 2 位小数、范围 (0, 100)、约 10³ 次累加时噪声约 100 × 10³ × 2.2e−16 ≈ 2.2e−11，取 EPS = 1e−9 比噪声大 2 个量级；值域 [−10⁹, 10⁹]、n ≤ 10⁴ 时噪声约 10⁹ × 10⁴ × 2.2e−16 = 2.2e−3，1e−9 比噪声小 6 个量级，完全不够用。容差必须按题目数据范围重算。

26.2 EPS 的取值原则

两条约束同时成立才有意义：

1
2
3
4

约束 1（下界）：EPS 必须大于本题的累加噪声量级
                否则"数学上相等"的两个量会被判为不等
约束 2（上界）：EPS 必须小于本题"真实可分辨的最小间隙"
                否则"数学上不等"的两个量会被判为相等

口诀是吸收噪声，不掩真相。常见场景的选值：

整数比较永远不要加容差：把 if a == b 写成 abs(a - b) < 1e-9 无害但无意义；写成 a <= b + 1e-9 更糟——一旦尺度选错（比如写成 1e0），就会把 a = b + 1 误判为相等。容差是浮点的补丁，不是通用习惯。

同一个 EPS 不能承担两种语义，三种用途的尺度不同：

26.3 浮点比较的三种写法

判等：if a == b 在浮点上几乎永远是错的，应写 if abs(a - b) < EPS。唯一例外是两个数是同一条计算路径的同一个值（如 x 与它自身的拷贝）。绝对容差 abs(a - b) < eps 适合量级已知且稳定的场景（如坐标 (0,100)）；相对容差 abs(a - b) <= eps * max(1.0, abs(a), abs(b)) 适合同一公式在不同量级下的比较，max(1, ...) 保证两数都接近 0 时不会过度苛刻。机考中绝大多数情形用绝对容差即可。

判阈值：题面"不超过 ε"（含等于）写 d * d <= eps * eps + EPS_IN；题面"小于 ε"写 d * d < eps * eps - EPS_IN——严格小于要把阈值往里收。易错点：把"严格大于"写成"大于等于"。判据是严格还是非严格，题面一定写清楚了，必须逐字对照。

判严格更优：写 if cost < best_cost - EPS_STRICT: 才改判。语义是只有差距超过噪声才换答案，于是并列时先遍历到的胜出；遍历顺序本来就是按序号升序，就自然实现了"同分取序号靠前"。若题面要"序号靠后"，有两条路径：改判据符号（< 还是 <=）或改遍历顺序——不要同时动两处，否则两个反转互相抵消，推荐固定"升序遍历 + 严格更优"。

26.4 舍入模式：half-up 与银行家舍入

银行家舍入让"上"和"下"各占一半，在大量舍入的统计场景中长期无偏，这是统计正确的选择，但与题面要求的"四舍五入"不符：round(2.5)、round(3.5)、round(0.5)、round(1.5) 依次得 2、4、0、2。所以"恰为 .5 向上"必须自己实现，不能用 round()。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import math


def half_up(x):
    """half-up 取整：2.5 → 3、3.5 → 4、−2.5 → −2；不能用 round()，它是银行家舍入"""
    return int(math.floor(x + 0.5))


def fmt2(x):
    """2 位小数输出，并把负零归一成 0.00"""
    s = f'{x:.2f}'
    return '0.00' if s == '-0.00' else s

逐点验证 floor(x + 0.5)：x = 2.4 得 2、x = 2.5 得 3（恰为 .5 向上）、x = 2.6 得 3、x = −2.5 得 −2。负数时这是"向零舍入"，严格数学意义的四舍五入对负数是"远离零"（应得 −3），须写成 floor(x + 0.5) if x >= 0 else ceil(x - 0.5)，这一处必须先看样例确认。真题里的舍入多半作用在非负量（分数 ×100、量化值）上，此时两种写法等价。

量化场景把这一点变成硬约束。【2026-09-02 编程题 2】要求 a = half_up(s × 2^b)，样例中的 s × 2^b 出现 .5 结尾的值，用 round() 会得到与题面不同的 a，此后 a 与 b 全部对不上。find_b(s) 的写法是：b 越大精度越高，取满足 a ≤ 127 的最大 b；s·2^b 关于 b 单调递增，可行集合是 {b : b ≤ b_max} 这样的前缀，故从 30 往下扫，第一个可行值即最大 b。

中间精度纪律：score = 0.4950001666 时，f'{score:.2f}'（内部按 half-even 舍入）与 f'{math.floor(score * 100 + 0.5) / 100:.2f}'（显式 half-up）都给 '0.50'；但若 score 精确位于 0.495 这类边界，前者可能给出 0.49 而题面要求 0.50，边界敏感的题优先用显式 half-up。

26.5 负零与输出格式纪律

-0.0 == 0.0 为真，但 f'{-0.0:.2f}' 得到 '-0.00'，评测机按字符串比较就会判错。产生原因是"两个应当相等的量相减得到一个负的极小值"，例如 −1e−17 保留 2 位小数时被舍入为 −0.00。两手都要做：数值层在计算末尾加 if abs(x) < EPS: x = 0.0，避免 −0.0 传染到后续计算（−0.0 * 5 = −0.0 会一路传播）；格式化层再用上节的 fmt2 兜底。

输出格式有六个检查项，逐条对照题面：

组间空行的标准写法是"从第二组起补空行"；【2026-09-09 编程题 1】的 KV 缓存题还要在头内用逗号、层内各头之间用空格连接。一次性拼接再写出更好：逐行 print 在 10⁵ 行量级时每次调用都有 I/O 开销，拼成一个字符串一次写出既提速，又便于精确控制末尾换行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def emit(groups):
    """按题面纪律输出：组间空行、行内空格分隔、无行尾空格、末尾恰好一个换行"""
    out = []
    for gi, group in enumerate(groups):
        if gi > 0:
            out.append('')                      # 空字符串就是空行，最后一组后不会多出
        for row in group:
            out.append(' '.join(fmt2(x) for x in row))
    if out:                                     # groups 为空时按题面处理，避免输出空行
        sys.stdout.write('\n'.join(out) + '\n')

同一头的索引用逗号连接、同一层的各头用空格连接时，写成 ' '.join(','.join(map(str, kept[l][h])) for h in range(H)) 即可。

26.6 输入解析与 Python 性能技巧

【2026-09-02 编程题 1】的规则是：若 batch_size / seq_len / d_k < 1 或 window_size ∉ [1, seq_len]，整个输出只有一行 0。关键纪律：校验必须放在读数据之前。 若先读完所有数据再校验，非法输入下的数据格式可能与预期不同（行数不够），读的过程就会抛异常；即使读得下去也白白浪费时间。

早返回还有三种常见形态：空输入（n = 0）输出空结果或不输出；边界退化（所有元素同值）走题面的退化分支，如 σ = 0 时所有 z = 0；除零风险（某列全为 0，s = 0）单独处理，量化值全 0。

【2026-08-26 编程题 2】的输入有一个陷阱：矩阵按行给出，但行边界与逻辑分块不一定对齐，不能假定"一行 = 矩阵的一行"。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import sys


class TokenReader:
    """按空白取词：需要几个数就取几个，跨行自动补齐"""

    def __init__(self):
        self._it = iter(sys.stdin.read().split())

    def ints(self, count):
        return [int(next(self._it)) for _ in range(count)]

    def floats(self, count):
        return [float(next(self._it)) for _ in range(count)]

    def matrix(self, rows, cols, as_float=False):
        vals = self.floats(rows * cols) if as_float else self.ints(rows * cols)
        # 按行优先切分：不管输入怎么折行，逻辑分块都由 rows/cols 决定
        return [vals[r * cols:(r + 1) * cols] for r in range(rows)]

为什么不能用 input() 逐行读：① 行边界是排版而非语义——输入可能合并或拆分行，若假定"读一行 = 得到矩阵的一行"，遇到折行就静默错位，数值都读进来了只是分配错位置，程序照跑答案全错；② 逻辑分块与物理行数不对齐——rows × cols 个数与文件行数本来就可以不同，只有按空白取词对两类情形都正确；③ 性能——input() 每次调用都有 I/O 与缓冲开销，sys.stdin.read().split() 一次读入切词，大输入下快数倍。

边界处理：输入用非空白分隔符（如 CDN 选址题的 0.00,0.00,2.00）时先 sys.stdin.read().replace(',', ' ') 归一化；整数与浮点混排要用对应的转换函数（int 不能解析 "1.0"）；题面不保证输入合法时，next() 越界抛 StopIteration，应捕获后走早返回分支。

技巧 ④ 的三种形态都是"每次循环做一次 O(n) 拷贝"：total += sum(a[i:]) 里的切片是 O(n) 拷贝，整体 O(n²)，改用前缀和把区间和压到 O(1)；result.insert(0, x) 要搬移全部元素，改用 list(reversed(items)) 或 collections.deque；s += x 每次创建新字符串，改用先收集再 ''.join(items)。技巧 ② 的典型落点是并查集：find 里先写 parent = self.parent，循环内不再走属性查找，在 find 被调用 10⁶ 次的题里收益是实打实的。

26.7 规则实现题的标准解题流程

六步流程：第 1 步抄规则——把题面规则逐条抄到纸上，不跳读、不概括，含公式的原样抄，含阈值的标出严格性（> 还是 ≥）；第 2 步列口径清单——对每一步回答"这一步用上一步的结果还是输入的原值"“统计量取自同一份快照吗"“除以 n 还是 n−1““边界处窗口缩小还是补零”；第 3 步写伪代码——写出各步顺序与数据流（哪一步产生哪个数组、下一步读哪个），这一步能提前发现"顺序依赖"类错误；第 4 步编码——按伪代码逐段写，每段加一句注释说明它在实现哪条规则；第 5 步对样例——手工推一遍样例（至少第一个），逐行核对中间结果，不只对最终答案；第 6 步查边界——逐条过下面的清单。

【2026-09-04 编程题 1】是口径纪律最密集的一道题，四阶段的口径如下：

第 ② 条必须"写进新数组”：若就地修改，i = 2 时用 [1,3] 的窗口（原值）平滑了 v[2]，i = 3 时用 [2,4] 的窗口——但 v[2] 已经被改过了。统计量混入了中间结果，与题面"同一份快照"不符，换个遍历方向（从后往前）答案就不同。这类错误的隐蔽性在于"结果看起来合理”：不会崩溃、不会变 NaN，只是在某些测试点上差一点点。

动手前过一遍、提交前再过一遍的自检清单：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

[ ] 边界口径：区间闭还是半开？"不超过"还是"小于"？含不含端点？
[ ] 执行顺序：多阶段题每步用上一步结果还是输入原值？
[ ] 快照一致性：统计量取自同一份快照，不就地边改边算
[ ] 状态口径：多输出题状态写"恰好"而不是"不超过"
[ ] 非法输入早返回：校验在读数据之前
[ ] 舍入方式：half-up（floor(x+0.5)）还是银行家？不能用 round()
[ ] 中间精度：题面的"保留 k 位"只约束输出，中间保持全精度
[ ] 浮点比较：判"严格更优"用 EPS；判"不超过半径"用平方 + 小容差
[ ] 负零：-0.00 归一成 0.00
[ ] 除零与退化：σ = 0、分母为 0、全零列、空簇是否都处理了
[ ] 输出格式：组间空行、分隔符、行尾空格、末尾换行
[ ] 输出排序：题面要求的最终排序做了没有
[ ] 多解并列：用"严格更优才更新"实现"序号靠前/消耗更小"

把本章纪律集中到一段骨架里（half_up、fmt2 用 26.4 的定义），考场先默写结构，再按题面往里填：

 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

def solve(n, w, k, rows):
    """① 参数校验（非法即早返回）；② 逐阶段处理，每步写入新数组；③ 统一格式化输出"""
    if n < 1 or w < 1 or w % 2 == 0 or w > n:   # 校验在任何"依赖这些参数"的读取之前
        return None
    # ── 阶段 1：清洗，只读输入，结果写进新数组 cur ──
    cur, anc, last = [float(r[1]) for r in rows], [-1] * n, -1
    for i in range(n):                           # 正向扫一遍，记下最近一个左锚点
        anc[i] = last
        if rows[i][2] == 0:                      # 锚点只认 q = 0
            last = i
    nxt = -1
    for i in range(n - 1, -1, -1):               # 反向扫，就地完成插值
        a, b = anc[i], nxt
        if rows[i][2] == 2:                      # 只清洗 q = 2 的可疑点
            if a >= 0 and b >= 0:                # 两端都有锚点才做线性插值
                span = float(rows[b][0] - rows[a][0])
                cur[i] = rows[a][1] + (rows[b][1] - rows[a][1]) * (rows[i][0] - rows[a][0]) / span
            elif a >= 0:                         # 只有单侧锚点则取该锚点的值
                cur[i] = float(rows[a][1])
            elif b >= 0:
                cur[i] = float(rows[b][1])
        if rows[i][2] == 0:
            nxt = i
    # ── 阶段 2：窗口统计，只读 cur 这一份快照，结果写进新数组 res ──
    p1, p2 = [0.0] * (n + 1), [0.0] * (n + 1)
    for i in range(n):                           # 前缀和把窗口查询压到 O(1)
        p1[i + 1], p2[i + 1] = p1[i] + cur[i], p2[i] + cur[i] * cur[i]
    half, res = (w - 1) // 2, [0.0] * n
    for i in range(n):
        lo, hi = max(0, i - half), min(n - 1, i + half)      # 边界自动缩小
        m = hi - lo + 1                          # 分母是实际点数，不是 w
        mu = (p1[hi + 1] - p1[lo]) / m
        var = (p2[hi + 1] - p2[lo]) / m - mu * mu            # 总体口径：除以 m
        if var < 0.0:
            var = 0.0                            # 相减抵消可能给出极小负数，开方前截断
        sd = math.sqrt(var)
        res[i] = mu if abs(cur[i] - mu) > k * sd else cur[i]  # 严格大于才判异常
    # ── 阶段 3：全局标准化，两遍法求总体标准差（除以 n，不是 n−1）──
    mean = sum(res) / n                          # 偏差已在均值附近，无大数相减
    sd_all = math.sqrt(sum((x - mean) * (x - mean) for x in res) / n)
    # ── 阶段 4：评分 + 输出，权重用输入给出的原始 q ──
    pw = [1.0 if r[2] == 0 else (0.5 if r[2] == 1 else 0.25) for r in rows]
    denom = sum(pw[i] * abs(res[i]) for i in range(n))
    if denom == 0.0:
        return 0                                 # 分母为 0 的退化分支先返回
    score = 0.0
    for i in range(n):
        z = 0.0 if sd_all == 0.0 else (res[i] - mean) / sd_all   # σ = 0 的退化分支
        score += pw[i] * abs(res[i]) / denom * abs(z)
    return f'{half_up(score * 100)}'            # ×100 后 half-up 取整，再交给 fmt2 输出
    # 实际提交时改为：print(fmt2(half_up(score * 100) / 100))
    # fmt2 的定义见 26.4：f'{x:.2f}'，并把 '-0.00' 归一成 '0.00'

本章小结

自测题

Q1（辨析）题面要求"保留 2 位小数，恰为 .5 时向上取整"。f'{x:.2f}'、f'{round(x, 2):.2f}'、f'{math.floor(x * 100 + 0.5) / 100:.2f}' 三种写法哪些正确？

Q2（估算）某题所有输入是 n ≤ 10⁴ 个浮点数，取值范围 [−10⁹, 10⁹]，需要判断两个"应当相等"的量是否真相等。给出 EPS 的估算过程。

1
2
3

EPS 必须 > 2.2e−3（吸收噪声）
EPS 必须 < 1（不掩真相）
取 EPS = 1e−2  ⟹  比噪声大 4 倍多，比真实间隙小 100 倍   ✓

Q3（设计）输入格式为"第一行 n；接下来给出一个 m × k 的矩阵，按行给出，但行边界可能被任意折行"。写出解析代码，并说明为什么不能用 input() 逐行读。

1
2
3
4
5
6
7
8

class TokenReader:
    def __init__(self):
        self._it = iter(sys.stdin.read().split())
    def ints(self, count):
        return [int(next(self._it)) for _ in range(count)]
    def matrix(self, rows, cols):
        vals = self.ints(rows * cols)
        return [vals[r * cols:(r + 1) * cols] for r in range(rows)]

Q4（诊断）下面代码想实现"输出 m 组结果，组间空行，最后一组后无空行"，指出问题并修正：for b in range(m): 内先逐行 print(' '.join(...))，循环末尾再 print()。

1
2
3
4
5
6
7
8

out = []
for b in range(m):
    if b > 0:
        out.append('')                           # 空字符串就是空行，最后一组后不会多出
    for row in result[b]:
        out.append(' '.join(fmt(x) for x in row))
if out:
    sys.stdout.write('\n'.join(out) + '\n')      # 末尾恰好一个换行

与真题的关联

延伸阅读

• Goldberg, D.《What Every Computer Scientist Should Know About Floating-Point Arithmetic》（ACM Computing Surveys, 1991）——浮点误差的经典综述，相减抵消与容差取值的第一手讨论。
• IEEE Std 754-2019《Standard for Floating-Point Arithmetic》——四种舍入模式的规范定义，银行家舍入的出处。
• Higham, N. J.《Accuracy and Stability of Numerical Algorithms》第 1 章——“两遍法 vs 一遍法"的数值稳定性分析。