1 教学目标
- 会写一个随机数据生成器, 并且知道为什么要控制数据规模
- 会用 01 序列模板 (
b[dep]试 0/1 的 dfs) 写一个"宁慢勿错"的暴力, 作为对拍标准答案 - 会写 / 会读一个最小可用的对拍脚本 (编译 + 循环 + diff + 保留现场)
- 亲手用一个反例证伪"按开始时间排序"的错误贪心
- 会用交换论证说明"按结束时间排序"为什么正确
- 明确区分: 对拍能发现错误, 不能证明正确
2 前置知识
- 01 序列模板:
dfs(dep)里for(i = 0..1) { b[dep] = i; dfs(dep+1); } - 贪心的基本形式 (排序 + 一遍扫描)
- 命令行:
g++、重定向、diff、chmod +x
3 暴力为什么用 01 序列
| 写法 | 枚举对象 | 合法性检查 | 适合 |
|---|---|---|---|
| 01 序列 (本文) | 长度为 n 的 01 序列 b[1..n] 的全部 |
到叶子后两两判重叠 | 零剪枝, 一眼看出"没漏方案" |
| DFS 选/不选 (延伸) | 递归二叉树叶子 | 边搜边判 start >= last |
能剪枝, 可顶到大一点的 |
用 01 序列不是因为它更快, 而是因为它最难写错: 没有回溯、没有排序假设、没有剪枝条件,
for(i = 0..1) { b[dep] = i; dfs(dep+1); } 一个不漏。标准答案要的就是这个。
和「01 序列」文章的模板逐行对得上，只把「输出 b[]」换成「check() + 统计场数」。
关键点是语义必须和题意一致: P1803 允许首尾相接, 所以冲突判定写 L[i] < R[j] && L[j] < R[i]
(相等不算冲突)。写成 <= 会把合法方案误判成冲突, 暴力答案偏小, 于是错误贪心反而显得对。
4 建议课堂流程
| 环节 | 时间 | 教师动作 | 学生动作 |
|---|---|---|---|
| 讲模型 | 5 min | 写线段覆盖模型, 抛出两个贪心候选 | 判断哪个对 |
| 写代码 | 12 min | 给出四个文件, 只讲 gen 和 check 的关键点 | 抄写并跑通 |
| 找反例 | 10 min | 不告诉学生贪心是错的 | 看 diff 报错, 读反例 |
| 改贪心 | 5 min | 引导不变量: 影响后续的只有结束时间 | 改排序关键字, 重跑 |
| 收尾提问 | 5 min | 提三个问题 | 讨论 |
5 常见卡点
- 假通过: 编译失败后脚本继续用旧可执行文件对拍 → 必须
|| exit 1 - 只对拍一次: 手工输入一次相等就以为对了 → 必须循环上百次
- 暴力写错: 标准答案本身不保证正确 → 报错时先核对暴力与题意
- 语义不统一: 把首尾相接当冲突 → 标准答案偏小, 对拍会"假通过"
- 数据太大:
n = 20时 01 序列要跑→ 生成器控制在 n <= 8 - 分布偏差:
rand()取值少 /srand(time(0))秒级种子 → 用mt19937 diff尾随空格 / 换行差异: 用diff -b, 或者统一输出格式
6 课堂提问与参考答案
- 为什么暴力程序可以当标准答案? 必须满足什么条件?
- 本身正确; 可运行 (规模小); 输出格式与被测程序一致。
- 为什么生成器要生成小数据?
还能对拍吗? - 暴力跑不完; 大数据只能换成已验证的另一个算法互拍, 或只做小数据验证。
- 对拍 1000 组没发现错误, 能说算法一定正确吗?
- 不能, 只能说没找到反例; 正确性仍需证明。
7 课后延伸
- 把同一套流程套到 P2240 (部分背包) 或 P1223 (排队接水) 上
- 让学生故意写出第三种错误贪心 (按区间长度排序), 再对拍找到反例
- 把 01 序列暴力改写成二进制 mask 子集枚举 (子集枚举 文章写法), 体会同一枚举的两种实现
- 加入
timeout与ulimit, 观察 TLE / RE 类型的对拍