# 第 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` 的位布局讲起 |
| 有效数字与数量级的估算 | 26.1 节给出误差量级公式与两个算例 |
| Python 的 `round`、`math.floor`、格式化输出 | 26.4 节给出舍入对照与逐点验证 |
| `sys.stdin` 与逐行 `input()` 的差别 | 26.6 节给出三条理由与五条性能技巧 |
| 列表推导、局部变量与属性查找的开销 | 26.6 节给出五条技巧与反例 |
| 前缀和、并查集等第 22~25 章的工具 | 本章不涉及算法设计，只讲实现纪律 |

## 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`。

> [!IMPORTANT]
> 浮点数不是实数，而是实数的一个有限子集。任何"数学上相等"的断言，在浮点下都必须写成"差不超过 `EPS`"。题面写"精确输出 2 位小数"，暗含"你的计算误差要在 `1e−2` 的半个单位以内"。

| 误差来源 | 机制 | 典型量级（双精度） | 表现 |
|---|---|---|---|
| 表示误差 | 十进制小数无法精确表示为二进制 | 约 `1e−16`（相对） | `0.1` 存进去就不准 |
| 舍入误差 | 每次算术运算的结果被舍入到最近的可表示值 | 每次约 `1e−16`，累加 `n` 次后约 `n·1e−16` | 长求和偏离真值 |
| **相减抵消** | 两个相近的大数相减，有效位大量丢失 | 可能放大到 `1e−10` 以上 | `E[X²] − μ²` 算出负方差 |

**相减抵消最危险，因为它放大的是相对误差**。取 `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²] − μ²` 可能算出负数的根因：数据几乎恒定时两项是相近的大数，相减后有效位几乎丢失，连符号都可能翻转。两遍法（偏差平方和）绕开了它——偏差本就落在均值附近，不再有大数相减：

```python
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))
```

| 做法 | 时间 | 数值稳定性 | 适用场景 |
|---|---|---|---|
| 一遍法 `E[X²] − μ²` | `O(n)` | 差（数据接近常数时失效） | 需要 `O(1)` 任意窗口查询时 |
| 两遍法（偏差平方和） | `O(2n)` | 好 | 只需算一次全局统计量时首选 |

选择依据是"要算几次"：前缀和用一遍法换来 `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（下界）：EPS 必须大于本题的累加噪声量级
                否则"数学上相等"的两个量会被判为不等
约束 2（上界）：EPS 必须小于本题"真实可分辨的最小间隙"
                否则"数学上不等"的两个量会被判为相等
```

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

| 场景 | 噪声量级 | 真实最小间隙 | 推荐 `EPS` |
|---|---|---|---|
| 坐标 2 位小数、值域 `(0,100)` 的距离比较 | `1e−15` ~ `1e−11` | `1e−4`（`0.01²`） | `1e−7` |
| 距离/代价比较，判"严格更优" | `1e−15` ~ `1e−10` | `1e−2` 量级 | `1e−9` |
| 输出 2 位小数的浮点求和 | `1e−14` | `1e−2` | `1e−9` |
| 大数量级（`10⁹`）求和 | `1e−3` | 视题面 | 按上节重算，可能到 `1e−1` |
| 整数比较 | 无 | 1 | **`0`**（不要加容差） |

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

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

| 用途 | 判据形式 | 尺度 | 为什么不同 |
|---|---|---|---|
| 判"落在阈值内" | `d <= threshold + EPS_IN` | 较大（`1e−7`） | 要吸收"恰好相切"的误差，误差方向不确定，宁可宽一点 |
| 判"严格更优" | `d < best - EPS_STRICT` | 较小（`1e−9`） | 只需排除末位噪声，不能吞掉真实差距 |
| 判"两数相等" | `abs(a - b) < EPS_EQ` | 中等（`1e−9`） | 语义就是"应当相等" |

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

