# lab · 第 3、4、5、6、9、10、11、13、14、16、17、18、19、21、22、25、26、29、30、33 课与实验一、二、三、四的动手练习

这个 lab 有二十四份练习，一课（或一个实验）一个目录，各自带自己的判分脚本：

| 课 | 目录 | 练什么 |
| --- | --- | --- |
| 0003 · 列表与字典的隐藏价格 | `0003-python-list-dict-cost/` | 同一份数据用「列表 `in`」「集合 `in`」「字典查」各跑一遍量耗时；再用 `pop(0)` 与 `deque.popleft()` 对照一次；最后把 n 放大十倍，看哪一行跟着涨 |
| 0004 · 把一段代码变成函数 | `0004-python-function-basics/` | 把摊平的题改写成三四个函数，输出必须逐字一致；默认参数的陷阱与修法；故意用全局变量传状态；函数里改传进来的列表，两种后果各看一遍 |
| 0005 · 推导式与常用内置工具 | `0005-python-comprehension-builtins/` | 把十段循环逐段压成一行（推导式或现成函数），输出必须逐字一致；生成器为什么只能走一遍；`enumerate` / `zip` 改造下标循环；`sorted(key=)` 按第二关键字排序与 `list.sort` 返回 `None` 的坑；`any` / `all` 与空序列的口径 |
| 0006 · 读完输入再动手 | `0006-python-io-and-debug/` | 五种输入格式（单行多整数、多行整数、矩阵、混合行列、多组数据带空行）各读成指定的数据结构；同一份数只把换行位置换掉，看「边读边算」静默算错、而「先读完再算」两条都对；字符串当数字比的反直觉结果；用打印把出错范围缩小；`input()` 的提示为什么会让提交判零分 |
| 0009 · 一维数据的两种走法 | `0009-linear-structures-two-pointers/` | 同一道区间求和题写三个版本（暴力 / 前缀和 / 双指针），拿暴力版当基准对拍；含 0 与负数的数组上双指针漏解，亲眼看见它和暴力版答案不同；去掉 `r < n` 复现下标越界；把三种走法随规模的增长量成数字（暴力翻倍涨四倍、两个线性版涨两倍） |
| 实验一 · 把一道题跑通 | `0007-lab-01-run-one-problem/` | 两道题、两种输入格式各跑通一条完整链路（读入 → 解析 → 求解 → 打印）；自己写一份样例自测脚本（能抓出错解才算数）；再量一次两种查重容器的量级差。判分分五层：样例 / 换行被打乱的数据 / 大数据 / 自测脚本 / 规模对照 |
| 0010 · 后进先出与先进先出 | `0010-stack-and-queue/` | 用列表写栈、用 `deque` 写队列，再各量一次出队的代价；用它做三道题：括号匹配（还要交出第一个出错的位置）、后缀与中缀表达式求值、滑动窗口最大值（单调队列，两条弹出各写一遍） |
| 0011 · 双指针：两个下标的配合 | `0011-two-pointers-applications/` | 三种配合方式各写一遍：对撞（有序数组两数之和，还要数出每档走几轮）、快慢（原地去重：一个读一个写，写位置划出有效段）、从后往前（把有序数组 b 合并进 a 的后半段空位）。另有两道：`if` 与 `while` 只差一处关键字、却在一个特定输入形状上漏解；回文判定与「第一处错位」必须是同一趟走法（`'abca'` 的首尾相等，收一格之后才分开） |
| 0013 · 排序：分而治之的样板 | `0013-sorting-and-divide-conquer/` | 手写归并、快排（固定主元与随机主元两版）与计数排序，在随机 / 已有序 / 逆序 / 重复值四类数据上确认五个实现与 `sorted` 逐字一致；把「干了多少活」记成**操作次数**而不是秒数（换台机器还是同一个整数），算出相邻两档的倍率并指出哪一列不是 $n\log n$ 的形状；在已有序数据上把固定主元快排的 `RecursionError` 现场复现出来、再换随机主元修回去，看清两者「一个算得多动得少、一个算得少动得多」；最后算一遍计数排序开头那张表要开多少个位置，说清 0..999 能用而 0..10⁹ 根本开不出来 |
| 0014 · 二分：每次砍掉一半 | `0014-binary-search/` | 先把闭区间与左闭右开两个模板抄对——那半行区间开闭写串（闭区间里写 `hi = mid`、左闭右开里把 `hi` 取成 `len(a) - 1`）程序照样跑完，只在边界数据上给错答案；再用 8 组边界数据（空、单元素命中/不中、全相同命中/不中、目标在左端/右端/不存在）把三种典型错法逼现形，并写清是哪一行导致的；最后量轮数与耗时——轮数是 `ceil(log2(n+1))` 这样的确定值（n = 10 / 1000 / 10⁵ / 2×10⁶ → 4 / 10 / 17 / 21），而 200 万个数上线性扫比二分慢约 9000 倍 |
| 实验二 · 给解法装上对拍器 | `0015-lab-02-verify-by-brute-force/` | 自己写一份对拍脚本：参照解（线性扫的 `brute_find`）、两个数据生成器（宽范围 + 边界形态）、比对循环 `stress`、反例最小化 `shrink`；最后把原始反例 / 最小反例 / 出错的行号写进 `findings.md`。判分分四层：参照解 / 对拍器没自己骗自己 / 抓得住且可复现 / 缩到最小且记录对得上 |
| 0016 · 为什么字典查得那么快 | `0016-hash-table/` | 三件事各写两版（统计次数、找第一个重复、两数之和：列表版按定义做、字典或集合版一遍哈希），结果必须逐字一致；再手工算一遍哈希值与桶号看冲突；最后试「什么能当键」——列表当键报什么错、浮点当键为什么取不到、哈希值跨进程为什么不一样 |
| 0017 · 树：会递归的结构 | `0017-binary-tree-traversal/` | 用嵌套列表表示二叉树，写前中后序与层序四种遍历；再用递归汇总子树信息（节点数、树高、对称性）；查出链状树在默认递归上限下第几层爆栈；最后把「拼接」与「累加器」两种收集方式在链状与平衡树上各量一次 |
| 0018 · 每次都要最小的那个 | `0018-heap-and-priority-queue/` | 用 `heapq` 解决取极值类问题（合并果子、前 k 大、数据流中位数），再手写一个数组实现的最小堆：上浮、下沉、推入、弹出，并在随机数上与 `heapq` 对照弹出的序列 |
| 0019 · 并查集：谁和谁是一伙的 | `0019-union-find/` | 先写出基础 DSU（`find` / `union` / `connected`），再加上路径压缩与按大小合并两招；把 1..n 串成一条链，看树高从 **1999 掉到 1**、单次 `find` 的步数从 **19945 掉到 10**；做一张 2×2 对照表（两个优化各开各关）分清哪一招管「查得快」、哪一招管「树不歪」；最后拿并查集数一遍连通块，再用邻接表 BFS 数一遍，两种数法必须对上 |
| 0021 · 搜索：把图走一遍 | `0021-dfs-bfs-search/` | 网格与图上写出 DFS / BFS 两套模板，看两种走法的次序差在哪里；求迷宫最短路，并亲眼看见 DFS 在同一个迷宫里跑不完；数岛屿、连通块（搜索版与并查集版两条路）、多起点到达；最后把 visited 的两个标记时机摆在一起量四倍的差距 |
| 0022 · 二分答案：猜一个再验一遍 | `0022-binary-search-on-answer/` | 两道题（木材切割、跳石头）各拆成两步：先写 `check(x)`（这个候选长度 / 这个最小间隔行不行），再在答案区间上二分；**拿暴力枚举当尺子**，在 200+ 组随机小数据上验证二分找到的确实是最大值；最后亲手破坏 `check` 的单调性（True 区间变成零散的 `{2,4,6,8}`），看同一个二分在不同初始区间上给出 8 / 2 等不同答案——这就是「二分答案必须先证单调」的现场 |
| 0025 · 背包：选与不选 | `0025-dp-knapsack/` | 0/1 背包的二维表与一维逆序两版；内层正序那一版故意写错，看它偏大多少、以及它为什么恰好等于完全背包；恰好装满的负无穷初始化；分组背包「每组最多一件」的那一层循环次序 |
| 0026 · 序列与区间的状态设计 | `0026-dp-sequence-interval/` | LIS 的 DP 版 / 二分版 / 回溯版（并看清 `tails` 不是一条子序列）；LCS 的表与两条边上的 0；最长回文子序列的区间 DP；石子合并的断点枚举，以及「长度枚举写反」为什么让答案偏小 |
| 实验三 · 让助手推荐并验证 | `0027-lab-03-recommend-and-verify/` | 做出题目文本进、候选算法出、自动验证收尾的端到端脚本：提示词的四样约束、解析器六种形态的成绩、不靠模型的关键词打分、以及拿暴力当尺子的验证与收尾判断。判分分五层，第五层把 `socket` 换成会抛异常的版本再跑一遍 |
| 0029 · 让 Python 再快一点 | `0029-constant-factor-tuning/` | 一条先量后改的链：分段计时找出瓶颈（看着最重的不是最慢的）、依次上四招（换容器 → 整体读入 → 提前算不变式 → 用内置）并每招回验答案、和内置实现比并说清「差在哪一层」、最后**故意写错一次**确认对拍器抓得住。判分分五层，判死的全是**操作次数**而不是秒数 |
| 0030 · 交卷之前你要检查什么 | `0030-stress-test-and-review/` | 把「样例过了就交」拆成一条能被程序检查的链：对拍（换一把尺子，`0 / 58 / 58 / 0` 四个数一起看）、生成器的范围（`0 组` 与 `33 组` 是同一句话的两半）、多组数据要清空（第一组往往是对的）、取模（差 2080 位而在 n = 30 上逐字相同）。判分分五层，每层主检查 + 探针副线 |
| 实验四 · 一次完整的赛前模拟 | `0031-lab-04-spaced-repetition-drill/` | **这一课的实验本身就是考核**：五道省赛难度的题、满分 360、限时 240 分钟，而五题全做要 470 分钟——所以考的是「做哪几道、放弃哪几道」。五道题分别落在第 21／22／26／16+28／16+22 课，其中 p4 是**故意设计成做不完**的那一道。要交的是答案、一份限时记录（六格）与一份讲解稿（四段），判的是**决策与表述**：`score.py` 算分、`check_timeline.py` 查记录与讲解稿、`run_tests.py` 是判分器的自检 |
| 0033 · 综合实战：把刷题助手做完 | `0033-capstone-ai-tutor/` | 整门课收成一个能跑的作品：**题目文本进、带证据的记录出的五段流水线**（提取题意 → 推荐算法 → 写解法 → 验证 → 出记录），每两段之间查一次契约。三件真正要学的事：**先写契约再写实现**（不对时抛异常并点名字段）、**模型输出不可信**（被截断那一档三档解析器都救不回来，只能重试）、**`passed` 变成字符串 `'False'` 会被静默当成「通过」**。`call_model` 是唯一的联网点，判分全程用假模型、不用 key |

参考解在 `solutions/<同一目录名>/`，与任务分开放，做完才对照。
`0004-python-function-basics/` 里那份 `flat_odd.py` 是**基准**：它是改写前的摊平版，判分拿它的输出当标准，别改。
`0005-python-comprehension-builtins/` 里那份 `loops_original.py` 同样是**基准**：它是改写前的循环版，判分拿它那十行输出当标准，别改。
`0006-python-io-and-debug/` 里那份 `task2_read_then_compute.py` 的 `sum_rows_running` 也是**给好的对照**（「边读边算」那一版，别改）：判分靠它在折行数据上打出 36，让你看见什么叫「不报错的错」。
`0007-lab-01-run-one-problem/` 里那份 `probe_wrong_a.py` 是**判分用的错解**：判分把它替换成你的 `solve_a.py` 去试你的自测脚本，看你会不会报 FAIL；别删、别改、也别拿它当交差。
`0009-linear-structures-two-pointers/` 里那份 `tools.py` 是**给好的公共工具**（造数据、打印判分要读的固定格式行、计时）：五个任务都从它取东西，别改。
**0009 的基准不是某个文件，而是你自己写的任务 1**——暴力版对了，后面两个版本才有的比。

## 载体与环境依赖

- **载体**：Python 3 脚本 + 测试脚本自动判——学生写 `.py`，`run_tests.py` 跑它、读它打印出来的数字与列表。
- **依赖**：只用 Python 标准库（`time`、`collections`），不需要装任何第三方包，不需要联网。
  0005 连标准库都不用 import：整份练习只写普通语句、推导式与现成函数。
  0006 的六个任务只用 `sys.stdin` 与 `input()`，也不装任何东西。
  0007 的算法代码（`solve_a.py` / `solve_b.py`）也只用学过的语法；它的两份**工具**脚本
  （`selfcheck.py` / `scale_check.py`）另外要用 `sys` / `os` / `subprocess` / `random` / `time`——那是脚本的工具，不是算法的一部分。
  0009 的五个任务只用 `tools.py` 给的三个函数与课件学过的写法（`time` 由 `tools.timed` 代劳，任务里不用自己 import）；
  `tools.py` 与 `run_tests.py` 自己另外用 `time` / `subprocess` / `pathlib`——那是判分与工具的事，不是你要写的部分。
- **怎么跑**（先 `cd` 进某一课的目录；判分脚本只判它自己那一课）：

  ```text
  py task1_lookup.py        # 0003：单独跑一个任务，先看它打印什么
  py run_tests.py           # 0003：判分，四个任务一起判，逐条给 PASS / FAIL

  py flat_odd.py            # 0004：摊平版基准（给好的，别改），敲一个数回车
  py task1_functions.py     # 0004：单独跑一个任务，敲一个数回车
  py run_tests.py           # 0004：判分，四个任务一起判，逐条给 PASS / FAIL

  py loops_original.py      # 0005：改写前的循环版基准（给好的，别改），打出十行结果
  py task1_rewrite.py       # 0005：单独跑一个任务，先看它打印什么
  py run_tests.py           # 0005：判分，六个任务一起判，逐条给 PASS / FAIL

  cat sample1.in | py task1_parse.py one   # 0006：把样例接到标准输入上（PowerShell 的 cat 就是 Get-Content）
  py task1_parse.py one                    # 0006：这样直接跑没用，它在等标准输入
  py task2_read_then_compute.py tokens     # 0006：换成 sample6.in 再跑一次，看结果会不会变
  py run_tests.py                          # 0006：判分，六个任务一起判，逐条给 PASS / FAIL

  cat sample_a1.in | py solve_a.py   # 0007：把样例接进脚本跑一遍（PowerShell 的 cat 就是 Get-Content）
  py solve_a.py                      # 0007：这样直接跑没用，它在等标准输入
  py selfcheck.py                    # 0007：你自己的自测脚本，四组样例逐组 PASS / FAIL
  py scale_check.py                  # 0007：任务 4 的耗时对照（要跑一秒左右）
  py run_tests.py                    # 0007：判分，五层一起判，逐条给 PASS / FAIL

  py task1_brute.py         # 0009：单独跑一个任务，先看它打印什么
  py task3_window.py        # 0009：双指针那一个（会打出「错版报错 IndexError」那一行）
  py task5_scale.py         # 0009：耗时对照（要跑一两秒，慢的是暴力版）
  py run_tests.py           # 0009：判分，五个任务一起判，逐条给 PASS / FAIL

  py task1_stack_queue.py   # 0010：单独跑一个任务，先看它打印什么
  py task2_queue_cost.py    # 0010：出队 20 万次的两种写法（要跑一两秒，慢的是 pop(0)）
  py task5_window_max.py    # 0010：滑动窗口最大值（要跑一两秒，慢的是暴力那一列）
  py run_tests.py           # 0010：判分，五个任务一起判，逐条给 PASS / FAIL

  py stress.py              # 0015：跑完五个任务，把要抄进 findings.md 的东西打出来
  py buggy.py               # 0015：那一版有 bug 的候选解（给好的，别改），看它自查四组
  py run_tests.py           # 0015：判分，四层一起判，逐条给 PASS / FAIL

  py task1_count.py         # 0016：单独跑一个任务，先看它打印什么
  py task4_hash_buckets.py  # 0016：这一份要自己跑两遍，对比两次的哈希值（跨进程会变）
  py run_tests.py           # 0016：判分，五个任务一起判，逐条给 PASS / FAIL

  py task3_depth_shape.py   # 0017：要跑一两秒（会从 990 层往上试着搭链，直到爆栈）
  py task4_concat_cost.py   # 0017：拼接与累加器的耗时对照（要跑两三秒）
  py run_tests.py           # 0017：判分，四个任务一起判，逐条给 PASS / FAIL

  py task2_kth_largest.py   # 0018：20 万个数、七个 k（要跑十几秒）
  py task1_merge_fruit.py   # 0018：合并果子三档（要跑一两秒）
  py run_tests.py           # 0018：判分，四个任务一起判，逐条给 PASS / FAIL

  py task2_maze_shortest.py # 0021：DFS 那几段一律限量跑（迷宫那段要零点二秒）
  py task4_mark_timing.py   # 0021：两种标记时机摆在一起（要跑一两秒）
  py run_tests.py           # 0021：判分，四个任务一起判，逐条给 PASS / FAIL

  py task2_direction.py     # 0025：正序那一版错在哪（要跑一两秒）
  py run_tests.py           # 0025：判分，四个任务一起判，逐条给 PASS / FAIL

  py task4_stone.py         # 0026：石子合并与 200 组对拍（要跑一两秒）
  py run_tests.py           # 0026：判分，四个任务一起判，逐条给 PASS / FAIL

  py task1_prompt.py        # 0027：看提示词长什么样（离线，不联网）
  py run_tests.py           # 0027：判分，五层一起判，逐条给 PASS / FAIL
  ```

  0006 的每个任务都按「命令行给一个模式名」来跑，判分脚本就是这么各起一次进程的
  （`one` / `lines` / `matrix` / `mq` / `groups`、`running` / `tokens` / `parsed`、
  `diagnose` / `repr`、`clean` / `dirty`）——文件名、模式名与带 `print` 的行都是判分接口，别改。

  Windows 上 `python` 可能是应用商店的占位符（敲下去没反应），用 `py`。本机 `py` 指向 Python 3.14.7。
  退出码十五个 lab 一样：这一课（或这一个实验）的任务都过是 **0**，还有没过的就是 **1**，
  脚本最后一行会点出是哪几个没过。任务是几个就是几个：0003 / 0004 / 0017 / 0018 / 0021 / 0025 / 0026 各四个或五个，
  0005、0006、0010、0016 各五个或六个，0007 五层，0009 五个，0015 与 0027 各分四层或五层。
  判分**认的是它自己那一课目录里的文件**，所以要在哪一课里判就先 `cd` 进哪一个目录。
- **0003 的秒数只作参考**：课件与参考解里写的 1.5 秒 / 0.013 秒都是本机实测，换台机器绝对值会变。
  判分看的是**趋势**（列表 `in` 比集合慢几十倍以上、`popleft` 比 `pop(0)` 快 20 倍以上、
  放大十倍时列表涨约 10 倍而集合几乎不动），不是背下来的常数。
- **0004 看的是逐字一致**：任务 1、3 的答案必须与 `flat_odd.py` 的输出一个字符都不差
  （四组验收输入：0 → 0、1 → 1、10 → 5、1234567 → 617284）；任务 2、4 看的是几个固定 `print` 行打出的值。
- **0005 同样看逐字一致，另外把几件「看不见的事」变成数字**：任务 1 的十行结果必须与 `loops_original.py` 逐字相同；
  任务 3 用一个「会数自己被调用几次」的函数，把「生成器还没开始算」（0）、「取完就空」（第二次求和是 0）、
  「短路」（`any` 只看了 3 个、`all` 只看了 4 个）都打成数字；判分还会另起一个进程 import 任务 3 的
  `squares_gen`，确认它交回的是**生成器**（`len` 与下标都报 `TypeError`），不是列表。
  任务 1 末尾另有一条总检：大纲要求 `enumerate`、`zip`、`sorted(key=)`、`sum`、`max`、`any`、`all`、`map`
  各至少改写一处，缺哪个会点名。判分读的就是各个 `print` 行，别改它们。
- **0007 的报错都指名到「哪一层」**：判分分五层给反馈，一层里几条检查各自给 PASS / FAIL。
  第 1、2 层没过时第 3–5 层**直接跳过**（样例都没过，大数据组的信息没有参考价值）；
  第 3 层按 **2 秒**限时跑（题面写的是评测机上的 1 秒，本机比评测机慢，宽一点）——
  超时说明容器选错（列表查重是平方级），答案错说明正确性还有问题，两种情况给的话不一样。
  第 4 层会把整个目录复制一份、把 `solve_a.py` 换成 `probe_wrong_a.py`，只在**副本**里试你的自测脚本：
  它必须报 A1/A2 FAIL 而 B1/B2 仍 PASS，永远报 PASS 的自测脚本这一层过不去。
- **0007 的 `tests/` 是判分数据**：`a3.in` / `b3.in` 与样例 **token 完全一样、只是换行位置不同**
  （答案必须与对应样例一致）；`a_big.in` 是 10 万个整数，`b_big.in` 是 300×100 的成绩单。
  别改这些文件，也别把大数据删掉——第 3 层就是靠它们区分「写错了」与「选错了容器」。
- **0006 看的是「数据结构对不对」，不是「答案对不对」**：五个任务里比对的全是解析出来的
  数据结构（列表、二维列表、元组的列表），与课件写死的那几份逐字一致——
  单行多整数 `[3, 1, 4, 1, 5, 9, 2, 6]`、多行整数 `[3, -1, 4, 2, 7]`、
  矩阵 `[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]`、混合行列 `[(1, 1), (3, 4)]`、
  多组数据 `[[1, 2, 3], [10, 20, 30, 40]]`。
  任务 1 末尾单列一条折行检查：`sample6.in` 与 `sample3.in` 是**同一份数、只是换行位置不同**，
  两份必须打出同一个矩阵（按行切开会读出 `[[1, 2, 3, 4], [5, 6], [7, 8]]`）。
  任务 2 是这一课的要害：给好的对照版在整齐数据上 78、在折行数据上 **36** 而一个错字都不报，
  改写版必须两条都是 78。
- **0006 有两条检查是「检查本身也要被检查」**：任务 5 会把你的 `clean` 临时换成带提示的版本
  再跑一次，如果那样也验不出标准输出被污染，这条检查就是假的；任务 6 会拿八组文本
  （含只差末尾换行、只差一个空格、多一行、多一个前缀）试你的 `same_output`，
  永远返回 `True` 或永远返回 `False` 的写法都过不去。
- **0009 的判分读两种固定格式行，并且看趋势不看常数**：`计数 NN 标签 值`（答案个数）与
  `耗时 NN 标签 n=… 秒`（秒数）都由 `tools.py` 打印，编号与标签都别改。三个版本的正确性靠**对拍**验：
  任务 3、4 各交回「与暴力一致」这类比对行。**含负数那几行期望打出 `False`**——两个版本答案不同才是对的，
  它正是这一课要你看的反例；打出 `True` 反而说明双指针版写成了别的样子。
  耗时那一列只要求两条趋势：暴力随规模翻倍涨 2.5 倍以上（该是四倍上下）、两个线性版涨得比它少；
  以及同规模上暴力比双指针慢 100 倍以上。绝对值换台机器就变，别背几个秒数。
- **跑一遍要多久**：0003 全部十几秒（`pop(0)` 那 20 万次自己就要两三秒，这正是任务 2 要你看的东西）；
  0004 一两秒（它不做计时，只比输出）；0005 半秒以内（不做计时，只比输出与几个计数）；
  0006 两秒左右（不做计时，只比数据结构与几行固定输出）；
  0007 全部两秒以内（其中 `scale_check.py` 自己占一秒左右——那正是任务 4 要看的差距）；
  0009 全部两秒以内（其中 `task5_scale.py` 自己占一秒多——那正是任务 5 要看的差距）。

- **0010 的判分读四种固定格式行，也看趋势不看常数**：`计数 NN 标签 值` 与
  `耗时 NN 标签 k=… 秒数 秒`、`倍数 NN 标签 倍数`（`tools.py` 打印）再加上一批带标签的 `print` 行。
  任务 1 不比「结果碰巧对」：它拿列表 `append`/`pop`、`deque` `append`/`popleft` 当**参照模型**，
  300 步操作里每一步的栈顶与队头都要与模型一致。任务 2 的 `deque 比列表快` 那一行要 ≥ 20 倍，
  但**旁边的 `倍数 03` 期望小于 1**——它算的是「deque 秒数 ÷ 列表秒数」，两条计时各量各的本来就该这样。
  任务 5 的 `倍数 01/02` 反过来是「暴力 ÷ 单调队列」，越大越好；秒数换台机器就变，别背。
  任务 4 里 `后缀 减法与除法没有写反` 与 `中缀 同优先级从左往右` 两行专抓两处静默错：
  弹出顺序写反（`52-` 从 3 变 -3）与优先级比较写成 `>`（`9-3+2` 从 8 变 4）。
- **0015 是「四层」判分，第 1 层没过后面三层直接跳过**：参照解是尺子，尺子不准就没什么可看的。
  第 2 层拿**同一个函数**同时当候选与参照跑 2000 次，必须一次都抓不到——它专抓「stress 根本没在比对」；
  再加一条对照：候选换成「答案永远是 0」的函数，必须立刻抓到。
  第 3 层用两个「只在某种边界形态上出错」的假候选反过来试 `gen_boundary`（空数组、单元素或重复值），
  然后对拍 `buggy.py`，并要求同一个 seed 两次抓到**同一组**。
  第 4 层会把 `shrink` 交给一组专门造的输入（`[10, 20, 63, 97]` x=97）看它真的在缩，
  再比对 `findings.md` 里记的三样。**判分不判的东西**：生成器够不够多样、记录写得清不清楚——
  那由这份 README 的自查清单与课件那一节回答；判分只管能不能跑、比对有没有生效、反例能不能复现。
- **0016 每个任务都是「同一件事写两遍」，两版必须逐字一致**：只交一版（或者两版都交空字典）不算过。
  判分读的是脚本自己打印的行（前缀就是接口），外加**探针进程** import 你的函数、拿判分自己造的小数据试：
  任务 1 比六组、任务 2 比六组（含 `[]`、`[5, 5]`、`['a', 'b', 'a']`）、任务 3 比八组
  （专抓 `[3, 3]` 这一个「先查后存」的边界）、任务 4 拿十个键放进八个桶试 `conflicts`、
  任务 5 拿两个进程分别调 `hash_of` 比哈希值。**只硬凑 print 拿不到 PASS**——探针的数据在判分手里。
  任务 4 有两个反直觉的地方：判分**跑两遍**脚本，要求两次的哈希值确实不同（跨进程带随机种子），
  而「装了不止一个键的桶数」是按**你自己打出来的桶号**数的，所以那个数不必与别人相同，只要数法对。
