E10 完善程序专项（30 分）

2 篇程序，每篇 5 个空，每空 3 分，共 30 分。全部是四选一。

⚠️ 就算完全不会，全蒙的期望也有 7.5 分。 这一块绝对不许留空。

📝 本章的例子全部来自 E11 里那 7 套真题，每条结论都实测验证过。

一、先建立正确的心态

完善程序看着吓人（一大段陌生代码），但它其实比阅读程序好拿分，原因有三：

1. 有题目描述——题面会告诉你这段程序在干什么（「判断完全平方数」「最小区间覆盖」「编辑距离」）
2. 四选一——不用自己想，只要能排除
3. 五个空互相呼应——填出两个就能倒推第三个

⚠️ 最忌讳的是「看不懂就跳过」。 看不懂也要逐空排除。

二、★ 六类空位，各有固定填法

统计 7 套真题的 70 个空，几乎全部落在这六类里。

① 循环 / 递归的起点与边界

⚠️ CSP 2020 第 19 题（质因数分解）：① 填 1 会死循环（n % 1 == 0 恒成立），必须填 2。 ⚠️ CSP 2024 第 19 题（判断平方数）：① 填 2 会漏掉 $1 = 1^2$，必须填 1。

② 「规模一定要变小」的那个空

⚠️ 递归填空里最致命的一空。

CSP 2024 第 20 题（汉诺塔）：dfs(___, ...) 填 i 而不是 i-1 → 实测无限递归。 CSP 2021 第 19 题（约瑟夫）：i++ 而不是 i = (i+1) % n → 下标冲出数组，答案全错。

📝 通用查法：先确认递归出口（①），再确认规模在变小（②），最后才推参数顺序。 前两条一错就是死循环或答案差一倍，比参数顺序好查得多。

③ 数组访问前的边界保护

if (___ && isdigit(z[i + 1])) { ... }

📝 看这个空后面紧跟着哪次数组/字符串访问，空里填的多半就是那次访问的边界保护。

CSP 2025 第 19 题：下一句要访问 z[i+1]，所以填 i + 1 < z.length()。

⚠️ 实测提醒：这题填 i < z.length() 输出也完全正确（C++11 起 s[s.size()] 合法且返回 '\0'）。但考场上请填「访问前先检查边界」的那个——那才是出题人要的。

④ 比较 / 赋值（= vs ==）

⚠️ 选项里同时出现 num = i * i 和 num == i * i 时，几乎必然选 ==。

CSP 2024 第 19 题 ③ 就是这样。（该题的 ④ 是个特例：return num = 2*i 因为值非零恰好也对，所以标了「有多个可能选项」——但那是巧合，不是可以学的写法。）

⑤ 二分的中点与收缩方向

int mid = ___;              // 通常是 (a + b) >> 1
if (___) a = mid + 1;       // 通常是 cmp(A[mid], p)，即「比目标小就往右」
else b = mid;

⚠️ right = mid 与 right = mid - 1 的区别是二分最大的坑：

⚠️ CSP 2023 第 19 题实测：③ 填 right = mid - 1 会跳过正确答案；② 填 left = mid 会死循环。

⚠️ CSP 2021 第 20 题的教训更深：二分的比较函数多比了一个字段（id）就把目标滑掉了——我一开始猜错，穷举全部 $4^5 = 1024$ 种填法才定下唯一解。比较函数必须和「查找目标」的定义严格一致。

⑥ DP / 递推的转移与初始化

⚠️ DP 表下标从 1 开始，字符串下标从 0 开始，所以第 $i$ 个字符是 str[i-1]。 写成 str[i] 编译能过、样例可能碰巧也过，但错位一位——CSP 2023 第 20 题实测 kitten/sitting 从 3 变成 2。

三、★ 排除法的四条通用规则

即使完全看不懂程序，这四条也能帮你砍掉一半选项：

规则一：选项里如果有一个明显会死循环 / 越界，先划掉。

i--、「什么都不做」出现在循环推进的位置 → 死循环。

规则二：看这个空所在的语句是「赋值」「条件」还是「参数」，类型对不上的先划掉。

if (___) 里填 count++ 显然不对。

规则三：五个空互相印证。

比如 ② 填了 count * 10 + (z[i]-'0')（多位数字累加），那 ③ 就应该是 count（重复 count 次）而不是 10。

规则四：拿题面给的例子代进去验一下。

完善程序题通常给了样例（甚至像 CSP 2022 第 20 题那样把期望输出写在注释里）。把候选选项代入，手算一两步就能筛掉大半。

⚠️ 但要注意规则四的局限：题目自带的那一组数据可能区分不出正确和错误答案。

CSP 2022 第 20 题实测：② 填 image[cur]=prev_color（等于什么都没做）在题目给的那张 8×8 图上跑出来和标准答案完全一样——因为起点会被邻居反过来染色。换一张「起点是孤立像素」的图才露馅。

📝 考场上不必做到这一步，但要知道：过了样例不等于填对了。

四、必背的算法骨架

完善程序考的模型高度重复，把这几个骨架背下来，看到就认得出：

⚠️ BFS 的铁律：入队前就要标记。 等出队再标记，同一个格子会被多个邻居重复入队，队列爆炸。

⚠️ 计数排序的第三步必须倒着扫（for (i = n-1; i >= 0; --i)），否则丢失稳定性；双关键字要先排第二关键字再排第一关键字。

五、答题流程

1. 先读题面描述 —— 它告诉你程序在干什么（这是免费信息，别跳过）
2. 通读代码，标出五个空各自在什么语句里
3. 从「最容易的空」入手 —— 通常是①（起点）和⑤（返回/输出）
4. 用已填的空去推剩下的
5. 拿题面给的例子代进去验一遍
6. ⚠️ 剩下实在拿不准的，也必须蒙一个填上

📝 时间控制：每篇约 17 分钟。 一篇卡住超过 20 分钟就先蒙上往下走，回头再看。

30 秒自测

1. 完善程序共几分？全蒙的期望是多少？
2. 递归填空里最致命的一空是哪种？填错会怎样？
3. 「枚举因数只跑到 $\sqrt n$」之后，为什么还要 if (n > 1) 补一句？
4. right = mid 和 right = mid - 1 各用在什么时候？配什么循环条件？
5. DP 表下标从 1 开始时，第 $i$ 个字符怎么写？
6. BFS 里应该在入队前还是出队后做标记？为什么？
7. 计数排序第三步为什么要倒着扫？
8. 「代入题目给的样例验证通过」能保证填对吗？