1字符串哈希·概念
用哈希比较两个字符串是否相等，时间大约是多少？
算法进阶 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2哈希·多项式
逐字符计算哈希的递推式是什么样？
3哈希·子串哈希
取子串哈希的思想和哪种预处理技巧类似？
4哈希·应用
为降低哈希误判概率，常用什么办法？
5字符串·小结
“统计有多少单词以 'ab' 开头”，用哪种工具最合适？
6Floyd·概念
Floyd 求的是单源最短路还是任意两点最短路？
7Floyd·三重循环
Floyd 三重循环里，代表“中转点”的循环变量放在第几层？
8Floyd·中转直觉
Floyd 中把 k 放在内层循环会有什么问题？
9Bellman-Ford
n 个点的图，Bellman-Ford 最多需要松弛几轮？
10SPFA·概念
SPFA 相比朴素 Bellman-Ford 优化了什么？
第 1 页 · 背面（答案）
参考答案（家长）：h=(h*base+s[i])%mod。
参考答案（家长）：O(1)（只比一个整数）。
参考答案（家长）：双哈希（用两组 base/模数，都相等才算相等）。
参考答案（家长）：前缀和（用前缀哈希相减得到区间）。
参考答案（家长）：任意两点之间（多源）的最短路。
参考答案（家长）：Trie（前缀统计）。
参考答案（家长）：中转点“逐层放开”的顺序被打乱，结果可能不正确。
参考答案（家长）：最外层（k 在最外）。
参考答案（家长）：只把距离被更新的点入队处理，避免每轮扫全部边。
参考答案（家长）：n-1 轮。
第 2 页 · 正面（题目）
11SPFA·实现
inq[] 数组在 SPFA 里起什么作用？
12判负环直觉
SPFA 中怎样的迹象说明图里有负环？
13Prim·概念
Prim 每一步选择怎样的一条边？
14Prim·过程
Prim 里 dis[v] 表示的是什么？
15Prim与Kruskal
边很少的稀疏图，一般更适合用哪种算法？
16欧拉路·概念
欧拉路要求每条边经过几次？
17欧拉路·条件
无向图能一笔画成回路，奇度点应有几个？
18欧拉回路直觉
欧拉回路里，每个点的度数为什么必须是偶数？
19二分图·概念
二分图中，同一组内的两个点之间会有边吗？
20二分图·判定
染色时发现相邻两点同色，说明这个图怎样？
第 2 页 · 背面（答案）
参考答案（家长）：某个点的入队次数超过 n（点数），即存在负环。
参考答案（家长）：标记某点是否已在队列中，避免重复入队。
参考答案（家长）：未选点 v 到当前已生成树的最小边权。
参考答案（家长）：连接“已选点集”与“未选点”之间、权值最小的边。
参考答案（家长）：恰好一次。
参考答案（家长）：Kruskal（按边排序＋并查集）。
参考答案（家长）：每次进一个点就要出一次，边成对使用，故度数为偶。
参考答案（家长）：0 个（所有点度数都是偶数）。
参考答案（家长）：不是二分图（存在奇环）。
参考答案（家长）：不会，边只连接两组之间的点。
第 3 页 · 正面（题目）
21二分图·匹配
一个“匹配”里，同一个点最多被几条选中的边使用？
22LCA·概念
若 u 本身就是 v 的祖先，那么 LCA(u,v) 是谁？
23LCA·倍增
up[u][k] 表示 u 向上跳多少步的祖先？
24LCA·求距离
树上 u、v 距离公式里，为什么 dep[LCA] 要乘 2 再减？
25图论·小结
“求图中任意两点间最短路”，点数只有几百，用哪个算法最省事？
26拓扑排序·Kahn
Kahn 算法一开始把哪些点入队？
27DAG上DP·概念
DAG 上 DP 一般要按什么顺序处理结点？
28DAG·最长路
为什么最长路问题一般要求图是 DAG（无环）？
29DAG·路径计数
DAG 路径计数里，起点的 cnt 初值设为多少？
30进阶总复习
给“课程先修安排”和“树上两点距离”各选一个最合适的算法。
第 3 页 · 背面（答案）
参考答案（家长）：u 自己（最近公共祖先就是 u）。
参考答案（家长）：一条（匹配的边互不共用端点）。
参考答案（家长）：u、v 到根都各走了一遍 LCA 以上的路，重复算了两次，需减去。
参考答案（家长）：2^k 步（k=0 就是父亲）。
参考答案（家长）：所有入度为 0（没有前驱）的点。
参考答案（家长）：Floyd（三重循环，多源最短路）。
参考答案（家长）：有环时可绕环无限增长，最长路无意义/不收敛。
参考答案（家长）：拓扑序（保证前驱先于后继被处理）。
参考答案（家长）：课程先修用拓扑排序（DAG）；树上两点距离用 LCA。
参考答案（家长）：1（从起点到自身算作一条路径）。