- **跑一遍要多久**：0010 十几秒（其中 `pop(0)` 那 20 万次自己占一秒多、滑动窗口那四档暴力占一秒半）；
  0015 几秒（对拍每轮 2000 次，四层里跑了好几轮）；0016 十几秒（任务 3 的列表版自己就占十几秒——
  那是给好的数据刻意造出来的最坏情形，正是这一课要看的差距）。
  后面几课里，0018 与 0025 各自己占几十秒（0018 的任务 2 拿 20 万个数在七个 k 上跑、
  任务 1 的三档各跑 5 次；0025 每个任务都在几百组随机数据上对拍）；
  0017 几秒、0021 四秒上下（DFS 那几段一律限量，各占零点二秒）；
  0026 与 0027 各几秒。**判分脚本自己也有几处固定开销**（起子进程、造数据），
  所以「跑一遍」比单跑一个任务慢——这是正常的。

## 各份练习的写法边界

**0003 只用到这么多东西**，任务里请照着写：

- 标量、`for` / `while` 循环、`if` / `else`
- 列表 / 集合 / 字典的字面量与 `set()`、`[]`、`{}`
- `in`、`append`、`add`、`pop`、`insert`、`popleft`、`len`
- `print`、`f'{x:.6f}'` 这种格式化、`import time`、`import collections`

**0004 在 0003 的基础上加**（这就是这一课新学的）：

- 定义与调用函数：`def` / `return` / 形参与实参 / 默认参数 / 关键字实参 / `global`
- 判断两个名字是不是同一个对象：`is`（`L is None`）
- 下标循环：`for i in range(len(nums))` 配 `nums[i] = ...`
- 切片复制一份列表：`nums[:]`

**0003 与 0004 这两份都不用**：推导式、`sorted` / `enumerate` / `zip`、`defaultdict` / `Counter`、
`timeit.repeat`、递归——这些正是第 5 课新教的，留到 0005 去用。

**0005 在 0004 的基础上加**（这就是这一课新学的）：

- 列表推导式：`[x ** 2 for x in data]`，带条件的 `[x for x in data if x > 0]`，
  带嵌套的 `[num for elem in vec for num in elem]`
- 生成器表达式：`(x ** 2 for x in range(6))`——只能走一遍、没有 `len`、不能下标
- `sum` / `max` / `min` / `any` / `all` / `len` / `abs`，以及 `sum(1 for x in data if x > 0)` 这种计数写法
- `enumerate`（含 `start=1`）、`zip`、`map`（配 `list(...)` 收成表或直接喂给 `sum`）
- `sorted(...)` 与 `list.sort()`、`key=` 指定的键函数（**在本课里用 `def` 写，不用 `lambda`**——
  `lambda` 你只在课件里见过，写题时先用命名函数）
- 判定里的 `is None`、`if not nums:` 这类判空

**0005 不用**：递归、`defaultdict` / `Counter`、`timeit.repeat`、`itertools`。
本课不做耗时测量（课件里那张毫秒表是说明「一行不等于更快」，lab 不要求你复现数字）。
`input()` 仍然只在任务需要读入时才用，而且**不带提示参数**。

**0006 在 0005 的基础上加**（这就是这一课新学的）：

- 一次读完：`sys.stdin.read()`——**整份输入只被碰一次**
- 按空白切分：`text.split()`（连续空白算一个）；按行切分：`text.splitlines()`（会去掉行尾换行符）
- 空行跳过：`if line.strip()`（`int('')` 与 `int('\n')` 都报 `ValueError`）
- 二维列表：`[vals[i * m:(i + 1) * m] for i in range(n)]`（切片右端不包含）
- 显式下标变量推进读的位置（`pos`），读完拿它与 `len(tokens)` 对照
- `input()`（**竞赛代码里括号中永远不写参数**）、`print(repr(line))` 看不可见的字符
- `try` / `except TypeError`、`type(e).__name__`

**0006 不用**：递归、`heapq`、`itertools`、`Counter` / `defaultdict`、`timeit.repeat`、`lambda`。
本课不做耗时测量。参考解里出现 `os` / `subprocess` 的只有判分脚本 `run_tests.py`
（它是**判分用的工具**，按 0005、0007、0009 的先例单独对待），学生的六个任务文件一个都不 import。

**实验一（0007）是验收课：把前六课学过的东西一起用上，不引入新语法。**

- 第 6 课的读入规矩：一次读完（`sys.stdin.read()`）→ 按空白切分（`split()`）→ 解析成数据结构（第 4 课的函数）
- 第 5 课的推导式与内置：`[int(x) for x in tokens[1:1 + n]]`、`[max(row) for row in grid]`、
  `sorted(counts.items(), key=键函数)` 取第一条
- 第 3 课的容器选择：查重用 `set`、计数用 `dict`（`in` / `add` / 字典查都是平均 `O(1)`）
- 第 2 课的估算：动手之前先数「我的循环一共要跑多少次」，再对着题面的数据范围与时限判断

**0007 不用**：递归、`heapq`、`itertools`、`Counter` / `defaultdict`、`timeit.repeat`、`lambda`
（`lambda` 只在课件给过的代码里出现）。
**例外是那两份工具脚本**：`selfcheck.py` 与 `scale_check.py` 允许 `import os` / `sys` / `subprocess` /
`random` / `time`——它们要做的是「起一个子进程、量一次耗时」这种脚本活，不是算法。

**0009 用第 1 到 8 课学过的东西，不引入新语法**（这一课新学的只有「前缀和」与「双指针」两种走法本身）：

- 标量、`for` / `while` 循环、`if` / `else`
- 列表 / 集合 / 字典的字面量与 `[]`、`{}`、`set()`；`in`、`append`、切片、`len`、`sum`、`max`、`min`、`abs`
- 定义与调用函数（第 4 课）：`def` / `return` / 形参与实参；一个函数只管一件事
- 推导式与内置（第 5 课）：`[x for x in data]`、`sum(1 for x in row if …)`、`enumerate`、`zip`、`sorted`
- 从别的文件里取东西：`from tools import …`、`from task1_brute import count_brute`
  （这就是「把代码拆成几个文件」的入口，本课的五个任务互相之间就是这么用的）
- `if __name__ == '__main__':` 这一层守卫：任务 2 到 5 会 import 前面的任务文件（任务 3 要用任务 1、2 的函数），
  没有守卫的话 import 一次就把前面那些任务的 `print` 重放一遍。**每个任务里都给你写好了，别删**
- 计时不自己写：`tools.timed` 已经封好了「前后各取一次 `perf_counter` 相减」，你只要 `timed(count_brute, a, S)`
- 接住异常：任务 3 那一段 `try:` / `except IndexError as exc:` 是**给好的**（判分接口），
  它把去掉 `r < n` 之后那个越界报错接住、只打出报错的类型

**0009 不用**：递归、`heapq`、`itertools`、`Counter` / `defaultdict`、`timeit.repeat`、`lambda`。
**栈与队列（第 10 课）、对撞指针（第 11 课）都还没学，别用**——本课的双指针只指「滑动窗口」
这一种（两个下标都往右走），不是第 11 课那种「两个下标往中间收」。
`input()` 这一课的五个任务都用不着（数据由 `tools.py` 造），要用也**不带提示参数**。

**0015 用第 1 到 14 课学过的东西，不引入新语法**（这一课新学的只有「对拍」这件事本身）：

- `import random`（**必须**，判分第 1 层会看这一行）：造数据器与固定种子都要它
- `random.sample` / `random.randint` / `random.randrange` / `random.seed`——种子在**循环外面**设一次
- 定义与调用函数当**参数**传：`stress(candidate, reference, gen, trials, seed=None)` 收到的是函数本身，
  里面对它们做 `candidate(a, x)` 这样的调用（函数是一等对象，这一课第一次这么用）
- 元组装一组结果：`return (第几次, a, x, 候选答案, 参照答案)`；`None` 当「一次都没抓到」
- 列表切片拼出「删掉一个元素」的那一版：`cur[:i] + cur[i + 1:]`
- 只从 `tools` 里取：`as_lists` / `labels` / `load_buggy` / `match_found` / `show_count` / `show_pairs`

**0015 不用**：递归、`heapq`、`itertools`、`Counter` / `defaultdict`、`timeit.repeat`、`lambda`、
`try` / `except`（对拍器不该靠接住异常过日子）。`buggy.py` 与 `tools.py` 是**给好的**，别改、别删。

**0010 用前九课学过的东西，不引入新语法**（这一课新学的只有「栈与队列」这两个结构本身）：

- `from collections import deque`：`append` 进队、`popleft` 出队、`q[0]` 看队头
- 列表两端：`append` 进栈、不带参数的 `pop` 出栈、`st[-1]` 看栈顶
- 类的写法（第 17 课才展开，这一课照任务里给好的骨架填方法体）：`class` / `__init__` / `self`
- `from tools import …`：`make_perm` / `make_mixed` / `shuffle` / `rand_int` / `show_count` /
  `show_time` / `ratio_hint` / `timed`（这一课不自己写计时，用 `timed(函数, 参数…)` 或给好的 `t0` / `t1`）
- `try` / `except IndexError as exc:`（任务 1 那一段是**给好的**，它把空栈 `pop` 的报错接住）
- `if __name__ == '__main__':` 这一层守卫：判分要 import 你的任务文件，**每个任务里都给你写好了，别删**

**0010 不用**：递归（这一课的 DFS 那种走法还没学）、`heapq`、`itertools`、`Counter` / `defaultdict`、
`timeit.repeat`、`lambda`。`tools.py` 是**给好的**公共工具（确定性数据、固定格式的打印行、计时），别改。
任务 5 的 `range_max` 暴力版也是**给好的对照**，别改。

**0016 把第 3 课那笔账再算一遍，不引入新语法**（这一课新学的只有「哈希表为什么快」这件事本身）：

- 字典与集合的字面量与 `set()`、`dict.get(键, 默认值)`、`cnt[x] = cnt.get(x, 0) + 1`
- `in` / `add` / 下标取值；`hash(键)`、`hash(键) % 桶数`
- `type(e).__name__` 与 `str(e)`；`try` / `except` 接住「列表当键」抛出的异常
- `round(0.1 + 0.2, 10)`——浮点当键时先归一到固定小数位
- `from collections import Counter`（任务 1 里那一版是**给好的对照**，用来看「手写字典版与它一致」）
- 计时用给好的 `t0 = time.perf_counter()` / `t1` 两行把要量的那段包起来（`import time` 已给好）

**0016 不用**：递归、`heapq`、`itertools`、`defaultdict`、`timeit.repeat`、`lambda`。
任务 4 的 `reason` 那一句要自己写汉字理由，判分看的是长度与「有没有还留着 TODO」，不逐字比。
**`run_tests.py` 会起探针进程 import 你的任务文件**，所以函数名与参数都是判分接口，别改；
`if __name__ == '__main__':` 那一层守卫（任务 5 有）是给好的，删了 import 一次就会把 `print` 重放一遍。

**0017 用第 1 到 12 课学过的东西**（这一课新学的是「用嵌套列表表示树」与「递归返回值汇总子树」）：

- 嵌套列表当数据：`None` 表示空树、`[值, 左, 右]` 表示一个结点，由给好的 `tools.node(v, l, r)` 搭出来
- 递归函数的两种形状：传 `out=None` 当**累加器**（任务 1 / 4），与「两个孩子交回答案、在根上合并」（任务 2 / 3）
- `from collections import deque` 写层序遍历（第 10 课那条队列）
- `import sys`：`sys.getrecursionlimit()` 看默认上限（任务 3 量的就是它）；任务 4 量那条 2000 层的链时**临时**把它调高、`finally` 里还原——那一段是**给好的**
- `try` / `except RecursionError`：只在主块那几段用（**给好的**），任务 3 的 `height` 里**不许**接住它
- 只从 `tools` 里取：`node` / `show_count` / `show_label` / `show_pair` / `show_recursion_error` / `timed`

**0017 不用**：显式栈版的迭代遍历（这一课要写的就是递归）、`heapq`、`itertools`、`lambda`、
`lru_cache`（那是第 24 课的事）。`tools.py` 是**给好的**公共工具，别改；
任务 4 的 `preorder_concat` 拼接版**是故意的**，别把它改成累加器。

**0018 用前 17 课学过的东西**（这一课新学的只有 `heapq` 与「上浮 / 下沉」这两个动作）：

- `import heapq`：`heapify` / `heappush` / `heappop` / `heapreplace` / `nlargest`
- 列表当堆：`h[0]` 是最小值，**其余位置没有顺序**；结点 `i` 的孩子是 `2i + 1` 与 `2i + 2`、父结点是 `(i - 1) // 2`
- 用负数存最大堆：`heappush(lo, -v)` 与 `-lo[0]`（任务 3 的对顶堆）
- `import random` 与固定种子：`random.seed(11)` / `seed(5)` / `seed(9)`——数据是**确定的**，判分按同一个种子重算
- 类与方法的写法（第 17 课那条「用嵌套列表表示树」之外的另一种结构）：任务 4 的 `class MinHeap` 骨架已经给好，填四个方法
- 只从 `tools` 里取：`best_of` / `show_count` / `show_label` / `show_pair` / `show_time` / `timed`

**0018 不用**：`itertools`、`lambda`、`lru_cache`、`Counter` / `defaultdict`。
任务 1 的 `merge_list`（每轮排序版）与任务 4 的 `heap_ok` / `check_*` 验证器都是**给好的对照**，别改；
`heapq` 的 `_siftdown` 这类内部名字别去调——这一课要你在任务 4 里自己把上浮与下沉写出来。

**0021 用第 19、20 课刚学的两样**（图与并查集），其余都是前 18 课的东西：

- 网格当图：`blocked[r][c]` 的 `True` 是**不能走**；邻居用 `tools.DIRS` 与 `dr, dc in DIRS` 那套写法
- 邻接表当图：`adj[u]` 是点 `u` 的邻居表（`tools.make_adj` 搭出来的）
- 显式栈与队列：`stack.pop()` / `deque.popleft()`（**不写递归**——递归上限 1000、网格一条路就能走几千格）
- 并查集那一份只有三行：判分与 `tools` 里已经给好了并查集的接口（`UnionFind(n)` / `union` / `components()`）
- `import random`（有的那一份用来造数据）、`tools.timed` 量耗时
- 只从 `tools` 里取：`DIRS` / `make_grid` / `make_maze` / `make_adj` / `BLOCKED_BIG` / `show_*` / `timed`

**0021 不用**：递归版的 DFS（这一课一律显式栈——课件的 6×6 空方格递归要跑 9.68 秒、1847 万次调用）、
`heapq`、`itertools`、`lru_cache`、`functools`。任务 4 里**出队时标记那一版是要保留的写法**，
别把它「修」成入队时标记——两版摆在一起才看得出四倍的差距。

**0025 用第 24 课学的「状态、转移方程、边界」三件套**（这一课新学的就是背包的几种方向）：

- 列表推导式造表：`dp = [0] * (C + 1)`、`dp = [[0] * (C + 1) for _ in range(n + 1)]`
- 二维表与一维滚动数组、内层循环的正序与逆序
- `float('-inf')` 当「凑不出来」的标记（`tools.NEG`），以及拿它比大小前先判 `!= NEG`
- `random.seed(5)` 那一批数据是**给好的**（`tools.make_cases`）；判分按同一个种子复现同一批
- 只从 `tools` 里取：`brute01` / `make_cases` / `NEG` / `fmt` / `show_case` / `show_check` / `show_json` / `show_note` / `show_pair`

**0025 不用**：递归、`heapq`、`itertools`、`lru_cache`、`functools`、`lambda`、`Counter` / `defaultdict`。
`brute01`（枚举参照实现）是**给好的裁判**，别改；文件名、函数名、函数签名、
`CASES_*` 的种子与上限、带 `# 别改` 的每一行打印都是判分接口。

**0026 用第 24、25 课学的 DP 三件套，再加这一课新学的两件事**：
「状态得自己设计」与「区间 DP 必须按区间长度枚举」：

- 二维表：`dp = [[0] * (m + 1) for _ in range(n + 1)]`（任务 2 的 LCS）、
  区间表 `dp = [[0] * n for _ in range(n)]`（任务 3、4）
- `import bisect` 与 `bisect.bisect_left`（任务 1 的二分版；严格递增用 `left`，不是 `right`）
- 前缀和：`pre[j + 1] - pre[i]` 拿区间和（任务 4 的 `sum(i..j)`）
- `from functools import lru_cache` 写暴力版（任务 4 的 `stone_brute`）——**记在元组上**，列表不能当键
- `import random` 与固定种子（`seed(11)` / `seed(12)` / `seed(9)`）：对拍是这一课的主要手段
- 只从 `tools` 里取：`best_of` / `show_count` / `show_label` / `show_pair` / `show_time`

**0026 不用**：`heapq`、`itertools`、`Counter` / `defaultdict`、`lambda`（任务 1 的 `lis_recover`
里那一句「找最长那条的结尾下标」可以用普通循环写）。给好的 `is_subsequence` 与判分自己那套参照实现
（`model_*`）都别去改；四条固定格式的打印行（`计数 NN …` / `耗时 NN …` / `<标签> <值>` /
`<标签> <值1> <值2>`）是判分接口。

**0027 这一课只要补四个任务里的十来个函数**，其余全是给好的骨架：

- `json.loads` 与 `json.JSONDecodeError`（任务 2 的核心；第六种形态两版都救不了，交回字符串标记）
- 字符串手法：`raw.strip()`、`text.find('{')` 与 `text.rfind('}')`、切片、`re`（加固版剥围栏要用
  `re.S`，否则 `.` 不匹配换行，JSON 是多行的）
- 字典取键写 `d.get('family')` 这类写法（任务 3、4 里要把失败当成一种值带着往下走）
- 函数当参数传（任务 1 的 `model` 与任务 4 的 `run_trial`）——还是第 15 课那道「缝」的用法
- `tools` 给好的东西：`FAMILIES`（八张族名表）、`PROBLEMS`（六道题面）、`sample_texts()`（六种形态）、
  `PROBE_SAMPLES`、`show_line` / `show_banner` 这些打印助手

**0027 不用**：`requests` 或任何联网库（这一课**离线**：`call_model` 的职责就是
`raise NotImplementedError(...)`），也不用 `socket`（判分第 5 层自己会把 `socket.socket`
换成会抛异常的版本、核对连接尝试次数为 0）。`tools.py` 与 `run_tests.py` 是**给好的**，别改；
六道题面的关键词表里那条**假阳性**（「合并果子」里的「重量」让背包也上了候选）要**如实保留**——
它正是这一段要暴露的东西。

**0004 另外不写 f-string**：0003 那几个带 `f'{x:.6f}'` 的 `print` 行是**给好的**，照抄即可；
0004 的输出全是给定的 `print` 行，自己写代码时用不着格式化。0005 同理：要打印的值都是现成的 `print` 行，
自己不用写格式化。

**`input()` 不带提示参数**：提示文字会一起写进 stdout，而判分是按行读 stdout 的，会把它当成答案。

**给好的代码别改**：每个任务里造数据、算结果、`print` 那几行都是判分接口——
`run_tests.py` 按行读它们打印出来的东西。要写的是标着 `TODO` 的那几段。
0007 里对应的是「函数名与文件名」：`solve_a.py` / `solve_b.py` / `selfcheck.py` / `scale_check.py`
这四个文件名，以及每个文件里已经写好的函数名，都是判分接口，别改。

## 任务表 · 0003（`0003-python-list-dict-cost/`）

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 三种查法的耗时对照 | `task1_lookup.py` | 补三段计时：200 次查询分别走列表 `in`、集合 `in`、字典查 | `t0 = time.perf_counter()` 在循环前、`t1` 在循环后，相减 | 三行都量到；列表那行 ≥ 0.05 秒；列表比集合、字典各慢 50 倍以上 |
| 2 · 两种队列的代价 | `task2_queue.py` | 出队 20 万次：先用 `list.pop(0)`，再换成 `deque.popleft()` | `deque` 用 `append` 进队、`popleft` 出队；两种写法的出队顺序要一致 | 两行都量到；`pop(0)` ≥ 0.1 秒；`popleft` 比它快 20 倍以上；`出队顺序一致 True` |
| 3 · 列表查重改集合查重 | `task3_dedup.py` | 把给好的列表版查重改写成集合版（换容器 + 换一行 `add`） | 只动两处：`seen_set = set()` 与 `seen_set.add(x)`；`in` 不用改 | 两版的「不同元素 / 重复」个数一致、`结果一致 True`；集合版比列表版快 3 倍以上 |
| 4 · 放大十倍看趋势 | `task4_scale.py` | 同一段查法，n 从 `10^5` 到 `10^6` 各量一次列表与集合 | 两组代码形状一样，四个 `TODO` 是同一件事 | 四行都量到；列表涨到 4-40 倍之间；集合涨不到 5 倍 |

每个任务的期望输出形状（格式是判分接口，照抄给好的 `print` 行即可）：

```text
列表 in 1.502341 秒
集合 in 0.000018 秒
字典查 0.000016 秒

pop(0) 200000 次 2.741234 秒
popleft 200000 次 0.013456 秒
出队顺序一致 True

列表版 不同元素 5000 重复 15000 0.412345 秒
集合版 不同元素 5000 重复 15000 0.015678 秒
结果一致 True

n=100000 列表 in 0.152134 秒 集合 in 0.000017 秒
n=1000000 列表 in 1.512345 秒 集合 in 0.000018 秒
列表 in 放大十倍变成 9.94 倍
集合 in 放大十倍变成 1.06 倍
```

## 任务表 · 0004（`0004-python-function-basics/`）

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 摊平版改写成四个函数 | `task1_functions.py` | 照 `flat_odd.py` 写 `read_n()` / `odd_count(n)` / `show(count)` / `solve()`，每个只管一件事 | 算法一行都不许改，只是把 `print` 换成 `return`、把结果交给调用处；负数归零留在 `read_n` 里；最后一行 `solve()` 是给好的 | 四组验收输入 0→0、1→1、10→5、1234567→617284 与 `flat_odd.py` 逐字一致；四个函数名都在 |
| 2 · 默认值只算一次 | `task2_default_arg.py` | 三个 `TODO`：`show_default(arg=i)`、`grow_bad(a, L=[])`、`grow_ok(a, L=None)` | 默认值写在 `def` 那一行，它在定义时就算好了；陷阱版照课件原样写；修好版判 `L is None` 才新建空列表，调用处给进来现成列表要接着用 | A 打出 5；陷阱版三次依次 `[1]` / `[1, 2]` / `[1, 2, 3]`、`b1 is b2` 是 True、回头看 `b1` 已是 `[1, 2, 3]`；修好版 `[1] [2] [3]`、`g1 is g2` 是 False、接现成列表 `[7, 8] [7, 8]` |
| 3 · 全局变量传状态版 | `task3_global_state.py` | 同一道题再写一版：`read_n()` / `odd_count()` / `show()` 全靠全局变量 `n_global`、`count_global` 传数据 | 函数里改全局变量，函数体第一行先写 `global`；这一版**没有** `solve`，数据自己流动 | 四组输入的第一行与任务 1 的函数版逐字一致；函数外面读得到 `n_global` 与 `count_global` |
| 4 · 别改坏调用处的列表 | `task4_copy_list.py` | 两个函数做同一件事：`add_inplace(nums, delta)` 就地改，`add_copy(nums, delta)` 先 `nums = nums[:]` 再改副本 | 用下标循环 `for i in range(len(nums))`；副本版别忘了那一行复制 | 两份返回都是 `[11, 12, 13]`；就地版把调用处的 `a` 也改成 `[11, 12, 13]`；副本版的 `b` 仍是 `[1, 2, 3]` |

### 0004 的期望输出形状

```text
$ py task1_functions.py            （敲 10 回车）
5

$ py task3_global_state.py         （敲 10 回车）
5
函数外读到全局 n_global 10
函数外读到全局 count_global 5

$ py task2_default_arg.py
A 默认值 5
B 陷阱版 第 1 次 [1]
B 陷阱版 第 2 次 [1, 2]
B 陷阱版 第 3 次 [1, 2, 3]
B 陷阱版是同一个列表 True
B 陷阱版 b1 现在 [1, 2, 3]
B 修好版 [1] [2] [3]
B 修好版是同一个列表 False
B 修好版接现成列表 [7, 8] [7, 8]

$ py task4_copy_list.py
就地版 返回 [11, 12, 13]
就地版 调用处 [11, 12, 13]
就地版 改坏了调用处 True
副本版 返回 [11, 12, 13]
副本版 调用处 [1, 2, 3]
副本版 没改调用处 True
```

任务 2 的 `B 陷阱版` 是「调用一次、立刻打印一次」，所以看得见叠加的过程；
把三次都调用完再一起打印的话，三个名字打出的是同一个列表。
`solutions/0004-python-function-basics/` 里连 `run_tests.py` 与 `flat_odd.py` 都有一份，
可以整个目录拷进自己的任务目录直接跑。

## 任务表 · 0005（`0005-python-comprehension-builtins/`）

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 十段循环逐段改写成一行 | `task1_rewrite.py` | 把 `loops_original.py` 里那十段循环各压成一行：能写推导式的写推导式，能换现成函数的换现成函数 | 只动写法、不动结果；十条各自对应哪个现成函数，看文件开头的对照表 | 十行输出与 `loops_original.py` 逐字一致；另查大纲要求的八个内置函数各至少改写一处 |
| 2 · 带条件与嵌套的推导式 | `task2_nested.py` | 两个 `if` 子句、两个 `for` 子句展平、推导式里嵌推导式转置，以及「推导式的目标名不泄漏」 | 一行里 `for` 与 `if` 的先后，与循环版从上到下一致 | 01–04 四行结果对上；05 打出 `旧值`（外面的 `y` 没被推导式盖掉）；06 是给好的对照（循环版把 `y` 留成 3） |
| 3 · 生成器表达式与惰性 | `task3_generator.py` | 一处列表推导式改成生成器版、一处换成列表版，再用 `any` / `all` 各写一行，并给判分交一个「交回生成器」的函数 | 圆括号 = 要一个才算一个；`any` / `all` 能定结果就不再往下取 | 01 是 0、04 是 0（第二次要什么都没有）、06 是 6（建表就算完）、08 是 3、10 是 4；判分另起探针 import 你的函数，确认它是生成器、`len` 与下标都报 `TypeError` |
| 4 · 把下标循环换成 `enumerate` 与 `zip` | `task4_zip_enum.py` | 编号循环、`enumerate` 表、`zip` 截断、取一列、配对表、用 `zip` 转置 | `enumerate` 的 `start=1`；`zip` 到最短的用完就停 | 七行结果对上：三行编号从 1 起、截断长度是 2、转置是 4 组 |
| 5 · `sorted` 的 key 与 `list.sort` 的返回值 | `task5_sort.py` | 排行榜的键函数、要一张降序新表、把原地排序的返回值接住、用给好的键函数排一遍 | 元组按字典式顺序比；`sorted` 返回新表、`list.sort` 返回 `None` | 01 排行榜固定；02 与 04 原数据没动；05 是 True；06 原表被改；07 同分保持原顺序（稳定）；08 取键 4 次 |
| 6 · `any` 与 `all` | `task6_any_all.py` | 两种判定循环的换法、空序列的口径、判空、短路 | `any([])` 是 `False`、`all([])` 是 `True` | 01–04 四行；05 是 True（不判空的那版）、06 是 False（判空版）；07、08 两版一致；10 只看了 1 个 |

### 0005 的期望输出形状

判分按行读这些 `print`，所以格式（标签与顺序）别改：