| 场景 | 写法 | 配套遍历顺序 |
|---|---|---|
| 判两个值是否相等 | `abs(a - b) < EPS` | 无关 |
| 判是否落在阈值内 | `v <= threshold + EPS_IN` | 无关 |
| 判是否严格超出阈值 | `v > threshold + EPS_IN` | 无关 |
| 判严格更优（保序号靠前） | `v < best - EPS_STRICT` | 升序 |
| 判严格更优（保序号靠后） | `v <= best + EPS_STRICT` | 升序 |

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

| 舍入模式 | 规则 | `.5` 处的行为 | 偏差 | 使用者 |
|---|---|---|---|---|
| half-up（四舍五入） | 绝对值 ≥ `.5` 时向上进位 | `2.5 → 3`，`3.5 → 4` | 系统性偏大 | 数学与题面常用 |
| half-even（银行家舍入） | `.5` 时取最近的**偶数** | `2.5 → 2`，`3.5 → 4` | 无系统偏差 | IEEE 754 默认、Python `round` |

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

```python
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**。

> [!IMPORTANT]
> 【2026-09-02 编程题 1】里"归一化权重保留 6 位小数"是**展示精度，不是计算步骤**。样例 1 末行真实权重是 `0.4950001666`，直接乘 V 再进位得 `0.50`；若先量化成 `0.495000` 再乘 V，会输出 `0.49` 和 `0.51`。一般规则：题面里的"保留 k 位"只约束最终输出，中间计算一律保持全精度。

## 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` 兜底。

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

| 检查项 | 常见要求 | 实现要点 |
|---|---|---|
| **组间空行** | 多组结果之间空一行，**最后一组后面不空** | 从第二组起 `print()`，而不是每组后面 `print()` |
| **分隔符** | 同行内空格 / 逗号 | `' '.join(...)` 或 `','.join(...)`，看清题面用的是哪个 |
| **行尾空格** | 不留多余空格 | 用 `join`，而不是循环 `print(x, end=' ')` |
| **末尾换行** | 多数要求有，少数要求无 | `print()` 自带换行；要无换行用 `end=''` |
| **负零** | 归一为 `0.00` | 数值层归零 + 格式化层兜底 |
| **输出排序** | 按要求重排 | 如"按 `(x, y)` 升序""索引升序" |

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

