1状态压缩动规
为什么 n 不能大？
计算机基础 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2数位动规
为什么要记"是否贴着上界"？
3概率动规
为什么期望常倒推？
4动规优化：单调队列
这能把复杂度从多少降到多少？
5动规优化：斜率优化
它适用于什么形式的转移？
6图论：最短路算法总览
什么时候必须用 Bellman-Ford？
7Dijkstra 为什么怕负边
举一个反例。
8Bellman-Ford 与负环
为什么恰好是 n-1 轮？
9Floyd 的本质
为什么中转点必须在最外层？
10差分约束
这为什么可行？
第 1 页 · 背面（答案）
参考答案（家长）：贴着时这一位的取值受限，不贴着时可以随便取。
参考答案（家长）：状态数是 2 的 n 次方，n 大了爆炸。
参考答案（家长）：从 n 乘 k 降到 n。
参考答案（家长）：终点的期望已知为 0，从已知往回推更自然。
参考答案（家长）：有负权边时，Dijkstra 会出错。
参考答案（家长）：含两个下标乘积项、能拆成斜率与截距的形式。
参考答案（家长）：无负环时最短路最多经过 n-1 条边。
参考答案（家长）：绕远路经过一条很负的边，总长反而更小。
参考答案（家长）：不等式的形式和最短路的松弛条件完全一致。
参考答案（家长）：它是动规的阶段，顺序错了会漏解。
第 2 页 · 正面（题目）
11最小生成树的两种算法
它们的复杂度各是多少？
12割的性质
这个性质怎么证？
13强连通分量
缩点后的图是什么结构？
14割点与桥
这和系统设计的什么概念对应？
15二分图判定
什么图一定不是二分图？
16二分图最大匹配
什么叫增广路？
17网络流的基本概念
流量守恒是什么意思？
18最大流最小割定理
它有什么实际含义？
19网络流建模
二分图匹配怎么转成网络流？
20字符串：KMP
next 数组的含义是什么？
第 2 页 · 背面（答案）
参考答案（家长）：交换论证 —— 换上这条边不会让总权变大。
参考答案（家长）：Kruskal 是 E log E，Prim 用堆是 E log V。
参考答案（家长）：单点故障。
参考答案（家长）：有向无环图，可以在上面跑拓扑排序和动规。
参考答案（家长）：从未匹配点出发、交替走非匹配边和匹配边，到另一个未匹配点。
参考答案（家长）：含奇数长度环的图。
参考答案（家长）：瓶颈在哪，最大能力就由哪里决定。
参考答案（家长）：除源汇外，每点流入等于流出。
参考答案（家长）：每个前缀的最长相等真前后缀长度。
参考答案（家长）：加源汇，源连左部、右部连汇，容量全设为 1。
第 3 页 · 正面（题目）
21字符串哈希
怎么降低冲突概率？
22字典树
它的空间代价怎么样？
23AC 自动机
它相当于什么的多模式版本？
24后缀数组
它能解决什么问题？
25NP 是什么
数独属于这类吗？
26P 与 NP
如果 P 等于 NP，会怎样？
27NP 完全
举两个 NP 完全问题。
28归约
归约证明了什么方向？
29遇到 NP 难怎么办
旅行商问题实际中怎么处理？
30近似算法
2 倍近似是什么意思？
第 3 页 · 背面（答案）
参考答案（家长）：较大，每个节点要存所有可能的子节点指针。
参考答案（家长）：用大质数模数，或者用双哈希。
参考答案（家长）：最长重复子串、两串最长公共子串等。
参考答案（家长）：KMP 的多模式串推广。
参考答案（家长）：现有的很多加密体系会失效。
参考答案（家长）：属于，验证一个填好的答案很快，求解可能很慢。
参考答案（家长）：证明 B 至少和 A 一样难。
参考答案（家长）：如布尔可满足性、旅行商的判定版本、图着色。
参考答案（家长）：结果最多是最优解的两倍。
参考答案（家长）：用近似算法或启发式，求足够好而非最优。