```text
$ py task1_rewrite.py            （十行要与 py loops_original.py 一字不差）
01 平方 [9, 1, 16, 0, 49, 4]
02 正数 [3, 4, 7, 2]
03 总和 15
04 最大 7
05 正数个数 4
06 有大于5 True
07 全部非负 False
08 词长 [4, 3, 5]
09 转整数 [3, -1, 4]
10 排行榜 [('A01', 95), ('A04', 95), ('A02', 80), ('A03', 80)]

$ py task2_nested.py
01 两个条件 [6, 8]
02 展平 [1, 2, 3, 4, 5, 6]
03 转置 [[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]
04 平方表 [0, 1, 4, 9]
05 推导式外 y 旧值
06 循环外 y 3

$ py task3_generator.py
01 建好之后 calls 0
02 第一次 sum 55
03 第一次 sum 之后 calls 6
04 第二次 sum 0
05 第二次 sum 之后 calls 6
06 建表之后 calls 6
07 表能反复用 55 55
08 any 提前停 calls 3
09 any 的值 True
10 all 提前停 calls 4
11 all 的值 False
12 map 第一次 [3, -1, 4]
13 map 第二次 []

$ py task4_zip_enum.py
01 编号 1 第一题 80
01 编号 2 第二题 95
01 编号 3 第三题 60
02 enumerate 表 [(1, '第一题'), (2, '第二题'), (3, '第三题')]
03 zip 截断长度 2
04 zip 截断表 [('第一题', 80), ('第二题', 95)]
05 分数列 [80, 95, 60]
06 配对表 [('第一题', 80), ('第二题', 95), ('第三题', 60)]
07 转置 [[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

$ py task5_sort.py
01 排行榜 [('A01', 95), ('A04', 95), ('A02', 80), ('A03', 80)]
02 原记录没动 True
03 sorted 新表 [95, 88, 70]
04 原分数没动 [88, 95, 70]
05 sort 的返回值是 None True
06 被 sort 改过的原表 [70, 88, 95]
07 按分数升序 [('A03', 80), ('A02', 80), ('A01', 95), ('A04', 95)]
08 取键次数 4

$ py task6_any_all.py
01 有正数 True
02 全部为正 False
03 空数据 any False
04 空数据 all True
05 空数据 不判空版 True
06 空数据 判空版 False
07 非空数据 两版 True True
08 有负数 两版 False False
09 any 结果 True
10 any 看了几个 1
```

任务 3 的 `01` 与 `04` 两个 0 不是错：前者说明生成器写出来时还没开始算，后者说明第一次取完就空了。
任务 5 的 `05` 要的就是 `True`——原地排序交回来的是 `None`，`05` 这一行正是在确认这件事。
`solutions/0005-python-comprehension-builtins/` 里连 `loops_original.py` 与 `run_tests.py` 都有一份，
可以整个目录拷进自己的任务目录直接跑。

## 任务表 · 0006（`0006-python-io-and-debug/`）

八个 `sample*.in` 就是这一课要认的五种格式（外加几个边界排版），任务里拿它们当输入：

| 文件 | 是什么 |
| --- | --- |
| `sample1.in` | 单行多整数：`3 1 4 1 5 9 2 6` |
| `sample2.in` / `sample2b.in` | 多行整数：前者第一行给 `n`；后者不给 `n`、且第 4 行是空行 |
| `sample3.in` / `sample6.in` | 矩阵 `3 4` 加 12 个数：前者排版整齐，后者**同一份数、换行位置被打乱** |
| `sample4.in` | 混合行列：矩阵后面跟一个 `q`、再 `q` 行「行 列」 |
| `sample5.in` / `sample5b.in` | 多组数据：组间有空行、末尾还有一个空行；前者给组数、后者不给 |

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 五种格式各解析一次 | `task1_parse.py` | 补六个解析函数：单行多整数、多行整数、矩阵、混合行列、多组数据，各交出指定的数据结构 | 一律按空白读（`split()`），矩阵再按 `m` 个一段切开；混合那份用显式 `pos` 指针推；多组那份每组读完 `pos += n` | 五组样例各打出课件写死的那份结构；`sample6.in`（折行）与 `sample3.in` 打出**同一个**矩阵 |
| 2 · 先读完再算 | `task2_read_then_compute.py` | 把给好的「边读边算」版改写成「先读完、再算」，再拆成解析函数 + 算法两段 | 改写后从 `text` 出发，不出现 `input()`、不再碰 `sys.stdin`；`parse_matrix` 交 `(n, m, 二维列表)`，`sum_matrix` 只面对数据结构 | 给好的对照在整齐数据上 78、折行上 **36**（这是要看的现象，别改它）；你的两版在 `sample3` 与 `sample6` 上**都**是 78，每行长度 `[4, 4, 4]` |
| 3 · 读进来的都是字符串 | `task3_string_trap.py` | 把几个反直觉的结果亲手打出来：字符串直接比、直接排、直接求最大，再各来一遍「转成整数」的版本 | 字符串比较按字符逐个比编码；混着比才会报 `TypeError` | 八行：`True` / `False` / `['10', '100', '2', '9']` / `['2', '9', '10', '100']` / `9` / `100` / `TypeError` / `[31, 9, 100]` |
| 4 · 用打印缩小出错范围 | `task4_debug.py` | 解析函数里有一处切片写错了（每行少 1 个数）；先补三行诊断打印，再把切片改对，最后用 `repr` 看不可见字符 | 切片右端不包含；`repr` 会把 `\n` 显示出来——**别用 `splitlines()` 取这一行**，它会把行尾换行符去掉 | 诊断打出「n m 3 4」与三行「第 i 行长度」；改对后每行长度 `[4, 4, 4]`、总和 78；`repr` 打出 `'3 1 4 1 5 9 2 6\n'` |
| 5 · 提示混进标准输出 | `task5_clean_stdout.py` | 写一版干净的（`input()` 不带参数、`print` 只打答案）与一版脏的（带提示、带前缀），让判分**验**得出来 | 提示走 stdout 那条流，评测机读的正是它 | clean 的 stdout 逐字是 `20\n`；dirty 的 stdout 里混进了 `请输入` 或前缀；判分把 clean 换成带提示的版本后仍能验出污染 |
| 6 · 提交前的两个搜索与一次逐字比对 | `task6_submit_check.py` | 写一个逐字比对的 `same_output`，再交出提交前要搜的两个关键词 | 放过的是文本文件末尾那一个换行；抓的是行尾多一个空格、多一行、少一行、多一个前缀——**别用 `strip()`** | 四行自检 `True` / `True` / `False` / `False`；两个关键词是 `input(` 与 `print(`；判分的探针拿八组文本试它，逐组对上 |

### 0006 的期望输出形状

判分按行读这些 `print`，所以格式（标签与顺序）别改：

```text
$ cat sample1.in | py task1_parse.py one
01 单行多整数 [3, 1, 4, 1, 5, 9, 2, 6]

$ cat sample2.in | py task1_parse.py lines
02 多行整数 [3, -1, 4, 2, 7]

$ cat sample3.in | py task1_parse.py matrix
03 矩阵 n m 3 4
03 矩阵 [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]

$ cat sample4.in | py task1_parse.py mq
04 矩阵与查询 [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
04 查询 [(1, 1), (3, 4)]

$ cat sample5.in | py task1_parse.py groups
05 多组数据 [[1, 2, 3], [10, 20, 30, 40]]

$ cat sample3.in | py task2_read_then_compute.py running
边读边算 78
$ cat sample6.in | py task2_read_then_compute.py running
边读边算 36

$ cat sample6.in | py task2_read_then_compute.py tokens
先读完再算 78
$ cat sample6.in | py task2_read_then_compute.py parsed
解析 n m 3 4
每行长度 [4, 4, 4]
解析后求和 78

$ py task3_string_trap.py
01 字符串 10 < 9 True
02 字符串 2 < 10 False
03 直接排序 ['10', '100', '2', '9']
04 按整数排序 ['2', '9', '10', '100']
05 字符串最大值 9
06 转整数后最大值 100
07 混着比的报错类型 TypeError
08 解析层转完 [31, 9, 100]

$ cat sample3.in | py task4_debug.py diagnose
诊断 n m 3 4
诊断 第 0 行长度 4 [1, 2, 3, 4]
诊断 第 1 行长度 4 [5, 6, 7, 8]
诊断 第 2 行长度 4 [9, 10, 11, 12]
诊断 总和 78
修复后 每行长度 [4, 4, 4]
修复后 总和 78

$ cat sample1.in | py task4_debug.py repr
原文 repr '3 1 4 1 5 9 2 6\n'
原文长度 15

$ echo 10 | py task5_clean_stdout.py clean
20

$ echo 10 | py task5_clean_stdout.py dirty
请输入 N：答案是： 20

$ py task6_submit_check.py
01 完全相同 True
02 末尾换行 True
03 行尾多空格 False
04 少一行 False
05 搜两个关键词 ['input(', 'print(']
```

任务 2 的 `36` 不是笔误：那是**给好的对照版**在折行数据上的输出，它一个错字都不报。
你要交的 `先读完再算` 两行必须都是 `78`。
任务 4 的 `诊断 总和` 在你把切片改对之后会是 `78`（改之前是 `54`）；
判分看的是这几行**打出来了**，以及改对之后每行长度是 `[4, 4, 4]`。
任务 5 的 `dirty` 那一行是**故意写脏的**：它的用途就是让判分验出 stdout 被污染了。

`run_tests.py` 六个任务一起判，一条条给 PASS / FAIL：

```text
任务 1 · 五种格式各解析一次       8 条（五组数据 + 查询 + n m + 折行组）
任务 2 · 先读完再算               6 条（两条对照 + 两种排版 × 两段）
任务 3 · 读进来的都是字符串       8 条（对应 01–08 那八行）
任务 4 · 用打印缩小出错范围       5 条（三行诊断 + 修复后 + repr）
任务 5 · 提示混进标准输出         3 条（clean + dirty + 判分自己的探针）
任务 6 · 提交前的两个搜索与比对   7 条（四行自检 + 关键词 + 探针八组）
```

留白版原样跑是不通过的：解析函数都交回空表、诊断一行都不打、
`clean` 打出 `0`、`same_output` 永远 `False`——那是起点，不是 bug。
`solutions/0006-python-io-and-debug/` 里连 `run_tests.py` 都有一份：
把那里的六个 `.py` 拷进任务目录覆盖同名文件，`py run_tests.py` 应当六个任务全过（本机实测两秒左右）。

## 任务表 · 实验一（`0007-lab-01-run-one-problem/`）

题面在 `0007-lab-01-run-one-problem/problems.md`（两道题、两种输入格式），
课件里的任务书是 `lessons/0007-lab-01-run-one-problem.html`。

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 题目 A 跑通（一串整数） | `solve_a.py` | 补三段：`read_all()` 一次读完输入、`parse_input(text)` 交出 `(n, a)`、`count_distinct(a)` 交出「不同数值的个数」 | 别用 `input()` 逐行读——样例只有一行时它能过，`tests/a3.in` 一折行就错；查重那一行用什么容器决定十万个数跑不跑得完 | 四组样例逐字一致；`tests/a3.in` 与 `sample_a2` 是同一份数，答案也必须是 `4`；`tests/a_big.in`（10 万个数）在 2 秒内跑完 |
| 2 · 题目 B 跑通（矩阵） | `solve_b.py` | 补四个函数：`read_all()`、`parse_input(text)` 交出 `(n, m, grid)`、`row_maxes(grid)`、`most_common(grid)` 交出 `(分数, 次数)` | 题面只约定个数与先后顺序，所以按空白读、再按 `m` 个一段切开；「并列取最小」把键写成 `(-次数, 分数)` 取第一条 | 两组样例逐字一致（`sample_b2` 的答案是 `5 2`，写成 `max(counts, key=counts.get)` 会打出 `10 2`）；`tests/b3.in` 与 `sample_b2` 答案相同；`tests/b_big.in`（300×100）2 秒内跑完 |
| 3 · 写自己的自测脚本 | `selfcheck.py` | 补三个函数：`run_solver(script, in_path)` 起子进程跑脚本、`normalize(text)` 整理输出、`check_one(...)` 比对并打印一行 | 路径按 `__file__` 算（判分在副本目录里试它）；退出码不是 0 就报错原因；比对前去掉行尾空白与末尾空行 | 四组样例各一行 `样例 A1 PASS` …… 最后一行 `自测通过 4/4 组`；判分的探针把 `solve_a.py` 换成 `probe_wrong_a.py` 后，A1/A2 报 FAIL 而 B1/B2 仍 PASS |
| 4 · 两种容器的量级对照 | `scale_check.py` | 补 `distinct_by_list`、`distinct_by_set` 与那个预计值：同一份数据上各量一次，再推 n 放大 10 倍要多久 | 列表查重的比较次数按规模**平方**涨：规模 10 倍 ≈ 时间 100 倍（不是 10 倍） | 三行都量到；列表 ≥ 0.3 秒、集合 ≤ 0.05 秒、列表比集合慢 20 倍以上；两行「不同元素」一致；预计值 > 1 秒且接近实测的 100 倍 |

### 实验一的期望输出形状

```text
$ cat sample_a1.in | py solve_a.py
3

$ cat sample_b2.in | py solve_b.py
30 30 7 9
5 2

$ py selfcheck.py
样例 A1 PASS
样例 A2 PASS
样例 B1 PASS
样例 B2 PASS
自测通过 4/4 组

$ py scale_check.py
n=20000 列表 in 用时 0.855123 秒 不同元素 20000
n=20000 集合 in 用时 0.001234 秒 不同元素 20000
列表版放大 10 倍预计 85.51 秒 超出 1 秒时限 True
```

判分脚本 `run_tests.py` 分五层，一层里几条检查各自给 PASS / FAIL：

```text
第 1 层 · 样例（题面给的四组，小数据）
第 2 层 · 换行被打乱的小数据（同一份数、另一种排版）
第 3 层 · 大数据（题目 A 十万个数；限时 2.0 秒）
第 4 层 · 你自己的自测脚本（selfcheck.py）
第 5 层 · 规模对照（scale_check.py）
```

第 1、2 层没过时，第 3–5 层直接跳过（样例都没过，大数据组的失败信息没有参考价值）。
留白版原样跑是不通过的：`solve_a.py` 打出 `0`、`solve_b.py` 打出空行与 `0 0`、
`selfcheck.py` 一组都不报、`scale_check.py` 两行的秒数都小到 `0.000000`——那是起点，不是 bug。

`solutions/0007-lab-01-run-one-problem/` 里连 `run_tests.py` 与 `probe_wrong_a.py` 都有一份：
把那里的五个 `.py` 拷进任务目录覆盖同名文件，`py run_tests.py` 应当五层全过（本机实测一秒半左右）。

## 任务表 · 0009（`0009-linear-structures-two-pointers/`）

同一道题「给定数组 a 与整数 S，求和恰好等于 S 的连续区间有多少个」，
分五个任务写完三种走法（暴力 → 前缀和 → 双指针），再对拍、再量耗时。

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 暴力版：先写对，再当基准 | `task1_brute.py` | 补 `count_brute(a, S)`：两层循环枚举所有区间，边扩边累加 | 外层 `for l in range(n)` 里先写 `s = 0`；内层 `for r in range(l, n)`，先 `s += a[r]` 再判 `s == S`。`r` 从 `l` 起，不是从 0 起 | 小数组 `[4, 0, 0, 4, 0]`、S=4 打出 9；2000 个正整数打出 44；含负数的 300 个数打出 106 |
| 2 · 前缀和：把区间和变成两次取表相减 | `task2_prefix.py` | 补 `build_pre(a)` 与 `count_prefix(a, S)`：建 `pre[0] = 0` 的表，用字典一边扫一边查 | 表长是 `n + 1`；区间和是 `pre[r + 1] - pre[l]`；`seen` 的初值写 `{0: 1}`；**每轮先查后记** | 表是 `[0, 4, 4, 4, 8, 8]`；小数组 9、正数 44、含负数 106；含负数时**仍与暴力版一致** |
| 3 · 双指针：两个下标都只往前走 | `task3_window.py` | 补 `count_window(a, S)`（滑动窗口）与 `count_window_broken(a, S)`（去掉 `r < n` 的错版） | `while r < n and s < S:` 里右扩；`if s == S: count += 1`；每轮末尾 `s -= a[l]`。错版只差一处：条件写成 `while s < S:` | 全正数上双指针 44、与暴力一致；含负数上双指针只给 4、与暴力（106）**不一致**；错版在 `[1, 2]`、S=100 上报 `IndexError` |
| 4 · 对拍：三个版本答案对不对得上 | `task4_compare.py` | 补 `check_three(a, S)` 交回三版答案，`find_counterexample(arrays, S)` 找出第一个不一致的数组 | 拿暴力版当基准；`if w != b: return arr` 找到就立刻交回，没有就 `None` | 小数组三版答案 `(9, 9, 4)`；第一个反例是 `[4, 0, 0, 4, 0]`；全正数上三版**始终一致**；含负数上 `(106, 106, 4)` |
| 5 · 三个版本的实测耗时对照 | `task5_scale.py` | 补 `time_three(a, S)` 量三个版本各一次的秒数，`best_of_three(a, S)` 跑三次逐列取最小 | 用 `tools.timed(函数, 参数…)`，它交回 `(答案, 秒数)`；三个版本**分开量**，别把一次计时包住三个函数 | 三个规模都量到（秒数不能全是 0）；暴力翻倍涨 2.5 倍以上、两个线性版涨得比它少；暴力比双指针慢 100 倍以上 |

### 0009 的期望输出形状

判分读两种固定格式行，**编号与标签都别改**：

```text
$ py task1_brute.py
小数组 9
全正数 2000 个数 44
含负数 300 个数 106
计数 01 暴力 9

$ py task3_window.py
小数组 双指针 4
小数组 暴力 9
小数组 两版答案一致 False
全正数 2000 个数 双指针 44
全正数 与暴力一致 True
含负数 300 个数 双指针 4
含负数 与暴力一致 False
含负数 前缀和与暴力一致 True
错版在 [1, 2] 上报错 IndexError: list index out of range
计数 03 双指针 正数 44
计数 04 双指针 含负数 4

$ py task5_scale.py
耗时 01 暴力   n=500 0.003570 秒
耗时 02 前缀和 n=500 0.000132 秒
耗时 03 双指针 n=500 0.000059 秒
耗时 01 暴力   n=1000 0.014370 秒
耗时 02 前缀和 n=1000 0.000185 秒
耗时 03 双指针 n=1000 0.000071 秒
倍数 04 暴力  放大 4.03
倍数 05 前缀和放大 1.40
倍数 06 双指针放大 1.20
耗时 01 暴力   n=2000 0.057952 秒
耗时 02 前缀和 n=2000 0.000340 秒
耗时 03 双指针 n=2000 0.000145 秒
倍数 04 暴力  放大 4.03
倍数 05 前缀和放大 1.84
倍数 06 双指针放大 2.04
倍数 07 暴力比双指针 400.97
倍数 08 前缀和比双指针 2.34
```

**`False` 有两处是要的，不是错**：`小数组 两版答案一致 False` 与 `含负数 与暴力一致 False`
说明双指针版在含 0 / 负数的数组上给出与暴力版不同的答案——那正是这一课要你看的反例。
判分对这一行的期望同样是 `False`；打成 `True` 反而说明你写的不是课件那一版。
`倍数` 那几行每次跑都会有出入（两个线性版的 1.20 到 2.5 都可能出现），判分只看趋势，不核对具体数字。

留白版原样跑是不通过的（本机实测 34 条 FAIL、退出码 1）：四个函数都交回占位值，
所有计数打出 `0`、所有耗时打出 `0.000000`，还有几条「一致」的行因为两边都是 0 而碰巧成立——
判分对这几条另加了依赖检查（被依赖的那一行不对时，它也不给 PASS）。那是起点，不是 bug。

`solutions/0009-linear-structures-two-pointers/` 里连 `tools.py` 与 `run_tests.py` 都有一份：
把那里的五个 `.py` **一起**拷进任务目录覆盖同名文件（任务之间互相 `import`，别只拷一个），
`py run_tests.py` 应当五个任务全过（本机实测一秒出头）。

## 任务表 · 0010（`0010-stack-and-queue/`）

两套线性结构（栈与队列）各写一遍，再把它们放到四种题上：括号匹配、表达式求值、
滑动窗口最大值。

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 用列表写栈，用 deque 写队列 | `task1_stack_queue.py` | 补 `Stack` 的 `push` / `pop` / `top` / `is_empty` 与 `Queue` 的 `enqueue` / `dequeue` / `front` / `is_empty` 八个方法 | 栈在列表末尾进出（`append` / 不带参数的 `pop`）；队列一端进一端出，`deque` 的出队方法叫 `popleft`，不是 `pop`；`pop` 里别忘了 `return`，否则交回 `None` | 七行「一致」全打 `True`（出栈是入栈的反序、出队与入队同序、300 步随机操作里每一步的栈顶与队头都对得上）；空栈 `pop` 抛出 `IndexError: pop from empty list`；`计数 01/02/03` 是 `30 / 150 / 150` |
| 2 · 两种出队的代价 | `task2_queue_cost.py` | 出队 20 万次：先用 `lst.pop(0)`，再用 `dq.popleft()`，各量一次 | 两个循环各写各的、各自被一对 `t0` / `t1` 包住，别把两件事写进一次计时；列表那一版一定要写 `pop(0)`（**左端**），写成 `pop()` 量到的就是个位数倍数 | 两行耗时都量到、规模都是 `k=200000`；两版元素个数都是 200000、出队顺序一致；`deque 比列表快` 那一行 ≥ 20 倍（本机实测 98 倍上下） |
| 3 · 括号匹配与第一个出错位置 | `task3_brackets.py` | 补 `is_valid(s)` 与 `first_error(s)`：正确给 `True` / `-1`，否则给第一个出错的下标 | 只把**左括号**压栈；读到右括号先看栈空不空、栈顶对不对得上；整段读完还要 `return not st`。三种出错情形里第三种最容易漏：左括号没等到时，最**先**出错的是栈**最底下**那个，所以是 `st[0]` 不是 `st[-1]` | 九个用例逐字对上（`()[]{}` 与 `([)]` 与 `(]` 与 `((` 与 `()` 空串 `([{}])` 与 `)))` 与 `(()`）；配对的个数是 4；后三个的首个错位是 `-1 / 0 / 0`；`计数 01/02/03` 是 `4 / 0 / 1` |
| 4 · 后缀一遍、中缀两栈 | `task4_eval.py` | 补 `eval_rpn(s)`，以及中缀那两个：`parse(s)` 切段、`value(s)` 两栈求值 | 后缀：`b = st.pop()` **先弹的是右操作数**，`a` 后弹，按 `a - b` / `a // b` 算（写反了 `52-` 从 3 变 -3、`93/` 从 3 变 0）；除法用 `//`；中缀：`parse` 要用临时字符串把多位数字攒成一个 `int`，**扫完之后别忘了收最后一个数**（`'7'` 切出来是 `[7]`）；优先级比较写 `>=`，同优先级才从左往右算 | 后缀五组 `14 / 3 / 3 / 77 / 6` 全对、减法除法没写反；`切分 (12+3)*4` 是 `['(', 12, '+', 3, ')', '*', 4]`、`切分 7` 是 `[7]`；中缀六组 `15 / 9 / 40 / 8 / 4 / 18` 全对、`9-3+2` 是 8、`9-3-2` 是 4；`计数 01/02/03` 三行都是 `True` |
| 5 · 滑动窗口最大值：单调队列 | `task5_window_max.py` | 补 `max_window(a, k)`（单调队列）与 `bad_window(a, k)`（**故意**去掉队首过期检查的错版） | 队列里存**下标**；三条按顺序写：弹队尾（比 `a[i]` 小的都弹掉，用 `<=`）、入队、弹队首过期（`q[0] <= i - k`）；最后 `i >= k - 1` 才开始输出，少了它结果会多出 `k-1` 项。`bad_window` 只差**去掉队首那一条** | 课件那组 `[1, 3, -1, -3, 5, 3, 6, 7]`、k=3 是 `[3, 3, 5, 5, 6, 7]` 且与暴力一致；`[7, 1, 1, 1, 1]`、k=3 正确是 `[7, 1, 1]`、漏检查版是 `[7, 7, 7]`；排列 20 个数 k=4 的窗口个数是 17、k=1 与数组逐项相同、k=20 是 `[19]`；四档 k 上答案都与暴力一致；暴力那一列从 k=100 到 k=2000 涨 3 倍以上、单调队列那一列四档之间基本不动、k=2000 档上暴力慢 20 倍以上 |

### 0010 的期望输出形状

判分读两种固定格式行（`计数 NN <标签> <值>`、`耗时 NN <标签> k=… <秒数> 秒`）加一批带标签的 `print` 行，
**编号、标签与顺序都是判分接口**：

```text
$ py task1_stack_queue.py
栈 入栈顺序 [1, 10, 19, 25, …（30 个数的固定排列）]
栈 出栈顺序 [21, 15, 6, 26, …（同一串的反序，排列固定）]
栈 与参照模型一致 True
栈 出栈是入栈的反序 True
计数 01 栈 出栈 30
空栈 pop 报错类型 IndexError: pop from empty list
队列 与入队顺序相同 True
队列 出队与前 4 个 [1, 10, 19, 25]
随机 300 步 栈顶与模型一致 True
随机 300 步 队头与模型一致 True
随机 300 步 出栈顺序与模型一致 True
随机 300 步 出队顺序与模型一致 True
计数 02 栈 随机步数 150
计数 03 队列 随机步数 150

$ py task2_queue_cost.py
pop(0)  出队 200000 次 1.335131 秒
popleft 出队 200000 次 0.013567 秒
两种写法的出队顺序一致 True
两种写法取完的元素个数 200000 200000
deque 比列表快 98.4 倍
耗时 01 pop(0)  k=200000 1.335131 秒
耗时 02 popleft k=200000 0.013567 秒
倍数 03 deque 比列表快 0.01
计数 01 两种写法出队个数一致 True

$ py task3_brackets.py
用例 '()[]{}' True -1
用例 '([)]' False 2
用例 '(]' False 1
用例 '((' False 0
用例 '()' True -1
用例 '' True -1
用例 '([{}])' True -1
用例 ')))' False 0
用例 '(()' False 0
一组用例里配对正确的个数 4
校验 前六个用例逐字对照 True
校验 后三个用例逐字对照 True
计数 01 配对正确个数 4
计数 02 (() 的首个错位 0
计数 03 (]  的首个错位 1

$ py task4_eval.py
后缀 34+2* 14
后缀 12+ 3
后缀 93/ 3
后缀 56+7* 77
后缀 52-3+ 6
后缀 五组全部对上 True
后缀 减法与除法没有写反 True
切分 (12+3)*4 ['(', 12, '+', 3, ')', '*', 4]
切分 7 [7]
中缀 12+3 15
中缀 (1+2)*3 9
中缀 12*3+4 40
中缀 9-3+2 8
中缀 9-3-2 4
中缀 4*5-6/3 18
中缀 六组全部对上 True
中缀 同优先级从左往右 True
计数 01 后缀 全部对上 True
计数 02 中缀 全部对上 True
计数 03 两种都算对 True

$ py task5_window_max.py
课件数据 k=3 单调队列 [3, 3, 5, 5, 6, 7]
课件数据 k=3 暴力 [3, 3, 5, 5, 6, 7]
课件数据 与暴力一致 True
过期检查 k=3 单调队列 [7, 1, 1]
过期检查 k=3 漏检查版 [7, 7, 7]
过期检查 k=3 暴力 [7, 1, 1]
漏检查版与暴力不同 True
排列 20 个数 与暴力一致 True
排列 20 个数 窗口个数 17
排列 20 个数 k=1 True
排列 20 个数 k=20 [19]
随机 2000 个数 k=37 与暴力一致 True
计数 01 课件数据一致 True
计数 02 漏检查版不同 True
计数 03 窗口 2000 个数一致 True
耗时 01 单调队列 k=100 0.003957 秒
耗时 02 暴力     k=100 0.043104 秒
耗时 01 单调队列 k=500 0.003581 秒
耗时 02 暴力     k=500 0.213821 秒
耗时 01 单调队列 k=1000 0.003923 秒
耗时 02 暴力     k=1000 0.422147 秒
耗时 01 单调队列 k=2000 0.003656 秒
耗时 02 暴力     k=2000 0.771027 秒
四个 k 上答案都与暴力一致 True
同一规模上两个版本的答案个数 [19901, 19501, 19001, 18001]
倍数 01 k=100  暴力比单调队列慢 10.89
倍数 02 k=2000 暴力比单调队列慢 210.91
计数 04 四个 k 答案一致 True
```