```python
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。

> [!WARNING]
> "先校验还是后校验"是规则实现题的高频分差点。自检方法：在纸上写出输入格式的完整读取顺序，然后把校验语句插到第一个"依赖被校验参数"的读取动作之前。若某个参数被用来决定"要读多少行"，校验就必须在它之前。

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

```python
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`，应捕获后走早返回分支。

| 技巧 | 做法 | 收益 | 说明 |
|---|---|---|---|
| ① 列表推导替代显式 `for` + `append` | `[f(x) for x in a]` | 快 2~3 倍 | 循环在 C 层执行 |
| ② 把全局量绑定到局部变量 | `p = self.parent` 后在循环里用 `p` | 快 1.2~1.5 倍 | 局部变量查表比全局/属性查找快 |
| ③ `sys.stdin` 一次读入 | `sys.stdin.read().split()` | 大输入下快数倍 | 避免 `input()` 的逐行调用 |
| ④ 避免隐式的 `O(n²)` 拷贝 | 不用 `a[i:j]` 做累加、不用 `list.insert(0, x)` | 可能改变量级 | **最容易忽视的一条** |
| ⑤ 输出一次性拼接 | `sys.stdout.write('\n'.join(out))` | 大输出下快数倍 | 避免逐行 I/O |

技巧 ④ 的三种形态都是"每次循环做一次 `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⁶` 次的题里收益是实打实的。

> [!IMPORTANT]
> 性能技巧不能改变量级。算法本身是 `O(N²)` 时，把循环体优化 3 倍仍然超时（`10¹⁰ / 3 ≈ 3×10⁹`，远超 `10⁷`）。正确顺序是：先用第 22 章的标尺判断量级是否达标；不达标就换算法（性能技巧帮不上忙）；达标但常数偏大，才用五条技巧压常数。

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

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

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

| 阶段 | 口径问题 | 正确答案 | 错误做法的后果 |
|---|---|---|---|
| ① 清洗 | 插值的锚点认哪些记录？ | **只认 `q = 0`**；`q = 1` 既不清洗也不当锚点 | 把可疑值也当锚点，插值结果整体偏移 |
| ② 异常检测 | 窗口统计量取自哪一份数据？ | **第一步清洗后的同一份快照** | 就地平滑会污染后续窗口，答案随遍历方向变化 |
| ③ 标准化 | 标准差用什么口径？ | **总体口径**（除以 `n`，不是 `n−1`） | `n` 较小时差异显著（`n = 3` 时差 22%） |
| ④ 评分 | 权重 `pw` 用哪个 `q`？ | **输入给出的原始 `q`** | 被插值处理过的点若改用自己的旧标记，权重错 |

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

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

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

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

```python
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'
```

## 本章小结

| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| 浮点不是实数 | `0.1 + 0.2 != 0.3`，任何"相等"都要写成"差不超过 `EPS`" | 用 `==` 比较两个算出来的浮点数 |
| 三类误差 | 表示误差、舍入误差累加、相减抵消最危险 | 只考虑表示误差，忽略累加与抵消 |
| 相减抵消 | `E[X²] − μ²` 在数据接近常数时可能算出负数 | 直接开方，`math.sqrt` 抛 `ValueError` |
| 两遍法 | 只算一次的全局统计量用两遍法；`O(1)` 窗口查询才用一遍法 | 一律用一遍法，牺牲精度换不需要的速度 |
| `EPS` 两条约束 | 大于累加噪声、小于真实可分辨间隙 | 照抄 `1e−9` 而不按数据范围重算 |
| 容差用途不可混用 | 判阈值 `EPS_IN`、判严格更优 `EPS_STRICT`、判相等 `EPS_EQ` | 用同一个 `EPS` 处理两种语义 |
| 整数不加容差 | 整数比较就是精确比较 | 给整数比较加浮点容差 |
| 严格更优 | `v < best − EPS` + 升序遍历 ⟹ 并列取先遇到者 | 裸写 `<`，同分胜负由末位误差决定 |
| 舍入模式 | Python `round()` 是银行家舍入，half-up 要写 `floor(x + 0.5)` | 直接用 `round()`，`.5` 处与题面不符 |
| 负数 half-up | `floor(x + 0.5)` 对负数是"向零"，要"远离零"须另写 | 未看样例就假定负数行为 |
| 中间精度 | 题面的"保留 `k` 位"只约束输出 | 把中间结果先量化再继续算，误差累积 |
| 负零与格式 | 数值层归零 + `fmt2` 兜底；组间空行从第二组起打 | 每组后打空行，末尾多一行 |
| 早返回 | 校验必须在读数据之前 | 先读完再校验，或在读的过程中就崩了 |
| 按空白取词 | 需要几个数就取几个，跨行自动补齐 | 假定"一行 = 一个逻辑块"，分块不对齐时错位 |
| 性能技巧的边界 | 技巧只压常数，不改变量级 | 在 `O(N²)` 算法上死磕常数 |

## 自测题

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

<details><summary>答案与解析</summary>

**只有 `math.floor(x * 100 + 0.5) / 100` 能保证"恰为 `.5` 时向上"。** `f'{x:.2f}'` 用 round-half-even，`0.125` 输出 `0.12`；`round(x, 2)` 同样是银行家舍入，而且返回浮点而非定点数——`round(2.675, 2)` 得 `2.67`，因为 `2.675` 实际存储为 `2.67499999...`。三个细节：① `x * 100` 本身引入误差，`2.675 * 100 = 267.49999999999997`，要处理十进制字面值边界需用 `Decimal(str(x)).quantize(Decimal('0.01'), rounding=ROUND_HALF_UP)`；② 除回 `100` 只用于输出，中间计算不要提前量化；③ 负数时是"向零舍入"，题面要"远离零"须另写。**结论**：边界敏感时用第三种，样例显示边界不敏感时第一种更简洁，但绝不能默认它就是四舍五入。

</details>

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

<details><summary>答案与解析</summary>

**第一步估噪声**：数量级 `10⁹`，运算次数按"得到被比较的两个量所需的最少运算次数"数，若是求和 `n` 个数则为 `10⁴`，故 `噪声 ≈ 10⁹ × 10⁴ × 2.2e−16 = 2.2e−3`。**第二步定最小间隙**：取决于题目语义，若被比较的量是"整数加小数部分"，最小非零差距可能是 `1`；若是任意实数，差距可以任意小。**第三步取 `EPS`**（设真实最小间隙为 `1`）：

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

**这道题里 `1e−9` 完全不可用**——比噪声小 6 个量级，所有"应当相等"的量都会被判为不等。若实际只有 `n = 10²` 次运算，噪声降到 `2.2e−5`，取 `1e−3` 甚至 `1e−4` 也够。`EPS` 不是可以照抄的常数。

</details>

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

<details><summary>答案与解析</summary>

```python
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)]
```

**为什么不能用 `input()` 逐行读**：① **行边界是排版而非语义**——输入可能合并或拆分行，假定"读一行 = 矩阵的一行"遇到折行就**静默错位**，数值都读进来了只是分配错位置，程序照跑答案全错；② **逻辑分块与物理行数不对齐**——`rows × cols` 个数与文件行数本来就可以不同，只有按空白取词对两类情形都正确；③ **性能**——`input()` 每次调用都有 I/O 与缓冲开销，一次读入切词快数倍。**边界**：非空白分隔符需先 `replace(',', ' ')`；整数与浮点混排要用对应转换函数；`next()` 越界抛 `StopIteration`，应捕获后走早返回分支。

</details>

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

<details><summary>答案与解析</summary>

**问题**：空行打在了**每组之后**，最后一组后面会多出一个空行，与题面不符；评测机严格比对文本时会判为格式错误，即使数值全对。**修正**：把空行改到**每组之前**（从第二组开始），或收集全部输出行一次性写出：

```python
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')      # 末尾恰好一个换行
```

**顺带检查三点**：① **行尾空格**——`' '.join(...)` 不产生，写成 `for x in row: print(x, end=' ')` 就会多一个；② **末尾换行**——`'\n'.join(out) + '\n'` 保证恰好一个，有些题目要求末尾无换行（用 `end=''`），必须逐题核对；③ **`m = 0` 的退化情形**——`out` 为空时 `'\n'.join([]) + '\n'` 会输出一个空行，题面要求无输出时须 `if out:` 特判。

</details>

## 与真题的关联

| 真题 | 考查角度 | 对应本章小节 |
|---|---|---|
| 【2026-09-02 编程题 2】全整型量化的矩阵乘法 | half-up 与 `a / 2^b`；不能用 `round()`；从 30 往下扫取最大可行 `b` | 26.4 |
| 【2026-09-04 编程题 1】时间序列清洗与特征评分 | 四阶段口径清单；总体标准差；`×100` 后 half-up；负方差截断 | 26.1、26.7 |
| 【2026-09-02 编程题 1】滑动窗口注意力机制 | 参数校验在读矩阵之前；组间空行；负零归一；中间精度不量化 | 26.4、26.5、26.6 |
| 【2026-09-09 编程题 2】CDN 分发服务器选址 | `EPS = 1e−9` 判严格更优；同分取序号靠前；逗号分隔输入 | 26.2、26.3、26.6 |
| 【2026-08-26 编程题 2】多头注意力双向整数 RNN | 输入分块与逻辑分块不对齐 → 按空白取词 | 26.6 |
| 【2026-09-09 编程题 1】动态 KV 缓存稀疏优化 | 逗号连接头内索引、空格连接层内各头、行尾不留空格 | 26.5 |

## 延伸阅读

- 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 一遍法"的数值稳定性分析。


---

> 作者: [破戒僧](https://onlyblacktea.cn)  
> URL: https://onlyblacktea.cn/book/ai/ch26/  

