1启发式搜索
估价高估了会怎样？
计算机基础 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2剪枝
常见的剪枝有哪几类？
3迭代加深
重复搜索浪费大吗？
4随机化算法
随机化的代价是什么？
5在线算法
缓存替换是在线问题吗？
6算法正确性证明：循环不变量
给冒泡排序找一个循环不变量。
7证明终止性
二分查找的这个量是什么？
8综合：设计一个算法（一）
策略是什么？
9综合：证明它（二）
写出完整的证明思路。
10综合：实现与验证（三）
对拍发现不一致怎么办？
第 1 页 · 背面（答案）
参考答案（家长）：可行性剪枝、最优性剪枝、对称性去重。
参考答案（家长）：可能过早放弃真正的最优路径。
参考答案（家长）：可能有极小概率出错或很慢，但可以控制到可忽略。
参考答案（家长）：不大，最后一层的节点数通常远超之前所有层之和。
参考答案（家长）：每轮结束后，末尾若干个已是最大且有序。
参考答案（家长）：是，不知道未来会访问什么就得先决定换谁。
参考答案（家长）：按右端点排序，每次在最左的右端点放点。
参考答案（家长）：区间长度。
参考答案（家长）：缩小数据规模找出最小反例，再定位问题。
参考答案（家长）：最优解中第一个点可以右移到最早的右端点而不变差。
第 2 页 · 正面（题目）
11对拍的价值
为什么要随机小数据？
12综合练习一
想出线性做法。
13综合练习二
想出线性做法。
14综合练习三
这是什么问题？
15综合练习四
想出策略。
16综合练习五
写出状态与转移。
17算法选择的判断流程
n 是一百万，能接受什么复杂度？
18从数据规模反推算法
把这张对照表记下来。
19算法自查（一）
写下你的答案。
20算法自查（二）
写下你的答案，每类配一道题。
第 2 页 · 背面（答案）
参考答案（家长）：全为正数时双指针滑动窗口；有负数则要用前缀和加数据结构。
参考答案（家长）：小数据出错时人能手工看明白哪里错了。
参考答案（家长）：拓扑排序，能排出来当且仅当无环。
参考答案（家长）：两次遍历，或一次树形动规维护每点向下的最长与次长。
参考答案（家长）：二维动规，转移取增删改三种的最小值加一。
参考答案（家长）：按收益从大到小贪心，用并查集找最晚可用时刻。
参考答案（家长）：这是考场上最快的思路收敛工具。
参考答案（家长）：大致到 n log n，平方就太慢了。
参考答案（家长）：线性、区间、树形、状压、数位。
参考答案（家长）：能说清说明理解而非死记。
第 3 页 · 正面（题目）
21算法自查（三）
写下你的答案。
22这批课在考研里的位置
整理一份你自己的算法知识树。
23阶段小结
回顾这批课，你最大的变化是什么？
24计算理论要回答什么
你觉得有计算机永远算不出的问题吗？
25字母表与串
二进制字母表上"所有偶数长度的串"是一个语言吗？
26有限状态自动机
设计一个自动机，识别以 1 结尾的二进制串。
27自动机能做什么
登录流程算状态机吗？
28确定与非确定
既然能力相同，非确定型有什么用？
29子集构造法
n 个状态最多变成多少个？
30正则表达式
写一个匹配"若干个 a 后跟至少一个 b"的正则。
第 3 页 · 背面（答案）
参考答案（家长）：按"分析方法—算法族—典型题"三层组织最清晰。
参考答案（家长）：搜索、近似、利用特殊结构。
参考答案（家长）：有，而且已经被严格证明了。
参考答案（家长）：常见的是"开始先问能不能证明它对"。
参考答案（家长）：两个状态，读到 1 进接受态，读到 0 回非接受态。
参考答案（家长）：是，语言就是符合某规则的串的集合。
参考答案（家长）：设计起来简单得多，再机械转成确定型。
参考答案（家长）：算，未登录、验证中、已登录是几个状态。
参考答案（家长）：a 星号后跟 b 加号。
参考答案（家长）：2 的 n 次方个。