任务 2 的 `倍数 03` 打出的是 `deque 的秒数 ÷ 列表的秒数`（本机 0.01，比 1 小）——
**判分对这一行的期望就是「小于 1」**，因为两条计时各自量各的、deque 那条本来就快。
真正好看的倍数是上面那行 `deque 比列表快 98.4 倍`，它才是判分要核对「≥ 20 倍」的那一行。
任务 5 的 `倍数 01` 与 `倍数 02` 反过来，是 `暴力 ÷ 单调队列`，越大越好。
秒数每次都变，判分只看趋势；列表里的答案、窗口个数、四个 k 的答案个数都是确定值，逐项核对。

留白版原样跑是不通过的（本机实测 5 个任务 0 个通过、退出码 1）：
栈与队列的 `pop` / `dequeue` 交回 `None`、两个出队循环一行都不跑（耗时 `0.000000`）、
`is_valid` 恒 `False`、`eval_rpn` 恒 `0`、`max_window` 与 `bad_window` 都交回空表——
那是起点，不是 bug。留白版里 `倍数 01/02` 那两条仍会 PASS：它们是拿「答对的那两行」当依赖才成立的，
判分对此另加了依赖检查，被依赖的行不对时它也不给 PASS。

`solutions/0010-stack-and-queue/` 里连 `tools.py` 与 `run_tests.py` 都有一份：
任务之间**不互相 import**（只 import 给好的 `tools`），所以拷一个也能跑，五个一起拷最省事；
`py run_tests.py` 应当五个任务全过（本机实测十几秒，其中 `pop(0)` 那 20 万次自己占一秒多）。

## 任务表 · 0011（`0011-two-pointers-applications/`）

这一课只有一个动作：**两个下标怎么配合着走**。五个任务各是一种配合方式——对撞（两数之和、
回文判定）、快慢（原地去重）、从后往前（原地合并），中间夹一个「`if` 与 `while` 差一处
关键字」的对照。

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 两数之和的对撞指针 | `task1_two_sum_sorted.py` | 写 `two_sum_brute`（两层循环的基准）与 `two_sum_sorted`（对撞版），再数出四档规模各走几轮 | 和偏小就 `l += 1`、偏大就 `r -= 1`，**每轮只动一个下标**；循环条件是 `l < r` 不是 `l <= r`（相等时区间里只剩一个下标，凑不出两个位置）；三条规则靠「数组有序」才成立。轮数那四个 0 要换成 `n - 1` 的四个值 | 课件三组 `(0, 3) / (2, 5) / None` 与暴力对照一致；四组边界（空、单元素、`[3, 3]`、负数）对撞与暴力一致；四档规模（20/200/2000/8000）答案都是 `(n-2, n-1)` 且四行 `一致 True`；`每档的轮数` 是 `[19, 199, 1999, 7999]`、`轮数与 n-1 相同 True`；`计数 01/02/03/04` 四行都是 `True` |
| 2 · `if` 与 `while` 差一处关键字 | `task2_if_vs_while.py` | 写 `two_sum_if`（**故意漏解**的那一版，右指针每轮只收一格）与 `two_sum_while`（一直收到不再偏大） | `if` 版漏解的原因：和偏大时只收一格，而下一轮 `for` 已经把 `l` 交给了下一个值——「同一个 `l`、更小的 `r`」那些组合再没人检查。`while` 版内层条件里的 `l < r` 不能省（它保证 `r` 不收到 `l` 左边去）。**两版别写成一模一样** | 课件数据上 `if` 版 `None`、`while` 版 `(0, 3)`、两版不同 `True`；逐轮状态 `[(0, 4, 12), (1, 3, 13), (2, 2, None)]`；五组 `数据` 行的 `while对` 全 `True` 且 `while` 交回的对**合法**；`if 版漏解组数` 是 **1**、`while 版与暴力一致组数` 是 5 |
| 3 · 原地去重（快慢指针） | `task3_dedup_inplace.py` | 写正确版（先 `slow += 1` 再写）与**只删掉那一行**的错版 | `a[:slow]` 是已经去重好的那一段（这就是不变式）；`len(a) == 0` 要先返回 0，不然 `a[0]` 报错；错版要**整段照抄正确版**、只删那一行，否则「两个错互相解释」这个现象就看不到了 | 课件数据个数 4、前 k 项 `[1, 2, 3, 5]`、整个数组 `[1, 2, 3, 5, 3, 5]`；错版个数 **1**、整个数组 `[5, 1, 2, 3, 3, 5]`；三组边界（空 / 单个 / 全相同）都交回 1 或 0；三组数据「个数 + 前 k 项」全对；20000 个数去重后 6667 与参照一致、前后两项 `[5, 8] [20096, 20101]`；探针另起进程查 `(k, a[:k])` 两段 |
| 4 · 回文判定与第一处错位 | `task4_palindrome.py` | 写 `is_palindrome` 与 `first_mismatch`：**同一趟走法**，只差「不相等时交出什么」 | 相等时**两个指针都要动**（只动一个会原地打转）；`first_mismatch` 回文时给 `-1`、否则给那一对下标。十组用例里 `'abca'` 是关键对照：首尾都是 `a`、相等，收一格之后才在 `b` 与 `c` 上分开，所以是 `(1, 2)` **不是** `(0, 3)` | 十组用例（字符串与列表、含空序列与单元素）的判定与第一处错位全对、`十组用例的判定对上` 是 10、两版判定完全一致 `True`；三行 `第一处错位` 分别是 `(0, 5)` / `(0, 3)` / `(1, 2)`；`计数 01/02/03/04` 全对 |
| 5 · 合并两个有序数组 | `task5_merge_sorted.py` | 写新列表版、原地版（从后往前写）、取前 k 项版 | 新列表版**两个收尾 `while` 都要写**（漏一个会丢尾巴）；原地版 `p = m - 1`、`q = len(b) - 1`、`w = 末尾`，循环条件是 **`while q >= 0`**——`b` 用完就结束，`a` 里剩下的本来就在正确位置上；取前 k 项取满就交回、`k` 大于总长时把能给的都给出来 | 两组课件数据合并对且原数组没动；六组数据（含空、一边为空、全同值）与 `sorted(a + b)` 一致、`六组与基准一致` 是 6；原地四组 `[1, 2, 4, 5, 6, 7]` / `[0, 1, 2, 3, 4]` / `[1, 2, 3, 4, 5, 6, 7]` / `[1, 2, 2, 3, 3]` 全对；前 3 项 `[1, 2, 3]`、前 10 项 `[1, 2, 3, 4, 5, 8, 9, 11]`；探针另起进程查三个函数 |

### 0011 的期望输出形状

判分读两种固定格式行（`计数 NN <标签> <值>`、以及一批带标签的 `print` 行），
**编号、标签与顺序都是判分接口**：

```text
$ py task1_two_sum_sorted.py
课件数据 目标 10 (0, 3)
课件数据 目标 20 (2, 5)
课件数据 目标 100 None
课件数据 暴力对照 [(0, 3), (2, 5), None]
课件数据 三组一致 True
边界 [] 5 None None
边界 [7] 14 None None
边界 [3, 3] 6 (0, 1) (0, 1)
边界 [-5, -1, 0, 2] -6 (0, 1) (0, 1)
边界四组 对撞与暴力一致 True
规模  20 对撞 (18, 19) 暴力 (18, 19) 一致 True
耗时 02 对撞 n=20 0.000002 秒
规模  200 对撞 (198, 199) 暴力 (198, 199) 一致 True
耗时 02 对撞 n=200 0.000013 秒
规模  2000 对撞 (1998, 1999) 暴力 (1998, 1999) 一致 True
耗时 02 对撞 n=2000 0.000083 秒
规模  8000 对撞 (7998, 7999) 暴力 (7998, 7999) 一致 True
耗时 02 对撞 n=8000 0.000329 秒
四组规模 对撞与暴力全一致 True
每档的轮数 [19, 199, 1999, 7999]
轮数与 n-1 相同 True
计数 01 课件三组一致 True
计数 02 边界四组一致 True
计数 03 四组规模一致 True
计数 04 轮数正确 True

$ py task2_if_vs_while.py
课件数据 if 版 None
课件数据 while 版 (0, 3)
课件数据 两版不同 True
if 版逐轮状态 [(0, 4, 12), (1, 3, 13), (2, 2, None)]
if 版第 1 轮之后 r 已经收到 3
if 版把 (0, 3) 那一对跳过了 True
数据 [1, 4, 5, 9, 11] 10 if None while (0, 3) while对 True
数据 [2, 3, 4] 6 if (0, 2) while (0, 2) while对 True
数据 [1, 2, 3, 4, 5] 9 if (3, 4) while (3, 4) while对 True
数据 [1, 1, 2] 3 if (0, 2) while (0, 2) while对 True
数据 [5, 6, 7, 8] 13 if (0, 3) while (0, 3) while对 True
if 版漏解组数 1
while 版与暴力一致组数 5
计数 01 两版不同 True
计数 02 if 版漏解组数 1
计数 03 while 版一致组数 5

$ py task3_dedup_inplace.py
课件数据 个数 4
课件数据 前 k 项 [1, 2, 3, 5]
课件数据 整个数组 [1, 2, 3, 5, 3, 5]
错版 个数 1
错版 整个数组 [5, 1, 2, 3, 3, 5]
边界 [] 个数 0 前 k 项 []
边界 [7] 个数 1 前 k 项 [7]
边界 [4, 4, 4, 4] 个数 1 前 k 项 [4]
空数组交回 0 True
单个元素交回 1 True
全部相同交回 1 True
数据 [1, 1, 2, 3, 3, 5] 个数 4 前 k 项 [1, 2, 3, 5] 对 True
数据 [1, 2, 3, 4] 个数 4 前 k 项 [1, 2, 3, 4] 对 True
数据 [2, 2, 2, 2, 3, 3, 5, 5, 5, 9] 个数 4 前 k 项 [2, 3, 5, 9] 对 True
三组数据全部正确 True
20000 个数 去重后个数 6667 参照个数 6667
20000 个数 前后两项 [5, 8] [20096, 20101]
计数 01 课件数据个数 4
计数 02 课件数据前 k 项 True
计数 03 错版个数 1
计数 04 三组数据正确个数 3
计数 05 20000 个数个数一致 True

$ py task4_palindrome.py
用例 '上海自来水来自海上' True -1
用例 'abccba' True -1
用例 'abcabc' False (0, 5)
用例 [1, 2, 3, 2, 1] True -1
用例 [1, 2, 2, 1] True -1
用例 [] True -1
用例 [9] True -1
用例 'a' True -1
用例 'ab' False (0, 1)
用例 [1, 2] False (0, 1)
十组用例的判定对上 10
两版判定完全一致 True
第一处错位 abcabc (0, 5)
第一处错位 [1, 2, 2, 3] (0, 3)
第一处错位 abca (1, 2)
计数 01 判定对上组数 10
计数 02 两版一致 True
计数 03 abcabc 错位 True
计数 04 列表 [1,2,2,3] 错位 True

$ py task5_merge_sorted.py
第一组 合并 [1, 2, 3, 4, 5, 6, 7]
第一组 原数组没动 [1, 3, 5, 7] [2, 4, 6]
第二组 合并 [1, 2, 2, 2, 3, 9]
第二组 原数组没动 [1, 2, 3] [2, 2, 9]
数据 [1, 3, 5, 7] [2, 4, 6] 合并 [1, 2, 3, 4, 5, 6, 7] 与 sorted 一致 True
数据 [1, 2, 3] [2, 2, 9] 合并 [1, 2, 2, 2, 3, 9] 与 sorted 一致 True
数据 [] [1, 2] 合并 [1, 2] 与 sorted 一致 True
数据 [1, 2] [] 合并 [1, 2] 与 sorted 一致 True
数据 [] [] 合并 [] 与 sorted 一致 True
数据 [5, 5] [5] 合并 [5, 5, 5] 与 sorted 一致 True
六组与基准一致 6
原地 合并 [1, 2, 4, 5, 6, 7]
原地 b 更短 [0, 1, 2, 3, 4]
原地 b 更长 [1, 2, 3, 4, 5, 6, 7]
原地 有重复值 [1, 2, 2, 3, 3]
前 3 项 [1, 2, 3]
前 10 项 [1, 2, 3, 4, 5, 8, 9, 11]
计数 01 六组与基准一致 6
计数 02 原地第一组 True
计数 03 原地 b 更长 True
计数 04 前 3 项 True
```

**这一套判分一条耗时判据都没有。** 上面那四行 `耗时 02 对撞 n=… 秒` 是给学生自己看的，
秒数每次都变；判分读的全是确定值（答案、轮数、个数、逐字对照的布尔值）。
所以参考解连跑多次结果**完全一致**——这不是运气，是契约里本来就没有浮动量。

**「两数之和」只判交回的那一对合不合法，不写死是哪一对。** `[0, 0, 0]` 目标和 0 时
`(0, 1)`、`(0, 2)`、`(1, 2)` 都对：对撞版从两端出发先命中 `(0, 2)`，两层循环从左往右
先命中 `(0, 1)`，**两个都对**。判分只检查「交回的对满足 `i < j` 且 `a[i] + a[j] == target`，
无解时交回 `None`」。（这是本轮修的一处真 bug：原判分器写死了期望下标，而写死的值里
`[2, 3, 4]` 目标和 6 记成 `(1, 2)`——那是 3+4=7，算错了。）

**`if 版漏解组数` 的期望是 1，不是 3。** 五组数据里只有 `[1, 4, 5, 9, 11] / 10` 这一组
`if` 版交回 `None` 而 `while` 版找到了答案；其余四组第一次比较就命中，或者和一直偏小、
`r` 根本不用动。这个判据的意思不是「`if` 版处处都错」，而是**它错在一个特定的输入形状上**
——这正是这类 bug 危险的地方。

留白版原样跑是不通过的（本机实测 5 个任务 13 PASS / **58 FAIL**、退出码 1，
**58 条 FAIL 每条都点名要改的 TODO**）：
`two_sum_brute` / `two_sum_sorted` 交回 `None`、四档轮数还是 `[0, 0, 0, 0]`、
`two_sum_if` / `two_sum_while` 都交回 `None`（于是「两版不同」也成了 `False`）、
去重两版都交回 0、回文判定恒 `False` 且错位恒 `-1`、合并三版都交回空表——
那是起点，不是 bug。

`solutions/0011-two-pointers-applications/` 里连 `tools.py`、`run_tests.py` 与 `probes/`
都有一份（**与任务目录逐字节相同**）：任务之间不互相 import（只 import 给好的 `tools`），
所以拷一个也能跑（没拷到的任务会被报成「还没建这个文件」），五个一起拷最省事；
`py run_tests.py` 应当五个任务全过（本机实测 **71 PASS / 0 FAIL**、退出码 0，十几秒）。

**`probes/` 是个子目录，必须一起拷。** 只拷 `*.py` 会漏掉它，那时判分会报
`任务 N 的探针跑不起来：没找到探针文件 probes/probe_taskN.py`——**一份完全正确的参考解
在这种拷法下也会显示 3 条 FAIL**（只剩 64 PASS）。这三条说的不是你的代码有问题，
是探针没到位，所以它们**不带** TODO 提示。整个目录一起拷就不会遇到。

## 任务表 · 实验二（`0015-lab-02-verify-by-brute-force/`）

这一课交的是**一份对拍器**：随机造数据、拿参照解与候选解各跑一遍、不一致就报告、
再把抓到的那组数据缩到最小，最后把结论写进 `findings.md`。
四个部件缺一件都转不起来：参照解（`brute_find`）、候选解（`buggy.py` 里给好的 `cand_find`）、
数据生成器（`gen_wide` / `gen_boundary`）、比对循环（`stress`），外加一个 `shrink`。

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 参照解：慢但一定对 | `stress.py` 的 `brute_find(a, x)` | 在 `a` 里从头线性扫一遍，交回**第一处**等于 `x` 的下标；没有就 `-1` | 一个 `for` 加一个 `if` 就够，别写二分——参照解的价值在于**一眼看得出对不对**；`a` 是空表时 `range(len(a))` 一次都不跑，自动落到 `return -1`，不用特判 | 八组已知数据全对：空数组与「目标不存在」都交回 `-1`、重复值 `[5, 5, 5]` 交回第一处的 `0`、答案在右端的 `[4, 9]` x=9 交回 `1`；另查 `stress.py` 里有没有 `import random` |
| 2 · 两个造数据器 | `gen_wide()` / `gen_boundary()` | 两个都不收参数、各交回 `(a, x)`；`gen_wide` 造宽范围随机数据，`gen_boundary` 造**边界形态** | `a` 必须**升序**（候选解是二分，乱序的数据报出来的东西不算证据）；`gen_boundary` 四种形态各占一部分、用 `random.randrange(4)` 选一支：空数组 / 单元素且 x 就是它 / 全相同 / 答案恰好在两端。**只写 `gen_wide` 抓不到 bug**——`gen_wide` 的 `x` 大多不在数组里，两边都交回 `-1` | `gen_wide` 连造 40 组都是升序、形状合法；`gen_boundary` 连造 40 组的形态分布里四种都在；两个「只在某种形态上出错」的假候选（空数组上崩、单元素/重复值上错）都必须被抓到 |
| 3 · 比对循环 | `stress(candidate, reference, gen, trials, seed=None)` | 跑 `trials` 次：每次 `a, x = gen()`，用 `tools.as_lists(...)` 拿两边答案；不一样就交回 `(第几次, a, x, 候选答案, 参照答案)`，全一样交回 `None` | `random.seed(seed)` 要在**循环外面**设一次、而且只在 `seed` 不是 `None` 时设；两个答案不一样才报告（写反了只会在一致时报）；交回的五样里候选与参照别调位置。返回值是**故意**设计成带上那组数据的——只回一句「有问题」复现不了 | 拿同一个函数同时当候选与参照跑 2000 次，一次都不许抓到（交回 `None`）；再把候选换成「答案永远是 0」的函数，必须**立刻**抓到；对拍 `buggy.py` 必须抓到，而且同一个 seed 连着跑两次抓到的是**同一组** |
| 4 · 反例最小化 | `shrink(candidate, reference, a, x)` | 反复试：删掉 `cur` 里第 `i` 个元素得到 `smaller`，两边跑一遍，**只要还不一致**就 `cur = smaller` 并从头再试；一个都删不掉了就交回 `cur` | 从 `cur = list(a)` 开始（别改调用处那张表）；接受更小的版本**之前必须再比一次**，少了这一次会缩到两边一致、最小反例复现不了原来的错；交回的是**一张表**，不是 `(a, x)` 两个——`x` 从头到尾不变 | 交回的是整数表、而且仍然让两边不一致；再删一个元素就抓不到这个 bug 了（**缩到底**）；给它 `[10, 20, 63, 97]` x=97（前两个元素对暴露 bug 毫无贡献）必须真的缩；把候选换成「答案永远错」的函数也照样缩 |
| 5 · 把结论写进 `findings.md` | `findings.md` | 把三样东西填上（原始反例、最小反例、出错的行号），再把 `TBD` 记号从每一行删掉，末尾写一句「是哪个数据形态暴露的」 | 三样都照 `py stress.py` 打出来的那几行**抄**，别手写；行号用 `buggy.py` 里那一行 `while lo < hi`（从 1 数起） | 判分自己跑一遍 `shrink` 与你的对照、必须一致；最小反例再删一个元素就缩不动；原始反例拿去跑两边必须真的不一致；行号必须是 `buggy.py` 第 23 行；`findings.md` 里不许留着 `TBD` |

### 实验二的期望输出形状

`py stress.py` 打完五个任务的全部行；判分读的是其中这些（标签与顺序都是判分接口）：

```text
$ py stress.py
对拍器 0015 · 候选解 buggy.cand_find，参照解 brute_find

第 1 步 · 参照解的三组手算数据
  参照解 a=[] x=3 → -1（期望 -1）
  参照解 a=[5] x=5 → 0（期望 0）
  参照解 a=[63, 97] x=97 → 1（期望 1）

第 2 步 · 造数据器各来三组看一眼
  gen_wide [([...], 41), ...]        （每组是 (a, x)，a 升序）
  gen_boundary [([], 137), ...]      （空数组 / 单元素 / 全相同 / 答案在两端）

第 3 步 · 同一个函数当候选与参照（这一条必须是 None）
  还没抓到：stress 交回 None（要么真的一次都没抓到，要么它还没在比对）

第 4 步 · 对拍 buggy.py
  第 560 次抓到：a=[0, 0, 0, 0, 0] x=0 候选=-1 参照=0
  计数 01 种子 20261115 抓到 560
  计数 02 同一种子再跑一次 抓到 560

第 5 步 · 反例最小化
  原始反例: [0, 0, 0, 0, 0] x = 0  候选 -1  参照 0
  最小化后: [0, 0, 0] x = 0  候选 -1  参照 0
  计数 03 最小反例长度 3

findings.md 这样写（三样东西，缺一样第 4 层就不过）：
  原始反例: a = [0, 0, 0, 0, 0], x = 0
  最小反例: a = [0, 0, 0], x = 0
  出错的行: buggy.py 第 23 行  'while lo < hi:'
```

上面这几行的**数字**（第几次抓到、原始反例是哪一组）要看你的 `gen_boundary` 怎么写——
同一个种子、同一份生成器每次跑出来都一样，判分接受的正是「你自己的生成器给出的那一组」，
它只核对两件事：同一个 seed 两次抓到的是不是同一组，以及 `findings.md` 里抄的是不是那一组。
`最小化后` 那一行则不是随意的：`shrink` 要一直缩到删不动为止。

`buggy.py` 是**给好的候选解，别改、别删**：它跑起来一行报错都没有、样例上也过得去，
但闭区间 `[lo, hi]` 配 `while lo < hi`，区间只剩一格时循环已经退出，那一格从没被检查过。
把 bug 顺手修了，判分第 3 层就没东西可抓了。`tools.py` 同理是给好的公共工具
（两种「没找到」的写法归成同一个数、固定格式的打印行、读 `buggy.py` 的源码行）。

判分分四层，一层里几条检查各自给 PASS / FAIL：

```text
第 1 层 · 参照解对不对（八组已知数据）
第 2 层 · stress 没自己骗自己（同一函数当两边 2000 次；候选恒错必须被抓到）
第 3 层 · 抓得住，而且抓得可复现（两个生成器的形状与升序；两种边界形态；buggy.py；同种子两次）
第 4 层 · 缩到最小，记录对得上（shrink 的形状 / 仍是反例 / 缩到底 / 两组专门造的输入；findings.md 三样）
```

第 1 层没过时后面三层**直接跳过**（参照解不准，它们的结论没有参考价值）。
留白版原样跑是不通过的（本机实测 0 层通过、8 条 FAIL、退出码 1）：五个函数全交回 `None`——
那是起点，不是 bug。

`solutions/0015-lab-02-verify-by-brute-force/` 里连 `tools.py`、`buggy.py` 与一份填好的
`findings.md` 都有一份：把 `stress.py` 拷进任务目录覆盖同名文件（`findings.md` 也能一并拷，
它就是参考解那一组反例的记录），`py run_tests.py` 应当四层全过（本机实测 17 条 PASS、0 条 FAIL、
几秒跑完）。参考解抓到的原始反例是 `[0, 0, 0, 0, 0]` x=0，最小反例是 `[0, 0, 0]`，形态是**全相同**。

## 任务表 · 0016（`0016-hash-table/`）

五个任务都是「同一件事写两遍」：列表版按定义做（慢），字典或集合版一边扫一边记（快）。
两版结果必须**逐字一致**，只交一版不算过。

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 统计出现次数 | `task1_count.py` | 补 `TODO 1`（列表版：先把出现过的值去重存进 `uniq`，再对每个元素把整批数据从头数到尾）、`TODO 2`（字典版：一遍扫，`cnt[x] = cnt.get(x, 0) + 1`），以及 `count_list(items)` / `count_dict(items)` 两个函数 | 这就是第 3 课那笔账：数据 `n` 个、不同元素 `k` 个时列表版比较 `n × k` 次、字典版只比较 `n` 次；`TODO 1` 那段在 `t0` / `t1` 之间，`TODO 2` 在 `t2` / `t3` 之间，别写串 | 两个「不同元素」都是 **500**（给好的数据是 `i % 500` 跑 20000 次）；两个「总次数」都是 **20000**；`两版结果逐字一致` 是 `True`；`Counter 与字典版一致` 是 `True`；`字典版比列表版快` ≥ 5 倍（本机实测 252 倍）；判分的探针在六组小数据上比对两个函数 |
| 2 · 第一个重复出现的元素 | `task2_first_repeat.py` | 补列表版与集合版两段，以及 `first_repeat_list(items)` / `first_repeat_set(items)` | `seen` 分别是列表与集合；**发现重复的那一刻立刻停下**并交出这个元素，不能扫完再回头找；没有重复交回 `None`；空集合只能写 `set()` | 两版都交出 **7**（给好的数据里前 2000 个互不相同，第 2001 个是前面出现过的 `7`）；`两版结果逐字一致` 是 `True`；`列表版比集合版慢` ≥ 3 倍（本机实测 49 倍）；探针在六组小数据上比对两个函数（含 `[]`、`[5, 5]`、`['a', 'b', 'a']`） |
| 3 · 两数之和 | `task3_two_sum.py` | 补列表版（两层循环）与字典版（一遍哈希），以及 `two_sum_list(nums, target)` / `two_sum_dict(nums, target)` | **先查后存**是这一题的重点：扫到 `x` 时先算 `need = target - x`、先查 `need` 在不在字典里，最后才把 `x` 与它的下标记进去。`[3, 3]`、target 6 的答案是 `(0, 1)` 而不是 `(0, 0)`——写成「先存后查」当前元素就配上了自己 | 大数据两版都是 `(19998, 19999)`、`两版结果逐字一致` 是 `True`、`字典版比列表版快` ≥ 20 倍（本机实测 4166 倍）；五组小数据逐组一致：`普通 (0, 1)`、`两个相同的数 (0, 1)`、`找不到 (-1, -1)`、`空表 (-1, -1)`、`只有一个元素 (-1, -1)`；探针专抓 `[3, 3]` 这一个边界 |
| 4 · 手工算一遍哈希值与桶号 | `task4_hash_buckets.py` | 补两轮「哈希值 → 桶号」的计算（8 个桶与 16 个桶）、两轮冲突统计、`bucket_of(key, buckets)` / `conflicts(keys, buckets)`，以及 `reason` 那一句解释 | 桶号 = `hash(键) % 桶数`；`键 … 哈希值 … 桶号 …` 那几行与 `桶数 N` 分段是判分接口，别改；`reason` 要写一两句「为什么哈希值跨进程不同」——判分看长度 ≥ 10 字，且不能还留着 `TODO` | 8 个桶与 16 个桶两轮各打出 7 行、桶号各自落在 `0..7` / `0..15` 且等于 `hash(k) % 桶数`；`装了不止一个键的桶数` 按你自己打出来的桶号数得对（本机 8 个桶是 3 个、16 个桶是 1 个）；`桶变多了 冲突没变多` 与 `同进程内哈希值稳定` 都是 `True`；判分**跑两遍**脚本，看两次的哈希值确实不同 |
| 5 · 什么能当键 | `task5_key_rules.py` | 补四段：`try` / `except` 接住「列表当键」的异常、元组当键的 `get`、浮点当键的两次 `get`、`hash_of(text)` | 异常类的名字用 `type(e).__name__`、信息用 `str(e)`，**别让报错把脚本带崩**；`price = {0.3: …}` 上 `0.1 + 0.2` 取不到（那是另一把键），`round(0.1 + 0.2, 10)` 才取得到；`hash_of` 直接交回 `hash(text)`——判分起**两个进程**分别调它，比对结果 | 列表当键的异常类型是 `TypeError`、报错话里带 `unhashable` 与 `list`，新版 Python 的措辞里还有 `cannot use 'list' as a dict key`；元组当键取到 `A`、不存在的键 `get` 交回 `None`；浮点两次取到 `None` / `零点三元`，`(0.1 + 0.2) != 0.3` 是 `True`；三行稳定性都是 `True`；`hash_of('abc')` 同一个进程内两次相同、**跨进程必须不同** |

### 0016 的期望输出形状

判分按行读这些 `print`（前缀与顺序都是判分接口）：

```text
$ py task1_count.py
列表版 不同元素 500 0.348083 秒
字典版 不同元素 500 0.001378 秒
列表版 总次数 20000
字典版 总次数 20000
两版结果逐字一致 True
字典版比列表版快 252.5 倍
Counter 与字典版一致 True

$ py task2_first_repeat.py
列表版 第一个重复 7 0.008614 秒
集合版 第一个重复 7 0.000176 秒
两版结果逐字一致 True
列表版比集合版慢 49.1 倍

$ py task3_two_sum.py
列表版 大数据 (19998, 19999) 14.279952 秒
字典版 大数据 (19998, 19999) 0.003428 秒
两版结果逐字一致 True
字典版比列表版快 4166.0 倍
小数据 普通 (0, 1) 列表版 (0, 1) 一致 True
小数据 两个相同的数 (0, 1) 列表版 (0, 1) 一致 True
小数据 找不到 (-1, -1) 列表版 (-1, -1) 一致 True
小数据 空表 (-1, -1) 列表版 (-1, -1) 一致 True
小数据 只有一个元素 (-1, -1) 列表版 (-1, -1) 一致 True

$ py task4_hash_buckets.py            （这一份要自己跑两遍，哈希值每次都不一样）
桶数 8
键 apple 哈希值 3017888152601399529 桶号 1
键 banana 哈希值 6696966239679042685 桶号 5
键 cherry 哈希值 7864709498573724508 桶号 4
键 date 哈希值 1298427985472212536 桶号 0
键 fig 哈希值 3066357270181475061 桶号 5
键 grape 哈希值 -4627702387344484087 桶号 1
键 kiwi 哈希值 7514615438082555316 桶号 4
8 个桶 装了不止一个键的桶数 3
8 个桶 桶里最多装了 2 个键
桶数 16
键 apple 哈希值 3017888152601399529 桶号 9
（…16 个桶那七行，形状同上…）
16 个桶 装了不止一个键的桶数 1
16 个桶 桶里最多装了 2 个键
桶变多了 冲突没变多 True
同进程内哈希值稳定 True
原因 字符串哈希带随机种子：进程启动时随机选一个种子，本机 sys.hash_info 显示 siphash13、seed_bits 128，所以同一个串在不同进程里算出的哈希值不同，同一个进程内不变。加种子是为了防人预先构造一大批落进同一个桶的键，把字典拖成最坏 O(n)。

$ py task5_key_rules.py
列表当键 异常类型 TypeError
列表当键 报错说 cannot use 'list' as a dict key (unhashable type: 'list')
列表当键 提到 dict key True
元组当键 取到 A
元组当键 键不存在时 get 交回 None
浮点当键 0.1+0.2 取到 None
浮点当键 先 round 再取到 零点三元
浮点当键 不相等 True
同进程内两次一致 True
相同内容不同对象也一致 True
相等则哈希相同 True
hash_of abc 5284459870646369912
```

任务 4 那两轮哈希值是本机某一次运行的**原样**——你跑出来的会是另一串数（字符串哈希跨进程带随机种子），
桶号也跟着换。判分所以**不跨进程比桶号**，只核对两件事：每一次运行内部「桶号 = 哈希值 % 桶数」成立，
以及两次运行的哈希值确实不同。**两次运行之间比哈希值一样的，反而是错的**（那是把哈希值写成了常量）。
桶号是随机的，`装了不止一个键的桶数` 也随进程变？——不会：那是按**你自己打出来的桶号**数的，
数法对了就通过；判分另外还拿十个键放进八个桶试你的 `conflicts`（抽屉原理，一定有桶装了 2 个以上）。
任务 5 里 `hash_of abc` 那一行同样是进程相关的随机数，判分只比对**两个进程之间不相同**、且**同一个进程内两次相同**。

秒数那一列每次都变（任务 3 的列表版十几秒是正常的：两层循环在 2 万个互不相同的数上找不到配对时要把
近两亿组比完），判分只看趋势；`500`、`20000`、`7`、`(19998, 19999)`、五组小数据的答案
都是确定值，逐项核对。

留白版原样跑是不通过的（本机实测 5 个任务 0 个通过、退出码 1）：两个计数版都交出空字典、
`first_repeat_*` 交回 `None`、`two_sum_*` 交回 `(-1, -1)`、哈希值全是占位的 `0`、`hash_of` 交回 `0`——
那是起点，不是 bug。

`solutions/0016-hash-table/` 里连 `run_tests.py` 都有一份：把那里的五个 `.py` 拷进任务目录
覆盖同名文件，`py run_tests.py` 应当五个任务全过（本机实测十几秒，其中任务 3 的列表版自己占十几秒——
那正是这一课要你看的差距）。

## 任务表 · 0017（`0017-binary-tree-traversal/`）

这一课的结构表示约定是**嵌套列表**：空树写 `None`，一个结点写 `[值, 左子树, 右子树]`，
由 `tools.py` 给好的 `node(v, l, r)` 搭出来。四个任务都是「用两个孩子交回的答案算出自己的答案」。

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 四种遍历 | `task1_traversal.py` | 补 `preorder` / `inorder` / `postorder`（三个递归版，签名都是 `(t, out=None)`）与 `level_order(t)`（队列版），再照示例树的样子搭两棵树 `CHAIN5`（一直往左五层，值 1..5）与 `BAL5`（四层挂满 15 个结点） | 第一句永远是基例 `if t is None: return out`——漏了它走到叶子那个不存在的孩子时会报 `TypeError: 'NoneType' object is not subscriptable`；三个递归版**只差 `out.append(t[0])` 那一句的位置**（前序最前、中序夹中间、后序最后）；层序用 `deque` 的 `append` / `popleft`，队列里存的是**子树**不是值，入队前比较写 `x[1] is not None`（写 `if x[1]` 会把值为 `0` 的结点悄悄丢掉） | 示例树的四行与课件逐字一致（前序 `A B D E C F`、中序 `D B E A C F`、后序 `D E B F C A`、层序 `A B C D E F`）；链状树四行、平衡树四行都要对；`空树 四种` 是 `[] [] [] []`、`单点 四种` 是四份 `['A']`；`计数 01/02/03` 是 `6 / 5 / 15` |
| 2 · 汇总子树信息：节点数、树高、对称性 | `task2_tree_stats.py` | 补 `count(t)`、`height(t)`、`is_mirror(a, b)`、`is_symmetric(t)` | 四个都是「两个孩子交回答案、在根上合并」：`1 + count(左) + count(右)`、`1 + max(height(左), height(右))`（口径是**层数**：单点树高 1、空树 0）。`is_mirror` 的四个分支一个都不能少（都空 `True`、只有一个空 `False`、都非空才往下走），最后两个递归的参数是**左对右、右对左**（`a[1]` 配 `b[2]`）——写成左对左判的就是「两棵子树一模一样」 | 那张表的五行：空树 `0 0 True`、单点 `1 1 True`、对称树 `5 3 True`、示例树 `6 3 False`、只差一个值 `5 3 False`；`镜像对 是不是镜像` 是 `False`（形状相同的两棵树不是互为镜像）、`镜像树 自己是自己的镜像` 是 `True`、`示例树 两棵子树是不是镜像` 是 `False` |
| 3 · 形状与递归深度 | `task3_depth_shape.py` | 补 `build_balanced(n)`（照课件 `left = k // 2` 那一版）、`build_chain(n)`（每个结点只有左孩子）、`height(t)`、`max_safe_depth()` | `height` **不许改成显式栈的迭代版**：这一份量的就是递归深度，改成迭代就量不到了；也别在 `height` 里 `try` / `except RecursionError` 接住它（判分靠它判断爆栈发生在哪一层）。`max_safe_depth` 从 `limit - 5` 往上试到第一条爆栈的链、**不准改递归上限**，交回的是「**跑得动**的最大值」而不是 `sys.getrecursionlimit()` | 平衡树三种规模（100 / 1000 / 10000）的树高是 `7 / 10 / 14`；链状树三种规模**全是爆栈**（连 100 层那行都要先跑得动）；`链状 爆栈长度` 是 `999`（`计数 02` 那行会带上「已爆栈」几个字）；`递归再深一层` 落在 **995-998**（参考解 997）、与 `注释 递归上限`（1000）只差 1-6 层 |
| 4 · 拼接与累加器的代价 | `task4_concat_cost.py` | 补 `preorder_concat(t)`（**拼接版**：`[t[0]] + 递归 + 递归`）、`preorder_acc(t, out=None)`（累加器版）、`build_chain` / `build_balanced`（与任务 3 同一版）、`best_of(func, t, repeats)` | `preorder_concat` 就是要写出课件那个形状，**别偷偷改成累加器**（拼接版是要看的对象，不是要改的错）；`best_of` 要每次单独计时取最小，别把 `repeats` 次塞进一次计时 | 两版答案处处一致（链状 200、空树、单点都对，`计数 01` 是 `True`）；链状 200→400→800 上**拼接涨 8 倍以上**（平方级）、累加器涨 8 倍以内（线性该是 4 倍上下）；链状 2000 上拼接比累加器慢（倍数 > 1），而且**链状的倍数明显大于平衡树的倍数** |

### 0017 的期望输出形状

判分读四种格式：带标签的 `print` 行、`计数 NN <标签> <值>`、`耗时 NN <标签> n=… <秒数> 秒`、
以及 `show_label` 打出来的 `<标签> <值>`。任务 1、3 的行是本机参考解的原样值：

```text
$ py task1_traversal.py
示例树 前序 ['A', 'B', 'D', 'E', 'C', 'F']
示例树 中序 ['D', 'B', 'E', 'A', 'C', 'F']
示例树 后序 ['D', 'E', 'B', 'F', 'C', 'A']
示例树 层序 ['A', 'B', 'C', 'D', 'E', 'F']
计数 01 示例树 前序 6
（空行）

链状树 前序 [1, 2, 3, 4, 5]
链状树 中序 [5, 4, 3, 2, 1]
链状树 后序 [5, 4, 3, 2, 1]
链状树 层序 [1, 2, 3, 4, 5]
计数 02 链状树 前序 5
（空行）

平衡树 前序 [1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15]
平衡树 中序 [8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15]
平衡树 后序 [8, 9, 4, 10, 11, 5, 2, 12, 13, 6, 14, 15, 7, 3, 1]
平衡树 层序 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
计数 03 平衡树 前序 15
（空行）

课件 前序 ['A', 'B', 'D', 'E', 'C', 'F']
课件 中序 ['D', 'B', 'E', 'A', 'C', 'F']
课件 后序 ['D', 'E', 'B', 'F', 'C', 'A']
课件 层序 ['A', 'B', 'C', 'D', 'E', 'F']
空树 四种 [] [] [] []
单点 四种 ['A'] ['A'] ['A'] ['A']

$ py task2_tree_stats.py
数据 节点数 树高 对称
空树 0 0 True
单点 1 1 True
对称树 5 3 True
示例树 6 3 False
只差一个值 5 3 False

镜像对 是不是镜像 False
镜像树 自己是自己的镜像 True
示例树 两棵子树是不是镜像 False

$ py task3_depth_shape.py
形状 规模 树高 这一层的递归
平衡 n=  100 树高      7 跑得动
树高行 平衡 n=100 7 跑得动
平衡 n= 1000 树高     10 跑得动
树高行 平衡 n=1000 10 跑得动
平衡 n=10000 树高     14 跑得动
树高行 平衡 n=10000 14 跑得动
链状 n=  100 树高    100 跑得动
树高行 链状 n=100 100 跑得动
链状 n= 1000 树高 爆栈
树高行 链状 n=1000 爆栈 爆栈
链状 n=10000 树高 爆栈
树高行 链状 n=10000 爆栈 爆栈
计数 01 平衡 n=10000 树高 14
计数 02 链状 爆栈长度 999 已爆栈
链状 爆栈长度 999
递归再深一层 997
注释 递归上限 1000
递归深度比上限小几层 True
固定开销的层数 3
计数 02 爆栈长度 999
计数 03 递归再深一层 997
```

`链状 爆栈长度` 与 `递归再深一层` 这两行**注定差得动一两层**：贴着上限试，差的就是一两个栈帧——
在函数里试比在主块顶层试要少一层（函数自己那一帧），所以参考解报 997、而主块里直接试能走到 998。
判分接受的是一小段（995-998），真正的判据是「它贴着上限、而且那个深度上 `height` 交回的树高**等于深度本身**」，
以及「它不大于爆栈长度减一」。别为了凑一个漂亮的数去改递归上限。

任务 4 的秒数每次跑都会浮动，判分只看趋势；形状对照那两行本机参考解是「链状 2000 慢 20 倍上下、
平衡 2000 慢 1.7 倍上下」，判分要求的是「链状的倍数明显更大」。
任务 4 最后那一段量的链有 2000 层、比默认上限还深，所以主块在那一段外面临时把上限调高、
`finally` 里还原——那一段要看的是拼接的复制量，不是撞递归上限（默认上限下那条线是任务 3 量的）。

留白版原样跑是不通过的（本机实测 4 个任务 17 PASS / 72 FAIL、退出码 1，没有 Traceback）：
四种遍历都交回 `[]`、表里全是 `0 0 False`、树高全是 0、四类耗时全是 `0.000000`——
那是起点，不是 bug，每条 FAIL 都点出了缺哪一段 TODO。

`solutions/0017-binary-tree-traversal/` 里连 `tools.py` 与 `run_tests.py` 都有一份：
四个任务都只 `import` 给好的 `tools`、**任务之间不互相 import**（任务 4 自己带 `build_chain` / `build_balanced`），
所以拷一个也能跑，四个一起拷最省事；`py run_tests.py` 应当四个任务全过
（本机实测几秒，其中任务 4 的计时自己占一秒多）。

## 任务表 · 0018（`0018-heap-and-priority-queue/`）

四个任务围绕同一件事：**堆只维护「最小那个在顶上」这一条信息**，所以它每一步都是对数时间。
前三个用标准库 `heapq`，第四个自己把上浮与下沉写一遍。

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 合并果子两种写法 | `task1_merge_fruit.py` | 补 `merge_list(a)`（每轮 `a.sort()` 一次、取 `a[0]` 与 `a[1]` 合并、追加后**再排一次**）、`merge_heap(a)`（`heapify` 一次，每轮弹两个压一个）、`merge_plan(a)`（把每轮合出的 `(x, y, x + y)` 记下来） | 列表版是**要留着的对照**（它算得对、只是每轮多排一次序），别偷偷改成堆版；堆版要**先复制一份再动它**（`h = list(a)` 再 `heapify`）——`heappop` / `heappush` 都是原地改列表，不复制的话第一次调用就把传进来的列表掏空了，后面几次量的都是「没干活」；循环条件写 `len(h) > 1`（写成 `while h` 会在空列表上 `heappop` 报 `IndexError`）；`a.sort()` 在列表版**每轮末尾**都要有，少一次答案就错 | 两版总和一致、且等于判分自己按「每轮取最轻的两堆」算出来的值（本机 n=1000 是 `4759764`）；`合并过程 轮数` 是 `999`（n 堆合并 n-1 轮）；`合并过程 前三轮` 每项都是三元组、第一轮挑的正是最小的两个；`合并过程 末轮总和` 那第三个数是**所有堆的重量之和**（不是总代价）；`merge_heap` 与 `merge_plan` 都**不能动传进来的列表**（`计数 04` 期望 `False`）；三档耗时（1000 / 2000 / 4000）都量到、列表版涨得比堆版多、最大一档上列表版明显更慢；`空列表` / `单堆` 都是 0、`两堆` 是 8 |
| 2 · 前 k 大不必排全序 | `task2_kth_largest.py` | 补 `kth_by_sort(a, k)`（基准版：降序排完取第 `k-1` 项）、`kth_by_minheap(a, k)`（大小为 k 的最小堆）、`topk_by_heap(a, k)`（交回降序的前 k 大）、`smaller_heap_better(ratios)` | 堆版先拿前 k 个建堆，再从第 k+1 个起比堆顶：比堆顶大就 `heapreplace(h, v)`（**一步**做完弹顶与压入，别写成 `heappop` 再 `heappush`）；`h[0]` 是堆里那 k 个中最小的，比它大的正好有 k-1 个，所以它就是**第 k 大**。`topk_by_heap` 最后要把堆里的东西**逐个 `heappop`** 出来再反向——堆只保证 `h[0]` 最小，**其余位置没有顺序**，不能拿 `h` 当排好序的列表交回 | 七个 k（1 / 2 / 3 / 10 / 10 万 / 199999 / 20 万）上排序版与堆版都是同一个值、且等于判分自己排序取出来的那个；`前10大 两版一致`（排序取前 10 与 `heapq.nlargest(10, …)` 恒等）与「自己写的堆前 10 大与 `nlargest` 一致」都是 `True`、前三个也对得上；k=10 / 10 万 / 199999 三档耗时都量到；`k 小的时候堆更划算` 是 `True`（k=10 的倍数 > 1，而且不小于 k=199999 的倍数——判分留了 25% 的计时噪声带） |
| 3 · 数据流中位数 | `task3_running_median.py` | 补 `running_median(stream)`（交回**与数据流等长**的中位数序列）与 `median_state(stream)`（每一步之后的 `(len(lo), -lo[0], len(hi), hi[0] if hi else None)`） | 对顶堆三步一步都不能少、**顺序也不能换**：先 `heappush(lo, -v)`（负数存成最大堆）、再把 `lo` 顶挪到 `hi`、`hi` 比 `lo` 长就挪回来；维持的是两条不变式——`lo` 里每个数都不大于 `hi` 里每个数、两个堆长度差不超过一；取值时 `hi` 可能是空的，不能直接写 `hi[0]` | `中位数 个数` 是 11、`中位数 是每一步的序列` 是 `True`；每一步那行都要打出来（`第 N 步 lo长度 lo顶 hi长度 hi顶 中位数`）；`计数 01 不变式 长度差不超过一` 与 `计数 02 不变式 lo 顶不大于 hi 顶` 都是 `True`；边界：`空流` 是 `[]`、`一个数` 是 `[7]`、`两个数` 是 `[4, 6.5]`、`第一个数的状态` 是 `[(1, 7, 0, None)]` |
| 4 · 手写一个最小堆 | `task4_min_heap.py` | 补 `MinHeap` 的 `push(v)`（追加到末尾再上浮）、`pop()`（弹出并交回 `a[0]`）、`_up(i)`（与父结点比）、`_down(i)`（与**较小的那个孩子**比） | `pop` 那三步**顺序最容易写反**：先记下根（答案）、再把末尾元素取出来、然后把它放到根上往下沉——先删根再取末尾，下标就乱了；`_up` 的循环条件是 `i > 0`（根没有父结点；漏了它会去取 `a[-1]`，堆被悄悄弄坏还不一定报错）；`_down` 两处 `l < n` / `r < n` 一个都不能少，而且要先与左孩子比、再与右孩子比，`m` 记住的才是**较小的那个** | `手写堆弹出序列与 heapq 一致` 与 `与原数组排序一致` 都是 `True`、前 8 个弹出也对；`每推一个数之后` / `每弹一个数之后` 堆序性质都成立；`计数 01`（推完 50 个数之后元素个数）是 `50`；随机穿插 push/pop 之后弹出值都对；`单元素弹出` 是 `5 剩下 0`、空堆弹出报 `IndexError`；耗时那一行手写堆比 `heapq` 慢几倍（本机 4.25 倍）——判分只看趋势 |

### 0018 的期望输出形状

判分读 `计数 NN <标签> <值>`、`耗时 NN <标签> n=… <秒数> 秒` 与 `show_label` 的 `<标签> <值>`，
再另起探针进程 import 你的函数拿判分自己造的数据试。下面是本机参考解的原样输出（秒数是某一次的值）：

```text
$ py task1_merge_fruit.py
n=1000 列表版总和 4759764
n=1000 堆版总和 4759764
两版答案一致 True
合并果子 两版答案一致 True
计数 01 合并果子 堆版总和 4759764
合并过程 轮数 999 合并 n-1 轮
合并过程 前三轮 [(1, 1, 2), (2, 5, 7), (6, 7, 13)]
合并过程 末轮总和 [(209586, 281276, 490862)]
merge_heap 动过传进来的列表 False
merge_plan 动过传进来的列表 False
计数 04 merge_heap 动过传进来的列表 False
耗时 01 合并果子 列表版 n=1000 0.001000 秒
耗时 02 合并果子 堆版   n=1000 0.000352 秒
耗时 01 合并果子 列表版 n=2000 0.003611 秒
耗时 02 合并果子 堆版   n=2000 0.000725 秒
耗时 01 合并果子 列表版 n=4000 0.014905 秒
耗时 02 合并果子 堆版   n=4000 0.001607 秒
倍数 列表版 4000/1000 14.91
倍数 堆版 4000/1000 4.57
列表版每一档都更慢 True
规模翻四倍时列表版涨得更多 True
计数 02 堆版第一档更快 True
空列表 两版都是 0 True
单堆 两版都是 0 True
两堆 两版都是和 True
计数 03 两堆 堆版 8

$ py task2_kth_largest.py
k=1 排序版 999998089 堆版 999998089
第k大 k=1 一致 True
k=2 排序版 999992302 堆版 999992302
第k大 k=2 一致 True
k=3 排序版 999991022 堆版 999991022
第k大 k=3 一致 True
k=10 排序版 999937084 堆版 999937084
第k大 k=10 一致 True
k=100000 排序版 497487606 堆版 497487606
第k大 k=100000 一致 True
k=199999 排序版 5017 堆版 5017
第k大 k=199999 一致 True
k=200000 排序版 2782 堆版 2782
第k大 k=200000 一致 True
计数 01 第k大 k=10 999937084
计数 02 第k大 k=200000 2782
前10大 两版一致 True
前10大 前三个 [999998089, 999992302, 999991022]
自己写的堆 前10大 与 nlargest 一致 True
自己写的堆 前10大 前三个 [999998089, 999992302, 999991022]
耗时 01 第k大 排序版 k=10 0.020511 秒
耗时 02 第k大 堆版   k=10 0.003073 秒
倍数 k=10 排序比堆 6.68
耗时 01 第k大 排序版 k=100000 0.020000 秒
耗时 02 第k大 堆版   k=100000 0.023309 秒
倍数 k=100000 排序比堆 0.86
耗时 01 第k大 排序版 k=199999 0.020345 秒
耗时 02 第k大 堆版   k=199999 0.004104 秒
倍数 k=199999 排序比堆 4.96
计数 03 k小的时候堆更划算 True
k 小的时候堆更划算 True

$ py task3_running_median.py
数据流 [5, 15, 1, 3, 8, 7, 9, 10, 6, 11, 4]
中位数 [5, 10, 5, 4, 5, 6, 7, 7.5, 7, 7.5, 7]
中位数 个数 11
中位数 是每一步的序列 True
第1 步 1 5 0 None  中位数 5
第2 步 1 5 1 15  中位数 10.0
第3 步 2 5 1 15  中位数 5
第4 步 2 3 2 5  中位数 4.0
第5 步 3 5 2 8  中位数 5
第6 步 3 5 3 7  中位数 6.0
第7 步 4 7 3 8  中位数 7
第8 步 4 7 4 8  中位数 7.5
第9 步 5 7 4 8  中位数 7
第10 步 5 7 5 8  中位数 7.5
第11 步 6 7 5 8  中位数 7
不变式 每一步都有序 True
不变式 最后一行的两个堆顶 7 8
计数 01 不变式 长度差不超过一 True
计数 02 不变式 lo 顶不大于 hi 顶 True
空流 中位数 []
一个数 中位数 [7]
两个数 中位数 [4, 6.5]
第一个数的状态 [(1, 7, 0, None)]
计数 03 单个数 的中位数 7

$ py task4_min_heap.py
手写堆弹出序列与 heapq 一致 True
手写堆 与 heapq 一致 True
与原数组排序一致 True
手写堆 前 8 个弹出 [0, 3, 3, 5, 5, 5, 6, 7]
原数组 前 8 小 [0, 3, 3, 5, 5, 5, 6, 7]
每推一个数之后 堆序性质都成立 True
每弹一个数之后 堆序性质都成立 True
计数 01 推完 50 个数之后 元素个数 50
推完 50 个数之后 元素个数 50
穿插 push/pop 之后 弹出值都对 True
计数 02 穿插之后 剩下元素个数 26
穿插之后 剩下元素个数 26
耗时 01 推 1000 个数 手写堆 n=1000 0.000192 秒
耗时 02 推 1000 个数 heapq  n=1000 0.000045 秒
手写堆与 heapq 的差距 4.25 倍
耗时对照 手写堆比heapq慢 4.25
单元素弹出 5 剩下 0
空堆弹出报错 IndexError: list index out of range
空堆弹出报错类型 IndexError
```

任务 1 与任务 2 的那几个大数字（总和、第 k 大、前 10 大）都由**给好的种子**决定
（`random.seed(11)` / `random.seed(5)`），换台机器也是一样——判分自己按同一个种子重算一遍再对照。
秒数每次都变（任务 2 里 k=10 万那一档两个版本差不多、倍数只有 0.86，这正是课件那句
「k 涨到 n 的一半时两者差不多了」），判分只看趋势。
任务 1 的 `合并过程 末轮总和` 那个大数是**所有堆的重量之和**，别与 `计数 01` 的总代价搞混——
前者是「最后合成的那一堆有多重」，后者是「每一轮代价加起来」。
任务 2 的 `计数 03` 与 `k 小的时候堆更划算` 是同一个判断的两种打印，都是 `True`。

留白版原样跑是不通过的（本机实测 4 个任务 0 个通过、退出码 1）：四个函数都交回占位值
（`0` / `[]` / 空三元组）、三档耗时全是 `0.000000`、`Merge` 与堆的两版结果自然对不上——
那是起点，不是 bug，每条 FAIL 都会点名是哪个 TODO。

`solutions/0018-heap-and-priority-queue/` 里连 `tools.py` 与 `run_tests.py` 都有一份：
四个任务都只 `import` 给好的 `tools`、**任务之间不互相 import**，所以拷一个也能跑，
四个一起拷最省事；`py run_tests.py` 应当四个任务全过（本机实测几十秒，
其中任务 2 的 20 万个数要跑几遍、任务 1 的三档各跑 5 次）。

## 任务表 · 0021（`0021-dfs-bfs-search/`）

四个任务都在一套网格与图的模板上：**四行邻居判断**（不越界 → 不是墙 → 没走过 → **当场标记**）
是这一课最容易写错的地方，`blocked` 的 `True` 是**不能走**（这个约定写反了程序照样跑，只是答案全错）。
DFS 一律写**显式栈**，不写递归（递归上限 1000、实际 998 层，网格一条路就能走到几千格）。

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 两套模板与两种走法 | `task1_dfs_bfs.py` | 补 `dfs_reach` / `bfs_reach`（网格上从起点能走到几个格子）、`dfs_walk_order` / `bfs_walk_order`（邻接表上的**访问次序**） | 两套模板的差别**只有一行容器**（`stack.pop()` 换成 `q.popleft()`），四行判断完全一样——「能走到哪里」与走的先后无关；标记写在**入队（入栈）的那一刻**；次序一律照 `tools.DIRS` 那个固定次序走 | `计数 01/02`（6×6 有墙那张图上两套都是 **29**）、`两套模板个数一致` 是 `True`；`次序 点数一致吗` 是 `True`、`次序 第二个点一样吗` 是 **`False`**（两串次序从第二位就分开）；`计数 03/04`（50×50 大图两套都是 **2063**）、两套都走完且都没超过总点数；`大图 两套都没超过总点数` 是 `True` |
| 2 · 迷宫最短路与 DFS 的代价 | `task2_maze_shortest.py` | 补五段：`bfs_steps`（最少步数，走不到 `-1`）、`bfs_treasure`（同一套模板，交回 `(步数, 捡到的宝箱个数)`）、`dfs_steps`（把所有路试完取最短）、`dfs_calls`（只数递归调用了几次）、`dfs_calls_limited`（带**调用次数上限**，超了交回 `(None, calls)`） | 步数是**跟格子一起进队列**的（队列里放 `(行, 列, 步数)`），别另外维护「当前第几层」的变量；BFS **第一次把终点弹出队列时的步数就是最短的**，DFS 没有这个性质、得把所有路试完；三段 DFS 都必须**把 `seen[r][c]` 收回来**（`seen[r][c] = False`），不然第一条路走到底就再也试不出第二条路；`dfs_calls_limited` 超过上限交回 **`None`**（不是 `-1`，`-1` 是「走不到」） | 15×15 迷宫（183 个能走的格子）BFS 给出 **56** 步，而 DFS 试到 **400001** 次还没试完、交回 `None`；空方格图上 DFS 的调用次数 **4×4 = 1271、5×5 = 90111**（与课件那两个数逐字一致），12×12 直接撞上限；宝箱那一题是 56 步、捡到 **4** 个；`计数 01/04` 与 `12x12` 那三行都要对 |
| 3 · 岛屿数量、连通块与多起点 | `task3_islands.py` | 补 `count_islands(rows)`、`count_components(n, edges)`（搜索版）、`count_components_uf(n, edges)`（并查集版）、`reach_all(n, adj, starts)`（多起点到达） | 岛屿与连通块是同一套模板的两种包装：每遇到一块**没走过的陆地**就计数加一、再从那一格把整块走完；只有上、下、左、右四个方向算连在一起（**斜着挨着不算**）；并查集那一份**一行遍历都没有**（只把每条边的两个端点合并、最后数还剩几个根）；多起点的关键是**共用一张 `seen`**：几个起点先全部标上、一起入队 | 三道岛屿题是 **4 / 5 / 4**；3000 个点、4002 条边的图上搜索版与并查集版都是 **4** 块、`连通块 两种数法一致` 是 `True`；迷宫四个起点里 `(7, 7)` 是墙、到达 **183**；50×50 大空图两个起点到达 **2500**（相加会得到 5000，那是错的）；点边列表多起点是 **300**、单起点对照 200 |
| 4 · visited 标记的时机 | `task4_mark_timing.py` | 补 `bfs_trace(n, m, blocked, start, target, mark_on_push)`（交回 `(步数, 入队次数, 队列最长长度)`，开关决定入队时标记还是出队时标记）与 `bfs_trace_grid(size, mark_on_push)` | 出队时标记那一支：入队时**不看 `seen`**、`pushes += 1`，等 `popleft` 出来 `if seen[r][c]: continue` 再标记；两个版本都要能算完（出队时标记要多判一次 `seen`）；**出队时标记这一版是要保留的写法**（它是要看的对象，不是要改的错） | 答案处处一样（6×6 都是 **10** 步、迷宫都是 **56** 步、60×60 都是 **118** 步），入队次数却一路拉开：6×6 网格 **36 → 119**（3.31 倍）、10×10 **100 → 359**（3.59）、20×20 **400 → 1519**（3.80）、迷宫 **144 → 453**；队列最长也跟着涨（100×100 上 **100 → 398**）；`计数 01/02`、三档的 `计数 10/11` 都是确定值 |

### 0021 的期望输出形状

判分不 import 学生代码来判（探针只用来试函数接口），它读的是**任务脚本自己打印的行**。
任务 1、3、4 的这些行是本机参考解的原样值：

```text
$ py task1_dfs_bfs.py
计数 01 网格 DFS 到达 29
计数 02 网格 BFS 到达 29
两套模板个数一致 True 29
次序 DFS [1, 6, 9, 17, 10, 11, 14, 15, 5, 4, 3, 13, 19, 18, 12, 8, 7, 16, 2]
次序 BFS [1, 2, 6, 3, 8, 7, 9, 4, 16, 10, 17, 5, 11, 15, 12, 18, 14, 13, 19]
次序 点数一致吗 True
次序 第二个点一样吗 False
计数 03 大图 DFS 到达 2063
计数 04 大图 BFS 到达 2063
大图 两套都走完 True
大图 两套都没超过总点数 True
小图 点数 20
小图 边数 23
小图 起点 1

$ py task3_islands.py
计数 01 小网格 岛屿数量 4
计数 02 对角线 岛屿数量 5
计数 03 课件 岛屿数量 4
对角线 网格行数 4
计数 04 连通块 搜索版 4
计数 05 连通块 并查集版 4
连通块 两种数法一致 True 4
耗时 01 连通块 搜索版 n=3000 0.000513 秒
耗时 02 连通块 并查集版 n=3000 0.000815 秒
两条路各量一次 答案仍一致 True
计数 06 迷宫 多起点到达 183
起点 (0, 0) 是墙吗 False
起点 (14, 14) 是墙吗 False
起点 (7, 7) 是墙吗 True
起点 (10, 14) 是墙吗 False
计数 09 大空图 两个起点到达 2500
大空图 两个起点相加是多少 5000
计数 07 点边列表 多起点到达 300
点边列表 单起点对照 200
计数 08 大图 连通块 1
大图 点数 2500
大图 从 0 号点走得到几个 2500

$ py task4_mark_timing.py
6x6 两版答案一致 True 10
6x6 入队时标记 入队次数 队列最长 29 4
6x6 出队时标记 入队次数 队列最长 73 13
计数 01 6x6 入队时标记 入队次数 29
计数 02 6x6 出队时标记 入队次数 73
倍数 01 入队次数 出队时标记 2.52 倍
方格 6x6 两版答案一致 True 10
计数 10 方格 6x6 入队时标记 入队 36
计数 11 方格 6x6 出队时标记 入队 119
方格 6x6 队列最长 两版 6 22
倍数 02 方格 6x6 3.31 倍
方格 10x10 两版答案一致 True 18
计数 10 方格 10x10 入队时标记 入队 100
计数 11 方格 10x10 出队时标记 入队 359
方格 10x10 队列最长 两版 10 38
倍数 02 方格 10x10 3.59 倍
方格 20x20 两版答案一致 True 38
计数 10 方格 20x20 入队时标记 入队 400
计数 11 方格 20x20 出队时标记 入队 1519
方格 20x20 队列最长 两版 20 78
倍数 02 方格 20x20 3.80 倍
迷宫 两版答案一致 True 56
迷宫 入队次数 两版 144 453
60x60 入队时标记 步数 118
60x60 出队时标记 步数 118
60x60 两版步数一致 True
耗时 01 60x60 入队时标记 n=60x60 0.001684 秒
耗时 02 60x60 出队时标记 n=60x60 0.002407 秒
队列最长 入队时标记 100
队列最长 出队时标记 398
```

任务 1 的 `大图 两套都走完 True` 与 `次序 第二个点一样吗 False` 这两行正好是一对：
**能走到哪些点**两套必须一样，**先访问到哪个点**两套必须不一样——判分两样都核。
任务 4 的倍数从 3.31 涨到 3.80，规模越大越靠近 4：一个格子最多四个邻居，
出队时标记意味着它会被每个邻居各入队一次，所以入队次数最多是点数的四倍。
到达个数、岛屿数、连通块数、入队次数、调用次数都是**确定值**，判分精确核对；秒数只看趋势。

**DFS 那几项一律限量**：课件里 6×6 空方格的 DFS 要跑 9.68 秒、1847 万次调用，
所以判分只在小规模上核它的**精确**调用次数（4×4 = 1271、5×5 = 90111，两个确定值都来自课件），
更大的规模一律走带上限的版本、只看它有没有撞上限（本机 6×6 用 0.21 秒撞掉 40 万次）。

留白版原样跑是不通过的（本机实测 **21 PASS / 87 FAIL、退出码 1，0 处 Traceback**）：
两套模板都只交回起点、次序两行都是 `[]`、迷宫步数 `-1`、DFS 调用次数 `0`、
岛屿与连通块全是 `0`、四类入队次数与耗时全是 `0` / `0.000000`——
那是起点，不是 bug，**每一条 FAIL 都点出了缺哪一段 TODO**。

`solutions/0021-dfs-bfs-search/` 里连 `tools.py` 与 `run_tests.py` 都有一份：
四个任务都只 `import` 给好的 `tools`、**任务之间不互相 import**，所以拷一个也能跑；
`py run_tests.py` 应当四个任务全过（本机实测 4 秒上下，其中 DFS 那几段限量跑各占零点二秒）。

## 任务表 · 0025（`0025-dp-knapsack/`）

四个任务把 0/1 背包、完全背包、恰好装满、分组背包的**写法差别**摆在一起。
判分每个任务都走**两条证据路**：读脚本自己打印的行（判分另有参照实现重算一遍），
再另起探针进程 import 你的函数、拿判分**自己单独种子的数据**试。

| 任务 | 文件 | 要写的 TODO | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 0/1 背包的两种等价写法 | `task1_knap01.py` | `knap01_2d(w, v, C)`（二维表 `dp[i][c]`）、`knap01_1d_rev(w, v, C)`（压成一维、内层**逆序**） | 拿的那一支查的是 `dp[i-1][c-w[i-1]]`（**前 i-1 件**），看懂这个下标，一维版为什么必须逆序就不言自明：逆序时 `dp[c-w[i]]` 还没被本轮改过 | 两版在判分自造的 15 组上逐组对枚举；两版处处一致；容量 0 时都是 0 |
| 2 · 内层循环方向 | `task2_direction.py` | `knap01_1d_fwd`（内层**正序**——错：同一件会被重复选）、`knap_complete`（完全背包，就是这一版）、`first_wrong(w, v, C)`（在**某一个容量**上交回 `(容量, 枚举答案, 正序答案)`） | 正序错版与完全背包**循环体逐字相同**：答案**总是偏大**，而且**恰好等于完全背包**；`first_wrong` 按 `(先算正序版 → 再枚举 → 再比)` 的次序写 | 判分按种子 **5** 造 400 组自己数：正序错 **297** 组、逆序错 **0** 组；不一致的那些组里正序**总是偏大**、且都等于完全背包；课件那个反例是重量 `[6, 9, 1, 8, 4]`、价值 `[2, 6, 4, 12, 16]`、容量 8 → 逆序 **20**、正序 **32**、枚举 **20** |
| 3 · 恰好装满 | `task3_exact.py` | `knap01_exact`（只把 `dp[0]` 设 0、其余全设负无穷）、`knap01_exact_rev`（初始化照上面、内层**正序**）、`probe_exact`（独立写一遍）、`first_short` | 非法状态用**负无穷**（不是 0）是对这一问唯一的正确初始化——写成全 0 会让它悄悄交回「不超过」那一问的答案；拿负无穷比大小之前要先判 `dp[c - w] != NEG`（`-inf + 价值` 还是 `-inf`）；`probe_exact` 必须**自己站得住**，不能去调 `knap01_exact`（探针拿判分自己的数据试它） | 重量 3/5/7 时恰好凑不出的容量是 **1、2、4、6、9、11、13、14**；`probe_exact` 与 `knap01_exact` 在任何一组上都是同一个值；判分对「无解」是**按值**认的（`float('-inf')`，不是 `None` 也不是 0） |
| 4 · 完全背包与分组背包 | `task4_complete_group.py` | `knap_complete2`（物品在外、容量正序）、`knap_complete_cap`（容量在外、逐容量从小到大推）、`knap_group(groups, C)`（**每组最多选一件**） | `knap_complete2` 与任务 2 的 `knap01_1d_fwd` 循环一模一样，只是名字与注释不同——一个是对的、一个是错的，差别在**问的是哪个问题**；分组背包是**组在外、容量在中逆序、组内物品在最里**，容量那一层的逆序保证一组里最多拿一件 | 完全背包两版在判分自造的 300 组上处处一致（不一致 0 组）；分组背包与「枚举每组取法」的答案一样；写反了组与容量那一层的次序，答案会偏大 |

### 0025 的期望输出形状

四个任务脚本各自都会把参数、每一批随机数据的 JSON、每一条用例的答案打出来，
判分按**标签整段**认行（`<标签>` 后面跟空白或没有，绝不做前缀匹配）。几个要记住的数：

```text
方向那一批（种子 5、400 组、limits [8, 9, 20, 20]）
  对拍 逆序与枚举不一致的组数 与 总组数   0 400
  对拍 正序与枚举不一致的组数 与 总组数   297 400
  对拍 不一致的那些组里正序总是偏大       True
  对拍 不一致的那些组里正序都等于完全背包 True
  揪出一组（按同一个取数次序找到的第一组）
    重量 [6, 9, 1, 8, 4]  价值 [2, 6, 4, 12, 16]  容量 8
    正序 32、枚举 20
恰好装满那一批（重量 3/5/7）
  凑不出来的容量   1、2、4、6、9、11、13、14（原样是负无穷）
  恰好装满与「正序版」给出不同答案的那些容量   按判分自己的那一批算
任务 4 收尾那一行   完全背包两版一致 / 分组背包与枚举一致 这些是 True
```

判分只判**确定值**：价值、偏大的数额、负无穷的格、对拍的组数、反例那一组、无解的容量个数。
**秒数一律不判**（本机实测、会浮动，只当趋势看）。它还会认一认「这一段是不是还没写」：
起一次探针看那几个 TODO 函数是不是清一色交回负无穷或 `None`，是的话每条 FAIL 后面都会补一句
「这一条要 TODO n 写出来才可能过」。所以空模板原样跑**每一条 FAIL 都点得出是哪个 TODO**
（四个任务文件各自**也能跑出完整的打印**、不会崩、不会 Traceback，只是每一行都被判成 FAIL——
这正是这一课要练的两条主线）。

**硬凑 print 后的数字没用**：判分自己有一份参照实现（二维表 / 逆序一维 / 枚举 / 逐容量递推 /
分组枚举 / 恰好装满），期望值是它在**判分自己砌的那批数据**上现算的，不是抄来的常数；
探针用的种子也与脚本那几批刻意不同，**只写 print 不写实现拿不到 PASS**。
（还有一条：文件名、函数名、函数签名、`CASES_*` 的种子与上限、带 `# 别改` 的每一行打印
都是判分接口——判分自己按同一个种子复现同一批数据，你改了种子它就对不上，直接判 FAIL。）

留白版原样跑：四个任务全部 FAIL，最后一行会点出是哪个任务没过。
`solutions/0025-dp-knapsack/` 里 `tools.py` 与 `run_tests.py` 与空模板那份**逐字节相同**，
把四个任务文件拷进任务目录覆盖同名文件，`py run_tests.py` 应当四个任务全过
（本机实测 176 PASS / 0 FAIL、最后一行是「四个任务全过。」、退出码 0）。

## 任务表 · 0026（`0026-dp-sequence-interval/`）

这一课练四件事，都是「**先把状态定义写出来，再写代码**」——
上一课背包的状态是题目递给你的（容量），这一课的状态得自己设计。
「前 i 个的最大 XXX」和「**以第 i 个结尾**的最大 XXX」看着差不多，选错一句就写不出转移方程。

| 任务 | 文件 | 要交的东西 | 状态定义 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 最长递增子序列 | `task1_lis.py` | `lis_dp`（`O(n²)`，交回 `(长度, dp)`）、`lis_bisect`（`O(n log n)`，交回 `(长度, tails)`）、`lis_recover`（DP 加 `prev` **回溯**出那条子序列） | $dp[i]$ = **以 $a_i$ 结尾**的最长递增子序列长度，答案是 `max(dp)` **不是** `dp[n-1]`；严格递增用 `bisect_left`（换成 `bisect_right` 就变成「不下降」，全相同元素上会从 1 变成 4） | 课件那组 `[10, 9, 2, 5, 3, 7, 101, 18]` 上 `LIS 两版长度一致`、`tails 与恢复出的子序列相同吗` 是 **`False`**、`恢复出的就是判分要的那一条` 是 `True`（`[2, 5, 7, 101]`）、`恢复出的严格递增` 与 `恢复出的长度等于 LIS 长度` 都是 `True`；全相同元素 `[5, 5, 5, 5]` 两版长度都是 **1**；500 组随机数据上两版长度从不打架、恢复出的长度不对的组数是 **0**；二分版在最大一档上更快、DP 版涨得更多 |
| 2 · 最长公共子序列 | `task2_lcs.py` | `lcs(s, t)`、`table_shape(table, s, t)`（交回 `(行数, 列数, 两条边上的 0 的个数)`） | $dp[i][j]$ = s 的**前 i 个**与 t 的**前 j 个**的 LCS 长度；依赖方向是**左、上、左上**，天然对应逐行逐列填，所以**不用**操心枚举顺序；第一行与第一列全是 0 | 打印出来的那张表判分**逐格**对照；`第一行第一列 全是0`、`第一行第一列 的 0 的个数`、`表的行数列数`、`右下角等于长度` 都要对（本机那组是 **8×7 的表、13 个 0**）；探针在判分自造的 10 组字符串（含空串、单字符、倒序、重复字符）上核 `lcs` 与 `table_shape` |
| 3 · 最长回文子序列 | `task3_palindrome.py` | `lps(s)`（区间 DP）、`lps_brute(s)`（暴力版当尺子） | $dp[i][j]$ = $s[i..j]$ 这段里的最长回文子序列长度；依赖的是**比它更小的区间**，所以枚举顺序不能随便：**必须先算短的区间、再算长的**（`for length in range(2, n + 1)` 那一行是关键） | 七组短串上「区间 DP / 暴力」两列都等于判分自己算的长度；`全相同 等于长度`（`aaaaaaaa` 给 8）；200 组随机小串（长度 0~12、字母表 abc）上与暴力不一致组数是 **0**；`O(n²)` 的表要真的建出来（判分看耗时趋势） |
| 4 · 石子合并 | `task4_stone.py` | `stone_dp(a, order='asc')`、`stone_desc(a)`（**故意把长度枚举写反**的那一版）、`stone_brute(a)`（`lru_cache` 暴力版当尺子） | 转移要在**最后那一次合并断在哪里**上枚举：`min(dp[i][k] + dp[k+1][j]) + sum(i..j)`，末尾那个区间和是**这次合并本身的代价**（用前缀和 `O(1)` 拿）；`order='desc'` 那一支一个字都不用另写，同一个循环、只是 `lengths` 反过来 | 三组课件数据从小到大是 **19 / 57 / 51**、从大到小是 **10 / 25 / 21**（**偏小，而且小得离谱**）；`从小到大 三组都与暴力一致` 是 `True`、`从大到小 三组都与暴力一致` 是 `False`；边界：单堆 0、两堆是它们的和、`[5, 5, 5, 5]` 是 **40**、`[9, 9, 9]` 是 **45**；200 组随机数据（`random.seed(9)`、1~7 堆、每堆 1~20）上从小到大错 **0** 组、从大到小错 **137** 组 |

### 0026 的期望输出形状

判分分两路，缺一不可：跑任务脚本读它自己打印的行（主要证据），再另起探针 import 你的函数
用**判分自己造的数据**试（独立证据——探针的种子与脚本那几批刻意不同，
判分用 `seed(1011)` / `seed(2027)` 等、脚本用 `seed(11)` / `seed(12)`，**只写 print 不写实现拿不到 PASS**）。
固定格式四种，都由 `tools.py` 生成：

```text
计数 NN <标签> <值>            整数 或 True/False
耗时 NN <标签> <n=…> <秒数> 秒  六位小数
<标签> <值>
<标签> <值1> <值2>
```

判分**按标签找行**（不按编号）——标签里写着是这一组数据、是哪个方向。留白版会把这些行**原样打出来**，
只是值是占位的（`0` / `[]` / `-1` / `0.000000`），所以「看得见的格式」与参考解完全一致。
这一课真正要拿走的一句话：**答案偏离的方向会告诉你错在哪一类**——
上一课背包写错方向时答案是**偏大**的（同一件物品被拿了多次），这里写错顺序是**偏小**的。
看到答案不对，先问一句「它错向了哪边」。

**判分看趋势不看常数**：秒数每次运行都会浮动，所以耗时那一列只要求「二分版每一档都比 DP 版快」
「规模翻四倍时 DP 版涨得更多」「二分版在最大一档更快」，以及几处留了 25% 噪声带的比较，
**绝不核对具体秒数**。判分里核对精确值的是那些**确定量**：`19 / 57 / 51`、`10 / 25 / 21`、
**137 组错**、500 组不一致 0 组、`4 / 3 / 5 / 4`、13 个 0、8×7 的表、`[2, 3, 7, 18]` 与 `[2, 5, 7, 101]`。

`solutions/0026-dp-sequence-interval/` 里连 `tools.py` 与 `run_tests.py` 都有一份
（两侧内容完全相同）：把四个任务文件拷进任务目录就能直接跑，`py run_tests.py` 应当四个任务全过。

## 任务表 · 实验三（`0027-lab-03-recommend-and-verify/`）

这一课把「用模型帮忙」拆成一条**能被程序检查**的链：

```text
题面 ──build_prompt──▶ 提示词 ──call_model／fake_model──▶ 一段文本
     ──parse_naive／parse_robust──▶ 字典 ──classify（交叉检查）──▶ 候选算法族
     ──run_trial（拿暴力当尺子）──▶ 每个候选实现的结论 ──nothing_passed──▶ 这条链验出东西了吗
```

三个判分层的骨架：五层里前四层对应四个任务，第 5 层把 `socket.socket` 换成会抛异常的版本
再跑一遍整条链——**这一课的判分不碰网络**，所以在没网的机器上也能跑，也不会因为网络抖动而不稳定。

| 任务 | 文件 | 要交的东西 | 这一段在链上的位置 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 造提示词 | `task1_prompt.py` | `build_prompt` / `call_model` / `fake_model` / `recommend` | 题面 → 提示词 → **那道缝**（模型调用） | 判分逐条去认四样约束的锚点：**「格式固定」+「JSON」**（三个键名）、**「只输出」+「不要」**（不许有别的文字、不许用围栏）、**「可选的算法族」+ 八张族名表**（八张表的族名要写全）、**「转义」+ `\"` 的写法**；题面要出现在提示词里而且是 `strip()` 之后的样子；`提示词里的围栏行` 是 **0**（提示词本身 8 行，含末尾空行） |
| 2 · 解析返回文本 | `task2_parse.py` | `parse_naive` / `parse_robust` / `explain_samples` | 一段文本 → 能取键的字典 | 六种形态里朴素过 **1** 种、加固过 **5** 种（`explain_samples()` 交回 `(1, 5)`）；第六种「内容本身不是合法 JSON」（引号没转义）两版都救不了，这时不许抛异常、也不许交回半个字典，要交回 **`'<JSONDecodeError>'`** 这样的**字符串标记** |
| 3 · 关键词打分 | `task3_classify.py` | `classify` / `explain_problems` | **不靠模型**的交叉检查 | 排序口径两级：先按命中数降序，再按族名字典序升序（第二级不是装饰：「岛屿数量」上并查集与图的搜索都是 1 个命中，谁在前就靠字典序，图的搜索在前）；六道题面的首选与命中词表都要对；「合并果子」那一行的**背包是假阳性**（题面里有「重量」两个字）——**这一行要如实保留**，它正是这一段要暴露的东西 |
| 4 · 端到端验证 | `task4_pipeline.py` | `resolve` / `run_trial` / `nothing_passed` | 推荐 → 候选实现 → 暴力验证 → 结论 | 两个实现选出的个数是 **1 与 6**、暴力给出的最优是 **6** 个；`实现数` 是 2、`通过的实现数` 是 1、`这条链没验证出东西` 是 `False`；解析坏掉时 `ok` 是 `False`、`reason` 是 **`<JSONDecodeError>`**（`resolve` 吃的就是任务 2 那个标记）；`首选与模型一致` 是 `True` |

### 实验三的期望输出形状

判分两路证据缺一不可：跑任务脚本读它自己打印的行（脚本把每一格都打出来，判分**按标签找行**、
行里的值都是**从函数交回的东西里查出来的**——留白版照样把这些行原样打出来，
只是值是占位的 `（还没接上）` / `0` / `False`），再另起探针 import 你的函数用判分自己造的数据试。
几个要记住的确定量：

```text
六种形态的成绩            1 与 5（朴素 1 种、加固 5 种）
第六种两版都救不了        交回 <JSONDecodeError>（字符串标记，不是异常）
explain_samples()         (1, 5)
六道题面的首选            木材加工→二分答案（命中 2 个：最大化、最长）
                         岛屿数量→图的搜索（命中 1 个：网格），并列 并查集（连通块）
                         合并果子→堆（命中 1 个：每次取最小），并列 背包（重量）← 假阳性
                         区间调度→贪心（命中 3 个：区间、不相交、按结束时间）
                         第 k 大→堆（命中 1 个：第 k 大）
                         跳石头→二分答案（命中 1 个：最短）
族名表大小                8
任务 4 的三条结论         A 1 个 / B 6 个 / 最优 6 个
                         解析坏掉时的 reason  <JSONDecodeError>
```

第 5 层会把 `socket.socket` 换成会抛异常的版本跑一遍整条链，并核对连接尝试次数为 **0**、
`call_model` 必须抛 `NotImplementedError`、装上的假模型必须交回**干净 JSON 一行**。
所以 `call_model` 的职责就是**明确地失败**，别写成「悄悄交回空串」——
那样「忘了换掉这个函数」会静默地变成「模型返回空」，后面每一段都在处理一个空字符串，查起来难得多。
任务 1 的 `recommend` 只到「拿到那段文本」为止、**不解析**（解析是任务 2 的事），
而且模型必须是**参数**，别在函数里写 `model = call_model` 之类的默认值把缝堵上。

判分里核对的是那些**确定量**：`1` 与 `5`、第六种的 `<JSONDecodeError>`、`explain_samples()` 的 `(1, 5)`、
六道题面的首选行与命中词表、`A 1 个 / B 6 个 / 最优 6 个`、`逐字` 的 `[(0, 60)]` 与那六个小区间、
三条 `nothing_passed`，以及**没有一条耗时断言**（本课一个时间都不量）。
留白版的成绩是 `0 层通过、5 层还没过`；参考解是 **105 条 PASS、0 条 FAIL、退出码 0**（连跑三次都一样）。

`solutions/0027-lab-03-recommend-and-verify/` 里连 `tools.py` 与 `run_tests.py` 都有一份
（两侧内容完全相同）：把四个任务文件拷进任务目录就能直接跑，`py run_tests.py` 应当五层全过。

## 任务表 · 0029（`0029-constant-factor-tuning/`）

这一课回答一个问题：**同一道题、同一个答案，为什么有的写法快两个数量级？** 答案不在「写得更漂亮」，
在**每一段各执行多少次操作**。所以它是一条先量后改的链：分段计时 → 上三到四招 → 和内置比 → 故意写错一次。

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 先量出瓶颈 | `task1_bottleneck.py` | 写 `segment_ops`（三段各多少次操作）、`analyze_segments`（哪段最慢）、`count_size_calls`（条件里的重复求值） | 三段是「装集合 / 排序 / 若干次 `in`」。**不能凭代码形状猜**：看着最重的 `A_set` 其实最轻，看着最无害的 `C_in` 最贵，因为它每次循环都在线性扫一整条数组。`analyze_segments` 的答案必须跟着**传进来的实测值**走，不能写死某一段——判分给两次不一样的实测值，第二次就露 | 三段操作次数在三组规模上逐组对上；`C 是 A 的几倍` 是 350；`猜的和实测一样吗` 是 `False`；`size()` 被调 **1001** 次（不是 1000——退出循环前还有一次失败的比较）、提到外面是 **1** 次、两版答案都是 499500；探针换成 n = 1234 再问一遍（**1235 / 1**） |
| 2 · 依次上三到四招 | `task2_tuning.py` | 写 `optimization_steps` / `tier_steps` / `solve_tier` / `tier_times`：四级从「列表 `in` + 逐行读入」一路改到「`sum` + generator」 | 四招的顺序不是随便排的：**换容器 → 整体读入 → 提前算不变式 → 用内置**（换容器省的是复杂度，抠语法省的是常数，先把钱大的做掉）。四格计数是**循环 / 相等比较 / 读入 / 建集合**；读入那一格**必须由读入器自己记**，不能按公式写。注意第 2 招：读入从 80000 降到 1，但**建集合从 1 涨到 400**——这正是第 3 招要收拾的 | 四级四格计数**逐级**对上（判分另算：`(1080000, 1080000, 9000) → (120, 1080000, 9000) → (120, 1080000, 1) → (120, 120, 1) → (1, 120, 1)`）；读入器账目对得上（`read_all` 1 次 / 逐行 0 次）；五级答案都是 400 且与标准答案一致；四级不一致的组数是 **0 组**；换容器那一处带**噪声容差 0.75**，另有一道**退化守卫**（四级耗时全是 `0.000000` 直接 FAIL） |
| 3 · 和内置比一次 | `task3_builtin.py` | 写 `compare_with_builtin`（五栏：`contain` / `sort` / `sum` / `min` / `role`）、`work_of`、`recursion_ceiling` | 五栏各交回「两边答案 / 两边各多少次值访问 / **差在哪一层**」。`sum` 那一栏两边值访问次数**一样**（都是 n）——差的是谁在绕这个循环，所以「次数一样、快 4.8 倍」不矛盾。`sort` 那一栏倍率上千，绝大部分是**复杂度**不是常数，把它当成「内置快一千倍」就学错了东西 | 五栏两边答案一致、值访问次数按规模算对上、`layer_of` 点到关键词（查找 / 复杂度 / 循环 / 每轮代价 / 分支）；倍率只打印不判死；**递归边界刻意不核具体数**：判分自己量 994、探针 import 之后量 992、脚本单跑量 995，**差 ≤4 层都算对**——核的是「有个 n 撑得住、再往上就不行」这个机制 |
| 4 · 故意写错一次 | `task4_break_it.py` | 写 `audit_broken_once` / `count_matches` / `audit_after_fix`：把 `stop = n` 改成 `stop = n - 1`（最后一个元素不看了），确认对拍抓得住，再改回来 | **对拍器自己也要被验一次**：抓不到错的对拍器，每轮都说「没事」。证据那一格是重点——要交出**最早对不上的那组原始数据**本身，有反例的否掉比没有反例的通过更有价值。为什么不是 50 组都露？因为有些组最后一个元素本来就不在区间里，两版答案一样，**这些「一样」不算对拍失效** | 50 组数据上对的那版加起来 **586**、坏的那版 **554**、坏版露了 **32 组**、`对拍抓到了吗 True`；证据那组数据连同两版答案（**17 / 16**）一起交回；`改回来之后不一致的组数` 是 **0 组**、`改回来之后还是坏的吗 False`——两头都对上才说明抓到的真是写坏的那一处 |

### 0029 的期望输出形状

四个脚本各带 `== 0029 … ==` 的小标题分段，判分按标签找行。**秒数每次都变，次数一个都不变**：

```text
$ py task1_bottleneck.py
== 0029 三段各量一次 ==
   三段各是什么：
      A_set  20 万个元素装进集合（看着最重）
      B_sort  排序同一批元素
      C_in  若干次「这个键在不在数组里」（看着最无害）
实测 A_set 0.002496 秒
实测 B_sort 0.005326 秒
实测 C_in 0.089400 秒
三段合计 0.097222 秒
== 0029 不看形状，看次数 ==
操作次数 A_set 60000
操作次数 B_sort 900000
操作次数 C_in 21000000
C 是 A 的几倍 350
== 0029 原以为哪段最慢 ==
凭形状猜最慢 A_set
实测最慢 C_in
猜的和实测一样吗 False
== 0029 循环条件里的重复求值 ==
写在条件里 size() 调用 1001
提到循环外面 size() 调用 1
两版答案一致吗 True
条件比循环体多判几次 1
== 0029 分段计时的结论 ==
   最慢的是 C_in，不是看着最重的 A_set；次数上 C_in 是 A_set 的 350 倍
   操作次数与耗时两栏都要看：次数是可复现的证据，秒数会被机器和噪声带着走。

$ py task2_tuning.py
== 0029 四招各是什么 ==
   第 0 级  起点：列表 in + 逐行读入
   第 1 级  第 1 招：换容器（列表 in → 集合 in）
   第 2 级  第 2 招：整体读入（逐行 → 一次 read().split()）
   第 3 级  第 3 招：提前算不变式（集合提到循环外）
   第 4 级  第 4 招：用内置（手写循环 → sum + generator）
== 0029 每一级的次数（确定量） ==
   第 0 级 循环 32000000 次 相等比较 32000000 次 读入 80000 次 建集合 1 次
   第 0 级耗时 0.102288 秒
   第 1 级 循环 400 次 相等比较 32000000 次 读入 80000 次 建集合 1 次
   第 1 级耗时 0.033441 秒
   第 2 级 循环 400 次 相等比较 32000000 次 读入 1 次 建集合 400 次
   第 2 级耗时 0.007923 秒
   第 3 级 循环 400 次 相等比较 400 次 读入 1 次 建集合 1 次
   第 3 级耗时 0.006814 秒
   第 4 级 循环 1 次 相等比较 400 次 读入 1 次 建集合 1 次
   第 4 级耗时 0.008005 秒
== 0029 每上一招，答案还对吗 ==
答案 0 级 400
答案 1 级 400
答案 2 级 400
答案 3 级 400
答案 4 级 400
标准答案 400
四级答案一致吗 True
== 0029 改正之后对拍一次 ==
四级答案不一致的组数 0 组
   四招上完再对拍一次：5 级里不一致 0 级——每改一处都要回验，这一格必须回到 0。
== 0029 换容器那一处的耗时（只当参考） ==
   第 0 级 0.102288 秒 → 第 1 级 0.033441 秒（换容器）
   这一条判了、过了：优化版 0.033441 秒，基线 0.102288 秒，快 3.1 倍（噪声容差 0.75）
== 0029 收尾 ==
   四招的顺序：换容器 → 整体读入 → 提前算不变式 → 用内置。
   先把钱大的做掉：换容器省的是复杂度，抠语法省的是常数。

$ py task3_builtin.py
== 0029 和内置比：四栏 ==
   contain 答案手写 119 内置 119 一致 True
手写 contain 120000000 次值访问 2.028605 秒
内置 contain 119 次值访问 0.004458 秒
差在哪一层 contain 查找那一层：列表是线性扫描 O(n)，集合是平均 O(1)
   sort 答案手写 [241, 254, 931, …（39 个数，此处省略）] 内置 [241, 254, 931, …（同一串）] 一致 True
手写 sort 3123750 次值访问 0.164418 秒
内置 sort 2500 次值访问 0.000998 秒
差在哪一层 sort 复杂度那一层：冒泡是 O(n^2)，Timsort 是 O(n log n)；常数只占一小部分
   sum 答案手写 135359 内置 135359 一致 True
手写 sum 300000 次值访问 0.005627 秒
内置 sum 300000 次值访问 0.001695 秒
差在哪一层 sum 循环那一层：手写每轮 FOR_ITER + 加法 + STORE_FAST，sum 整个循环在 C 里跑
   min 答案手写 10396 内置 10396 一致 True
手写 min 500000 次值访问 0.053011 秒
内置 min 100000 次值访问 0.001070 秒
差在哪一层 min 每轮代价那一层：反复 min 一遍遍扫全表，nsmallest 用堆 O(n log k)
   role 答案手写 [14998, 0, 0, 0, 0, 15005, 0, 0, 0, 0, 14999, 0, 0, 0, 0, 14998] 内置 [同一串] 一致 True
手写 role 480000 次值访问 0.018203 秒
内置 role 60000 次值访问 0.003101 秒
差在哪一层 role 分支那一层：if/elif 是一路比下来的，查表只索引一次
== 0029 倍率只当参考 ==
   sum 手写 0.005627 秒 → 内置 0.001695 秒；判了、过了：优化版 0.001695 秒，基线 0.005627 秒，快 3.3 倍（噪声容差 0.75）
   sort 手写 0.164418 秒 → 内置 0.000998 秒；判了、过了：优化版 0.000998 秒，基线 0.164418 秒，快 164.7 倍（噪声容差 0.75）
   min 手写 0.053011 秒 → 内置 0.001070 秒；判了、过了：优化版 0.001070 秒，基线 0.053011 秒，快 49.5 倍（噪声容差 0.75）
   排序那一栏的倍率分两层看：绝大部分是复杂度（O(n^2) 对 O(n log n)），
   只有一小部分是常数——它证明的是「别手写排序」，不是「内置快一千倍」。
== 0029 递归与迭代 ==
n=900 递归求和 404550
n=900 迭代求和 404550
n=900 迭代耗时 0.000011 秒
n=900 递归耗时 0.000094 秒
   两版各跑 5 遍取中位数（小段计时会被噪声盖住效应，跑够遍数才量得出来）
   递归每层都要建一个栈帧，所以同样是 900 层，慢的那一版就是它；更硬的问题是它到不了任意深。
   n = 995 递归版撑住了
   n = 997 递归版RecursionError
递归的边界 995
   边界就卡在 995 与 997 之间：默认上限 1000，主模块本身占一层；
   多一层调用就少一层栈，所以这个数会跟着调用位置浮动几层。
   深度跟着 n 长的递归一律改迭代——不只是慢，更要紧的是它到不了任意深。

$ py task4_break_it.py
== 0029 对拍：先跑对的那一版 ==
对拍的数据组数 50
两版答案不一致的组数 0
== 0029 故意写错一次 ==
对的那版加起来 586
坏的那版加起来 554
坏版露了几组 32
对拍抓到了吗 True
两版答案一样吗 False
== 0029 证据：最早对不上的那一组 ==
对不上的数据长这样 [2, 6, 3, 4, 3, 5, 6, 6, 3, 0, 0, 6, 6, 3, 4, 5, 6, 1, 4, 2, 1, 2, 1, 6, 2, 4]
这组数据上一组的答案 17
这组数据上坏版的答案 16
   差别只有一处：stop = n - 1 if broken else n —— 最后一个元素不看了。
   只有一个元素的数组上，答案会直接变成 0：错得不多，但已经错了。
== 0029 改回来之后 ==
改回来之后不一致的组数 0
改回来之后还是坏的吗 False
   两头都对上才说明「抓到的」真的是我写坏的那一处：坏版被抓到 32 组，改回来之后 0 组。
== 0029 这一段的结论 ==
   对拍器自己也要被验一次：抓不到错的对拍器，每轮都说「没事」。
   优化不许改答案——顺序是先让它对，再让它快，每快一次都重新证明它对。
```

这一课的判分里**核对的是次数，不是秒数**。判死的确定量是：三组规模的操作次数、`1001 / 1` 与
`1235 / 1`、四级四格计数、读入器账目、五栏答案与值访问次数、`586 / 554 / 32`、`0 组` 不一致。
耗时只在三处出现且三处都带保护：任务 2 的四级耗时（**退化守卫**：全 `0.000000` 就 FAIL，
这是留白版栽的那一条）+ 换容器那一处的**噪声容差 0.75**；任务 2 探针那一格只要求「有一格不是 0」；
任务 1 与任务 3 的耗时**只打印、判分一条都不读**。另有一条**不靠时钟的因果证据**：
第 4 级跑 16 遍只让读入器被调 0 次，第 0 级跑 1 遍就要 400 次——优化掉的是操作次数。

**`C_in` 那一段为什么最贵**：`keys * size`，循环只有几百次，但每次都在线性扫一整条数组。
`count_size_calls` 那一格的 `n + 1` 也值得记：**退出循环前还有一次失败的比较**，
所以条件里问 `size()` 是 1001 次而不是 1000 次——判分换成 n = 1234 再问一遍，写死 1001 会露。

留白版原样跑是不通过的（本机实测 0 层通过、**41 PASS / 67 FAIL**、退出码 1，
每条 FAIL 后面都点名是哪个文件的哪个 TODO）；参考解是 **5 层全过、109 PASS / 0 FAIL、退出码 0**。
`solutions/0029-constant-factor-tuning/` 里连 `tools.py` 与 `run_tests.py` 都有一份，
`py run_tests.py` 应当五层全过（本机实测约 33 秒，含两次探针子进程；任务 3 单跑自己占约 2 秒）。

## 任务表 · 0030（`0030-stress-test-and-review/`）

这一课把「样例过了就交」这件事拆成一条**能被程序检查**的链，四个任务就是四段：
换一把尺子（对拍）→ 换一批数据（生成器的范围）→ 换一种运行姿势（多组数据）→ 换数据规模（取模）。

| 任务 | 文件 | 要做什么 | 要点 | 怎么算过 |
| --- | --- | --- | --- | --- |
| 1 · 对拍：三把尺子量同一个候选解 | `task1_brute_ref.py` | 写 `run_trials`（500 组随机数据上，候选解与三把尺子各几组不一致）与 `first_bad`（交出**第一个**反例的组号、数据、两边答案） | 候选解里那个 bug 是给好的：`best` 从 `0` 起步，于是**全负数组**上交回 `0`。三把尺子只有两把能抓到它——**「同一个思路的参考解」抓不到**（它错在同一处），所以要拿 `first_bad` 找反例必须用独立那把。组号**从 0 起**。「修好初值」有个坑：**光把 `best` 改成 `-inf` 不够**，`cur = max(0, cur + x)` 那一句照样把当前段按回 0 | `不一致的` 三个数是 **0 / 58 / 58**；前 4 组数据与两把尺子的判定逐组对上；`first_bad` 交回的是**第 23 组**、数据 `[-7]`、候选 `0`、独立暴力 `-7`；修好初值之后那一格必须是 **0 组**；`run_trials()` 交回的表里该有的键一个都不能少，组数必须是 `int`（`'58'` / `58.0` / `None` 都算错） |
| 2 · 生成器的范围 | `task2_generator.py` | 写 `run_pair`：同一个 bug、同一个对拍器、同样 300 组，两种生成器各跑一遍 | 这一格要看见的是**0 组与 33 组是同一句话的两半**：bug 只在「全是负数」时才现形，所以「只造有正数的」生成器**永远抓不到**它。种子要放在循环**外面**（放里面每组退回同一个 n）。这一格也顺带证明了对拍器本身是有效的——它只是没被喂到对的数据 | `只造有正数的 300 组里抓到 bug 的有` **0 组**、`允许全负的 300 组里` **33 组**；前 3 组数据逐组对上（「允许全负的」那一列第 0 组就是 `[-7]`：候选 `0`、暴力 `-7`、`一致吗 False`）；`自己的 run_pair` 也要在「允许全负的」上抓到 **33 组**；探针拿**判分自己的生成器 + 另一个种子**再数一遍 |
| 3 · 多组数据要清空 | `task3_reset.py` | 写 `class Solver`（`answer` 累加、`reset` 清零）与 `run_cases`：三组数据各问一次，一版**忘了清空**、一版**每问都清空** | 三组是 `[[1, 2, 3], [10, 20], [5]]`、期望 `[6, 30, 5]`。忘了清空的错法是**累加**：第一组对，第二组变成 6+30=36，第三组 36+5=41——**第一组往往是对的**，所以只看第一组看不出来。`reset` 必须真的清零；`run_cases` 不能把传进来的 `cases` 改掉；`reset_per_case=False` 时**一次都不能调** `reset` | `忘了清空` 是 `[6, 36, 41]`、`每问清空` 是 `[6, 30, 5]`、`正确答案` 是 `[6, 30, 5]`；`忘了清空对吗 False` / `每问清空对吗 True`；两组各自的第 1 组都是 6；探针另起进程试「没人调 reset 时第二组是 11」「调一次 reset 之后再问交出 1」，并数「被 reset 了 N 次」 |
| 4 · 取模：小数据上看不出来 | `task4_modulo.py` | 写 `first_diff`（第一个让两版分家的 n）、`tail14`、`sample_rows`、`big_digits`、`random_bad`、`random_first`、`gap_cell` | `MOD = 10^9 + 7`。**小数据上两版逐字相同**（n = 10、30 都对得上），第一个分家点是 **n = 45**——所以「样例过了」在这里什么也证明不了。`first_diff` 不能写死 45（换个区间就露），区间**两端都要算进去**；`tail14` 要从**不取模**的完整值上切末 14 位，从取模值上切就错了；`big_digits` 数的是**不取模**时的位数，不是取模后的 | `n = 10 / 30` 两版相等、`n = 50 / 100 / 1000 / 10000` 都不等；`first_diff` 交回 **45**，且 `first_diff(41, 60)`、`first_diff(45, 60)` 两组另算；300 组随机 n（种子 3、n 在 21..120 之间）里**239 组**不相等、第一组不相等的 n 是 **51**；不取模在 n = 10000 时是 **2090 位**、取模值最多 10 位；`random_bad` / `random_first` 用判分自己的两组种子另算 |

### 0030 的期望输出形状

四个脚本都带 `== 0030 … ==` 的小标题分段，判分按标签找行：

```text
$ py task1_brute_ref.py
== 0030 对拍：两把尺子，同一批数据 ==
   种子 1，500 组随机数据（取值 -9..9，n 到 8）：
   → 与「同一个思路的参考解」对拍，不一致的: 0 组
   → 与「独立暴力解」对拍，不一致的        : 58 组
   → 与「独立分治解」对拍，不一致的        : 58 组
   前 4 组数据与两把尺子的判定:
      第 0 组 n=3 数据 [9, -7, -1] 候选解给 9 暴力解给 9 一致吗 True
      第 1 组 n=2 数据 [6, 5] 候选解给 11 暴力解给 11 一致吗 True
      第 2 组 n=8 数据 [3, -3, -6, 6, -9, 3, 4, -9] 候选解给 7 暴力解给 7 一致吗 True
      第 3 组 n=8 数据 [-1, -2, 9, -6, 1, -9, -9, -9] 候选解给 9 暴力解给 9 一致吗 True
   独立暴力抓到的第一个反例:
      在第 23 组
      数据 [-7]
      候选解给 0
      独立暴力给 -7
   → 修好初值（best 从 -inf 起步）之后，与独立暴力对拍不一致的: 0 组

$ py task2_generator.py
== 0030 生成器的范围：同一个 bug、同一个对拍器、同样 300 组 ==
   只造有正数的 300 组里抓到 bug 的有 0 组
   允许全负的 300 组里抓到 bug 的有 33 组
   前 3 组数据（同一个种子，两个生成器各起一个）:
      只造有正数的 第 0 组 n=1 数据 [2] 候选解给 2 暴力解给 2 一致吗 True
      只造有正数的 第 1 组 n=3 数据 [-8, 9, -4] 候选解给 9 暴力解给 9 一致吗 True
      只造有正数的 第 2 组 n=7 数据 [3, 7, 2, 8, 5, 7, -1] 候选解给 32 暴力解给 32 一致吗 True
      允许全负的 第 0 组 n=1 数据 [-7] 候选解给 0 暴力解给 -7 一致吗 False
      允许全负的 第 1 组 n=2 数据 [2, -4] 候选解给 2 暴力解给 2 一致吗 True
      允许全负的 第 2 组 n=5 数据 [-1, -3, -8, 9, -4] 候选解给 9 暴力解给 9 一致吗 True
   换成你自己写的 run_pair 跑一遍（同一个种子、同一个生成器）:
      自己的 run_pair 在「允许全负的」上：300 组 里抓到 33 组
   独立暴力抓到的第一个反例:
      出现在第 0 组
      数据 [-7]
      候选解给 0
      独立暴力给 -7

$ py task3_reset.py
== 0030 多组数据：第一组往往是对的 ==
   三组数据      : [[1, 2, 3], [10, 20], [5]]
   忘了清空      : [6, 36, 41]
   每问都清空    : [6, 30, 5]
   正确答案      : [6, 30, 5]
   忘了清空对吗: False    每问清空对吗: True
   → 两组各自的第 1 组: 忘了清空 6 / 每问清空 6 / 期望 6

$ py task4_modulo.py
== 0030 取模：小数据上看不出来 ==
   MOD = 1,000,000,007
   n        不取模（末 14 位）        取模后的值      两者相等吗
      10      …            55               55   True
      30      …        832040           832040   True
      50      …   12586269025        586268941   False
     100      …48179261915075        687995182   False
    1000      …95166849228875        517691607   False
   10000      …10059947366875        271496360   False
   → 第一个分家的 n（两版从这里开始不等）: 45
   300 组随机 n（种子 3，n 在 21..120 之间）:
      其中两版不相等的组数: 239
      第一组不相等的 n: 51
   不取模在 n = 10000 时的位数: 2090 位
   取模后的值最多 10 位——两版差了 2080 位，在 n = 30 上却逐字相同
```

**四个数要一起看**：`0 / 58 / 58 / 0` 里的第一个 `0` 和最后一个 `0` 意思完全不同——
第一个是「同一个思路的参考解抓不到」（它错在同一处），最后一个才是「修好之后真的没错了」。
同理任务 2 的 `0 组 / 33 组`：**抓不到不是对拍器坏了，是生成器没喂到。**
任务 4 那句「两版差了 2080 位，在 n = 30 上却逐字相同」正是这一课的主题：
**样例过了，什么都没证明。**

留白版原样跑是不通过的（本机实测退出码 1、**57 条 FAIL 全部点名 TODO**、
不含 `TODO` 的 0 条）；参考解是 **80 PASS / 0 FAIL、退出码 0、连跑 3 次逐字节相同**。
五个任务文件两侧单跑都是退出码 0、0 处 `Traceback`、**行数逐行相同（16 / 17 / 7 / 15）**。
`solutions/0030-stress-test-and-review/` 里连 `tools.py` 与 `run_tests.py` 都有一份
（与任务目录逐字节相同），`py run_tests.py` 应当五层全过。

## 任务表 · 实验四（`0031-lab-04-spaced-repetition-drill/`）

这一课是**唯一一份「实验本身就是考核」的练习**：不是填空、不是补全一个小函数，而是
**限时 240 分钟、满分 360 分，自己决定做哪几道、放弃哪几道**。判的是**决策与表述**。

五道省赛难度的题，**全部做完要 470 分钟**（35 + 70 + 110 + 180 + 75），而这一场只有 240 分钟——
所以从第一分钟起它就不是「做完五道题」，而是「在 240 分钟里取舍」。这一课真正的答案在
`timeline.md`（限时记录）与 `explain.md`（讲解稿）里，不在 `answers/` 里。

| 题 | 算法族 | 来源考点 | 分值 | 估时 | 性价比 | 定位 |
| --- | --- | --- | --- | --- | --- | --- |
| p1 舞台高度 | 二分答案 | 第 22 课 | 30 | 35 | 0.86 | 入门题：第 16～26 课的标准算法，必须拿满 |
| p2 四边形合并 | 区间 DP（多一维「这段还剩几堆」） | 第 26 课 | 60 | 70 | 0.86 | 标准题：模板熟悉，值得做 |
| p3 数颜色 | 离线 + 树状数组（离散化） | 第 16 + 28 课 | 90 | 110 | 0.82 | 主力题：想得通但写得久，用来体验「时间被吃掉」 |
| p4 最长公共子串 | 二分 + 双模数哈希 | 第 16 + 22 课 | 100 | **180** | **0.56** | **故意做不完的超难题——正确玩法是「算过的放弃」** |
| p5 雨天迷宫 | 0-1 BFS（双端队列） | 第 21 课 | 80 | 75 | **1.07** | **性价比最高**：模板题，应该先做 |

**p4 是这道实验题眼**：$|S| = |T| = 10^5$，教科书式二维 DP 要 $10^{10}$ 个状态（一个状态 4 字节就是 40 GB），
从读题起这条路就堵死；正解思路不长，但哈希冲突、二分边界、双端点三处任一返工都要 30 分钟起。
**参考解把 p4 也写好了**（`reference/p4.py`）——两份答案放在一起，「会做」和「该做」的差别就摆在明面上。

| 交什么 | 交到哪 | 判什么 |
| --- | --- | --- |
| 五道题的答案 | `answers/p1.py` … `answers/p5.py` | `py score.py` 跑 30 组数据算分 |
| 限时解题记录 | `timeline.md` | `py check_timeline.py` |
| 讲解稿 | `explain.md` | `py check_timeline.py` |

记录的**六格**（每题都填，**没做出来的题也要填**）：读题用时 / 定下的算法（**要说数据范围**）/
写完时刻 / 自检做了什么 / 得分 / 丢分丢在哪。讲解稿的**四段**：解决什么问题 / 为什么正确（不变式）/
复杂度怎么推 / **多大的规模会淘汰它（必须带具体数字）**。第四段是这一课真正要判的东西。

### 实验四的期望输出形状

三条命令各管一段，判分按标签找行：

```text
$ py score.py            # 跑 answers/p1.py … p5.py，逐组比输出、算分（写 score.json）
总分：360 / 360          ← 参考解那一侧；留白版的骨架只 import sys、不输出，是 0 / 360
                         # 五题 × 6 组 = 30 组数据，题面与数据在 problems/pN/ 下

$ py check_timeline.py   # 查 timeline.md 与 explain.md
24 条 PASS、0 条 FAIL    ← 参考解那一侧；留白版是 2 条 PASS、21 条 FAIL

$ py run_tests.py        # 判分器自检（七层），维护用，学生不用跑
留白版     ：共 65 条 PASS、0 条 FAIL（退出码 1；另有 21 条「材料还没填」单独列出）
参考解那侧 ：共 62 条 PASS、0 条 FAIL（退出码 0）
```

两侧条数不同是正常的：留白版**没有 `reference/`**，有两层按「查不到」走另一条分支。
`run_tests.py` 里核对的是确定量——数据现算且每次一样、参考解 30 组全过、
`score.py` 抓得住写错的答案、`check_timeline.py` 抓得住写坏的材料（7 种形态）、
**留白版里没有泄漏参考解**、以及这一侧的材料确实还是「还没做」的样子。
**这一课没有任何基于耗时的断言**：题面给的是每题 10～25 秒的时限，落盘时只记录了参考解
最大数据组的实测秒数（p1 0.22 / p2 1.7 / p3 0.67 / p4 1.5 / p5 0.27 秒），一条都不参与判定。

几个要记住的确定量：

```text
满分与时长            360 分 / 240 分钟
五题估时合计          470 分钟（35 + 70 + 110 + 180 + 75）> 240，所以必须放弃至少一道
性价比（分值÷估时）   p5 1.07 > p1 0.86 = p2 0.86 > p3 0.82 > p4 0.56
应放弃的那道          p4 · 最长公共子串（100 分 / 估时 180 分钟）
参考解这一场的成绩    170 / 360
                      p1 30/30（28 分钟）· p5 80/80（35 分钟）· p2 60/60（70 分钟）
                      p3  0/90（65 分钟没写完，方案对、时间不够）· p4 0/100（主动放弃）
放弃的依据            做完前三道时是第 185 分钟，剩 55 分钟 < p4 估值 180 分钟
```

**这一场的教学结论不是「p4 太难」**：参考解把 p4 也写对了，它证明的是**「放弃」是一个可以算出来的决定**。
记录里那一句「预计 180 分钟 > 剩余 55 分钟」才是这一课要交的东西。
另外「把 p3 排得太靠后」才是真正的失分点——复盘那一节把这件事算清了（若按性价比重排能多拿多少分）。

**留白版原样跑是不通过的**（退出码 1）：`timeline.md` / `explain.md` 是**待填模板**
（85 处占位符），`answers/p1.py…p5.py` 是各 20 行的骨架（含 `main()` 与「待填」）。
脚手架本身 0 条 FAIL——那 21 条 FAIL 说的全是「材料还没填」，每条都点名是哪份材料、
哪一道题、缺哪一格或哪一段（形如「`记录 p3`：这几格空着没填——读题用时、定下的算法、写完时刻…」）。
**这 21 条用的是中文「待填」而不是英文字面 `TODO`**，判据是**点名了文件名与缺失项**——
据这次核对，「既无文件/材料名又无缺失项」的 FAIL 是 **0 条**。

这一课给的五道题与数据都是现算的（`test_data.py` 固定种子，`problems/pN/cases/` 就是算出来的那一份，
共 99 个文件、约 13 MB）。`solutions/0031-lab-04-spaced-repetition-drill/` 里连
`run_tests.py`、`check_timeline.py`、`test_data.py`、`score.py` 与两份模板都有一份，
**与任务目录逐字节相同**（`problems/` 整棵目录也逐字节相同）；那一侧独有的是 `reference/`
（五道题的参考解）与**填好的** `timeline.md`（162 行）/ `explain.md`（238 行）。
`run_tests.py` 一份大约 **21 秒**（留白版）/ **27 秒**（参考解那侧），`score.py` 跑完五道题约 8 秒。

## 任务表 · 0033（`0033-capstone-ai-tutor/`）

这一课把整门课收成一个能跑的作品：**题目文本进、带证据的记录出的五段流水线**。
它不像前面那些课一样「一题一练」，而是**一条链**——链上任何两段对不上，后面全白写。

```text
题目文本 ──①提取题意──▶ {title, constraints, ask}
        ──②推荐算法──▶ {candidates, reasons, picked}
        ──③写解法──▶ {code, entry, complexity}
        ──④自动验证──▶ {passed, evidence, failing_case}
        ──⑤出记录──▶ {problem, picked, passed, evidence, seed, rerun}
```

| 段 | 文件 | 要交的东西 | 这一段真正在教什么 |
| --- | --- | --- | --- |
| 契约表 + 第 4 段的契约 | `contracts.py` | `TABLE_ROWS`（五行，段号 1..5）/ `CONTRACTS`（五段）/ 契约检查器 | **先写契约再写实现**：契约不对时**抛异常**而不是交回 `False`，而且要说清**是哪个字段**。`passed` 那一格必须是 `is_bool` —— `True`/`False` 本身才算数，`1`/`0`/`'True'`/`'False'` 全拦住 |
| ① 提取题意 | `parse.py` | `parse_naive` / `parse_fenced` / `parse_balanced` / `parse_with_retry` | **模型输出不可信**，所以要三档解析 + 一层重试。四份预置输出里**「被截断」那一档三档都救不回来**（括号不闭合），只能交给重试——而且重试必须**带上 `retry=True` 与同一份提示词** |
| ② 推荐算法 | `parse.py` | 候选筛选 | 模型说什么不算数，**筛一遍**才算 |
| ③④⑤ 与整条链 | `pipeline.py` | `run_cases` / `check_contract` / `run_pipeline` / `show_verdict` | 每两段之间查一次契约；**结论必须是算出来的**；记录里要留**数据本身**而不是只留 seed |
| 模型那道缝 | `fake_model.py` | `call_model(prompt, retry=False)` | **整条链上唯一的联网点**。docstring 里留了换真 DeepSeek 调用的改法；判分全程用它，**不用 key、不联网** |

### 0033 的期望输出形状

判分分五层、**103 条检查**。两路证据缺一不可：跑脚本读它自己打印的行（按**标签**找行），
另起探针 `import` 学生的函数、用**判分自己造的数据**试（嵌套对象、字符串里带花括号、
全错的沙箱、`title → name` 的字段漂移）。**只写 `print` 不写实现拿不到 PASS。**

四个脚本单跑，两侧 **退出码 0、0 处 Traceback、打印行数逐行相同**：

```text
contracts.py   18 行
parse.py       21 行
fake_model.py   0 行
pipeline.py    30 行
```

`contracts.py` 与 `pipeline.py` 的行数是**固定的**：还没接上时每一格打占位（`（还没接上）`），
接上之后就是真值——**行数不许随进度变**，因为判分读的就是这几行。

这一课的高潮是最后那一段「类型漂移」：

```text
契约检查放过了它吗: False
契约检查怎么说漂移后那一格: 4 验证: 字段 passed 应为 bool，实际是 str
漂移之后输出里写的结论: 验证 通过
正确答案: 验证 未过
静默地当成「通过」了吗: True
```

```python
passed = 'False'          # 该是 True / False 本身
bool('False')             # → True，非空字符串在布尔语境里就是 True
```

不拦它，报告那一行会**静默地**写成「验证 通过」，而正确答案是「未过」——
**它不抛异常、不报错、也没人会发现，这正是它危险的地方。**

几个要记住的确定量：

```text
五段的段名（要逐字）   1 提取题意 / 2 推荐算法 / 3 写解法 / 4 验证 / 5 出记录
第一段调了几次模型     2（第一次交回被截断的那一份，第二次带 retry=True）
四份预置输出的成绩     干净 3 档都过 · 带围栏从第 2 档起 · 带前言只有第 3 档过 · 被截断 3 档都不行
五组数据与结论         0 0 0 / 0 0 1 / 2 1 0 都在；passed 是 [True, True, True, True, False]
第一个反例             第 4 组：算出来 18、期望 4
seed                   20260301
题目 / 算法族          拨钟问题 / 图的搜索（候选里还有「枚举」，代价更大所以没选）
```

**这一课一个耗时都不量**，所以不会出现计时的抖动。判分核对的全是确定量。

**留白版原样跑是不通过的**（退出码 1、`0 层通过、5 层还没过`、**29 PASS / 55 FAIL**，
**55 条 FAIL 每条都点明「→ 这一条指 `<文件>` TODO n（…）」，不含 TODO 的 0 条**）；
参考解是 **`5 层通过、0 层还没过`、103 PASS / 0 FAIL、退出码 0，连跑 3 次输出逐字节相同**
（输出按 LF 归一化后的 SHA-256 是 `345A9D8526FF8FB7…`）。

`solutions/0033-capstone-ai-tutor/` 里 `tools.py`、`fake_model.py`、`run_tests.py` 三份
**与任务目录逐字节相同**（判分第 5 层就用它们的 SHA-256 核对：`5E047339…` / `B76CE358…` / `6B0B0D4B…`）。
参考解那一侧独有的是 `README.md`（逐段讲解）与**填好的** `record_example.md` / `answer_example.md`。
**留白版没有那两份填好的样例**——`record.md` 与 `answer.md` 本身就是要交的东西，
提前看到答案等于抄；两份模板里的指针已经改成指往参考解那一侧。

## 卡壳顺序（先做前三步再来问）

1. **读错误信息**：`run_tests.py` 会把脚本报错的最后几行贴出来。`NameError` / `IndexError` /
   `UnboundLocalError` 通常就指在还没填的那一段；先看它指的那一行。
2. **自己跑一遍**：`py task1_lookup.py`（0003）或 `py task1_functions.py`（0004）单独跑，
   看它到底打印了什么——打出 `0.000000` 就是那一段还没量；0004 一行都不打印，就是 `solve` 还没接上。
   0007 同理：`cat sample_a1.in | py solve_a.py` 打出 `0` 就是求解还没接上，
   `scale_check.py` 两行的秒数都小到 `0.000000` 就是那两个函数还空着。
3. **看 FAIL 行**：`run_tests.py` 的 FAIL 后面已经写了缺哪一段、期望的量级或值是多少。
   0007 的 FAIL 还会点出「这一层指向哪一段」（第 2 层指输入解析、第 3 层指复杂度、
   第 4 层的探针指自测脚本、第 5 层指估算），顺着那一句改就行。
4. **再对线索**：
   - 0003：
     - 计时永远是「前后各取一次 `perf_counter()`、相减」，`t0` 在循环之前、`t1` 在循环之后，中间不夹别的代码。
     - 列表 `in` 要一个个比过去（目标取在末尾附近，每次几乎扫完整个列表）；集合与字典走哈希直接落位。
     - 空集合只能写 `set()`——`{}` 建的是空字典。
     - `deque` 的出队方法是 `popleft()`，不是 `pop()`（`pop()` 出的是右端）。
     - 结果对不上时先怀疑容器写错（集合版里还留着 `lst` / `append`）。
   - 0004：
     - 改写只改代码的组织方式、不改算法：负数归零留在 `read_n` 里，`odd_count` 就是原来那一行，
       只是把 `print` 换成 `return`；算出来的值交给 `show` 打印。
     - 必须先定义后调用；调用要带括号（只写 `odd_count` 是这个名字本身，一行都不执行）。
     - 默认值写在 `def` 那一行，**它在定义时就算好了**：`def show_default(arg=i)` 记下的是读到那一行时的 `i`，
       之后再改全局 `i` 也不影响它。
     - 默认为空容器写 `L=None` 加 `if L is None: L = []`；调用处给进来现成列表时要接着用，别丢掉。
     - 函数里改全局名字，函数体第一行先写 `global`；不写的话那个名字就成了局部的，
       赋值之前读它会报 `UnboundLocalError`。
     - 函数拿到的是列表的**引用**：就地改 `nums[i] = ...` 会改到调用处；不想改就先写 `nums = nums[:]`
       （复制一份要花正比于元素个数的时间）。
     - 任务 4 里两个函数只差那一行复制；「返回的列表对不对」和「调用处的列表变没变」是两件事，分开看。
     - 全程只用到这一课教的东西：推导式、`sorted`、`enumerate`、`zip`、f-string、`lambda` 都先不用。
   - 0005：
     - 任务 1 那十段是「同一个模式、不同收尾」：先把循环版每一段读一遍、说清它在算什么，
       再对着 `task1_rewrite.py` 开头的对照表找它该换成什么。最容易写反的两处是
       「数个数」（`sum(1 for …)`，每个满足条件的算 1）与「求和」（`sum(x for …)`）；
       以及 `any`（存在一个）与 `all`（一个反例都没有）。
     - 判分说某一行「打出 None」，就是那一段的 TODO 还是占位值；说「十行里有 N 段还没对上」，
       就从 FAIL 点到的编号一行行改。
     - 推导式里赋给目标的名字不会泄漏到外面（本课用「外面的 `y` 还是旧值」来验），
       循环版反而会把它留下——这是两者的差别，不是 bug。
     - 生成器第二次打出 0 是对的（第一次已经取空）；它没有 `len`、不能下标；
       `map`、`zip`、`enumerate` 同理，取完就空、不存在「重置」。
     - `zip` 长度不齐只会变短（不报错、也不补齐）；`enumerate` 默认从 0 起，要按题号数就写 `start=1`。
     - `sorted` 返回新表、`list.sort()` 返回 `None`：写成 `x = a.sort()` 之后 `x` 就是 `None`，
       再拿它取下标就报 `'NoneType' object is not subscriptable`。
     - `any([])` 是 `False`、`all([])` 是 `True`；用 `all` 检查「这批数据是不是都合法」时，
       空数据也会给 `True`，要按题目要求另外判空（`if not nums:`）。
     - `key` 用 `def` 写的命名函数（本课不用 `lambda`），也别去碰递归与 `itertools`。
   - 实验一（0007）：
     - **第 2 层「折行组」错，几乎一定是输入读的那一层**：`tests/a3.in` 打出 `2`（应是 `4`）
       就是 `a = list(map(int, input().split()))` 那种逐行读；`tests/b3.in` 报
       `ValueError: too many values to unpack` 就是 `n, m = map(int, input().split())`。
       改法是第 6 课那条规矩：`sys.stdin.read()` 一次读完 → `split()` 按空白切分 → 自己解析成数据结构。
     - **第 3 层「超过 2 秒还没跑完」是复杂度问题，不是写错了**：先把「循环要跑多少次」数出来。
       题目 A 用列表查重是 `n²/2` 次比较（10 万个数就是几十亿次），换成集合或字典就是 `O(n)`；
       第 3 层答案不对但没超时，才回去看解析与边界。同一个判断也在 `scale_check.py` 里量给你看。
     - **第 4 层「探针……仍然报 PASS」**：自测脚本必须真的起子进程跑 `solve_a.py`、拿标准输出与
       `.out` 逐字比。它在副本目录里跑，所以路径要按 `os.path.dirname(os.path.abspath(__file__))` 算；
       比之前先 `rstrip()` 每行、去掉末尾空行，否则 Windows 换行会变成假失败。
     - **第 5 层「预计值偏小」**：规模放大 10 倍，列表查重的比较次数涨约 100 倍（不是 10 倍）；
       `predicted = t_list * 100` 才是按平方级推的。
     - `IndexError: list index out of range` 指在 `int(tokens[0])`：`read_all()` 还没真的读进来
       （留白版是 `return ''`），token 表是空的。
     - 标准输出里多出「答案是：」这类行会让四组样例全部 FAIL：调试 `print` 用完就删，
       或者临时改成写 `sys.stderr`。
     - 列表里的字面量、下标都对但 `sample_b2` 打出 `10 2`：并列取最小没处理——
       键写成 `(-次数, 分数)`，排序后取第一条。
    - 0006：
      - **任务 1 的 `sample6.in` 打出 `[[1, 2, 3, 4], [5, 6], [7, 8]]`**：矩阵那一版按行切开了。
        题面只约定元素的个数与先后顺序，所以按空白读是按题面办事：先把 `n*m` 个数取成一段
        `vals`，再按 `m` 个一段切开。这两组是同一份数、只换了换行位置。
      - **任务 2 的改写版也打出 36**：改写后还在用 `input()`（或者 `text` 拿到了却没用）。
        从 `text.split()` 出发、只用 `vals`，两条排版就都会给出 78。给好的对照版
        `sum_rows_running` 打出 36 是**对的**，别去改它——那正是这一课要看的现象。
      - **任务 2 的「每行长度」是 `[3, 3, 3]`**：切片右端写成 `i*m + m - 1` 了。切片右端不包含，
        要取 `m` 个数得写 `(i + 1) * m`（写 `i * m + m` 等价）。
      - **任务 3 的 `06 转整数后最大值` 对不上**：`max(raw)` 在字符串上给的是 `9`，
        转成整数之后才是 `100`——这两行不是一个答案，别把两处写成同一个式子。
      - **任务 3 的 `07` 一行报错退出**：混着比的写法是 `'10' < 5`；用 `try` / `except TypeError`
        把它接住，`type(e).__name__` 拿到的就是 `TypeError`。别让异常跑出去。
      - **任务 4 的 `诊断 总和` 直接就是 78**：先把三行诊断打印补上（那时它是 54），再改切片——
        顺序反了就看不到「它不报错、只是偏小」这一步。判分不卡这个顺序，但这一步是任务的价值所在。
      - **任务 4 的 `原文 repr` 末尾少了 `\n`**：你用了 `splitlines()` 取第一行，它会把行尾的
        换行符去掉。按第一个换行符切、把 `\n` 留在左边这一行上，`repr` 才显示得出来。
      - **任务 5 的 `clean` 打出 `0`**：`int(input())` 那一句还没填（留白版是 `n = 0`）。
        另外 `clean` 里**不要**给 `input()` 加提示、也**不要**给 `print` 加前缀。
      - **任务 5 的 `dirty` 也被判成干净的**：这一版就是要犯那两个错——
        `input('请输入 N：')` 配 `print('答案是：', n * 2)`。
      - **任务 6 的探针说「有 3 组不对」**：`same_output` 用 `strip()` 把两边空白都抹掉了，
        于是「末尾多一个换行」与「行尾多一个空格」都分不出来。两边都 `splitlines()` 再比。
      - **任务 6 的 `05 搜两个关键词` 空着**：交回 `['input(', 'print(']` 这两个字符串。
    - 0009：
      - 任务 2 到 5 都 `import` 前面的任务文件（任务 3 要用任务 1、2 的函数），
        所以**五个文件要一起改、一起跑**；只填了任务 3、前面没填，它拿到的就是占位值。
        每个任务末尾那层 `if __name__ == '__main__':` 是给好的，删了的话 import 一次
        就会把前面任务的 `print` 重放一遍。
      - **任务 1 打出 0**：两层循环还没写。先确认 `s = 0` 写在 `for l` 里、`for r` 外——
        写在外面会被上一个左端点的累加带着走；再确认 `r` 是从 `l` 起的。
      - **任务 2 打出 `[0]`**：`build_pre` 还是占位值。它是 `pre = [0]` 后逐个
        `pre.append(pre[-1] + x)`，交回的表长应当是 `len(a) + 1`。
      - **任务 2 的「区间和公式 还没建好：表长 1」**：这一行是给好的保护——
        表没建好时下标会越界，它接住并告诉你表长是多少；表建对了这一行会变成 `4790`。
      - **任务 2 的答案偏小**：先看 `seen` 的初值是不是 `{0: 1}`（少了它，所有从数组开头算起的
        区间都漏掉），再看是不是先记后查了（写反会把空区间算进来）。
      - **任务 3 的「小数组 两版答案一致」打出 `True`**：期望是 `False`。打出 `True` 说明
        你的双指针版不是课件那一版（比如把 `l` 也交给 while、或者漏了末尾的 `s -= a[l]`）。
      - **任务 3 的错版没报 IndexError**：`count_window_broken` 要**只去掉** `r < n`
        （写成 `while s < S:`），其余原样。报 `IndexError` 才是对的——
        报别的异常、或者干脆打出一个数，都说明那一版写偏了。
      - **双指针在含负数的数组上给出与暴力相同的答案**：这不是「更好」，是写错了。
        课件那一版在含 0 或负数时**必然**漏解（本机实测：小数组 4 对 9、300 个数 4 对 106）。
        答案相同只有两种可能：要么你把双指针写成了别的（比如每轮把 `r` 重置回 `l`），
        要么那个数组其实没有 0 与负数。
      - **任务 4 的「第一个反例」打出 `None`**：`find_counterexample` 要么没写（占位值就是 `None`），
        要么把比较写反了。它找的是「双指针与**暴力**不同」的数组：`if w != b: return arr`。
      - **任务 4 的「全正数上三版始终一致」**：这一条期望 `True`，但留白版上它也算「一致」
        （三个版本都交回 0）。判分对此另加了依赖检查：先看「小数组三版答案」对不对，这一条才算数。
      - **任务 5 的三行秒数都是 `0.000000`**：`time_three` 还没接上 `tools.timed`。
        写成 `b, tb = timed(count_brute, a, S)`——它交回 `(答案, 秒数)`，
        你只要秒数那一个，`return (tb, tp, tw)`。
      - **任务 5 的「暴力翻倍只涨一点点」**：多半是把三个版本包在一次计时里量了。
        三个版本要**各量各的**：三次 `timed`、三次相减，中间不夹别的代码。
      - **「暴力只比双指针慢 X 倍」里 X 很小**：先确认两个版本的答案都对（对拍那一步过了吗），
        再看计时是不是按三个函数分开量的。这一条要的是两个数量级以上的差距，
        本机实测 400 倍上下——差距小到几十倍，通常是计时混在一起了。
      - 本课只用到第 1 到 8 课的东西，新学的就是「前缀和」与「双指针」两种走法本身：
        递归、`heapq`、`itertools`、`Counter` / `defaultdict`、`timeit.repeat`、`lambda` 都别用；
        栈与队列（第 10 课）、对撞指针（第 11 课）也还没学。
5. **对照参考解**：某一课的任务都过了，再打开 `solutions/0003-python-list-dict-cost/`、
   `solutions/0004-python-function-basics/`、`solutions/0005-python-comprehension-builtins/`、
   `solutions/0006-python-io-and-debug/`、`solutions/0007-lab-01-run-one-problem/`
   或 `solutions/0009-linear-structures-two-pointers/`。

## 做完之后

- **0003**：看完参考解，用一句话回答：这四个任务里，**哪一行代码决定了快慢**？
  （能说清「哪一行 → 什么复杂度 → 为什么」就算这一课练到位了。）
- **0004**：用一句话回答：只看 `read_n` 的**定义那一行**，看得出它动了哪些数据吗？
  再把任务 1 与任务 3 摆在一起看——要改「奇数个数怎么算」这一处逻辑，两种写法各要翻几个地方？
- **0005**：用一句话回答：这十段里有哪几段其实**不该**压成一行（跨轮次的状态、一个元素要产出好几样、
  `for` 与 `if` 叠了三层以上、打算反复调试）？再把任务 3 的 `01` 与 `04` 摆在一起——
  它俩打出的都是 0，一个为什么是「还没算」、另一个为什么是「已经空了」？
- **0006**：用一句话回答：任务 2 里，**哪一行决定了折行数据算不算得对**？
  再说一句：任务 1 与任务 2 都改了输入读法，为什么 `sample6.in` 这种「同一份数、只换换行位置」
  的数据，恰好是检验它的那把尺子？
- **实验一**：用一句话回答：这两份脚本里，**哪一行决定了题目 A 能不能跑完十万个数**？
  再说一句 `selfcheck.py` 与评测机做的是不是同一件事——它是后面「对拍验证」那个实验的起点。
- **0009**：用一句话回答：双指针的三个前提（元素全为正数、数组有序、题目问「和恰好等于 S」
  而不是「和不大于 S」）里，**哪一个在这道题上不成立**？再说一句：任务 5 那张表里，
  哪一列的涨法说明了暴力是平方级的？——能指着「翻倍涨四倍」那一列说出来，就算这一课练到位了。
- **0010**：用一句话回答：`pop(0)` 与 `popleft()` 都是「从前面拿走一个」，代价差在哪一步上？
  再回答：滑动窗口最大值里，**什么时候可以放心把队头扔掉、什么时候可以放心把队尾扔掉**？
- **实验二**：用一句话回答：如果对拍跑了一万次一次都没报错，是不是就说明候选解对了——
  **还差哪两件事**才算把这一份交出去？（一件与数据有关，一件与记录有关。）
- **0016**：用一句话回答：三个任务的「列表版」都是**对的**，为什么还要写字典版？
  再说一句：任务 4 里桶多了、冲突却没变少，这说明哈希表的快慢主要由**哪两件事**决定？
- **0017**：用一句话回答：为什么收集遍历结果要用**累加器**、而不能一路 `+` 拼接？
  再说一句：为什么量性能不能只测一种形状的树——平衡树与链状树差在哪一个量上？
- **0018**：用一句话回答：堆为什么能在对数时间取到最小（它**没有**把整个序列排好序，
  它是靠什么把「最小」一直留在 `h[0]` 的）？再说一句：k 远小于 n 时为什么不必排全序？
- **0021**：用一句话回答：求最少步数为什么必须用 BFS、而 visited 为什么要在**入队那一刻**就标记？
  再说一句：任务 4 里两版答案完全一样，代价却差四倍——多出来的那些入队次数是从哪来的？
- **0025**：用一句话回答：`knap01_1d_rev`（逆序）与 `knap_complete`（正序）循环体一字不差，
  凭什么一个是 0/1、一个是完全背包？再说一句：写错方向时答案**偏大**、区间 DP 写错顺序时答案
  **偏小**——这两个方向各自告诉你错在哪一类？
- **0026**：用一句话回答：为什么 `tails` 不是一条递增子序列，而区间 DP 又为什么**必须先算短区间**？
  再说一句：任务 4 那 137 组错解里，漏掉的是「前面的合并代价」——为什么区间越长漏得越多？
- **实验三**：用一句话回答：这个助手给出的结论，**凭什么**值得相信？
  再说一句：提示词里的格式约束、解析器的失败标记、以及把模型调用收成一道「缝」，
  这三件事各防的是哪一种错？