最后更新：2022-05-19
ACM的各种算法及其优化的核心：去除重复和不必要的计算。
各种搜索的核心：如何以特定顺序不重复不遗漏地扫一遍。
广度优先搜索（BFS）：由近及远的顺序。
深度优先搜索（DFS）：一条路走到头，走到死路再回头走另一条。
DLX：在DFS的基础上，不用“标记”来表示一条路走没走过，而是用链表来保存没走过的状态。优化的地方在于不用“看一下”是否被标记。
动态规划：以存代算，算过的结果存下来，需要的时候不用再算一遍。难点在于如何标识“这个问题已经算过”，以及计算的顺序。
Dijkstra最短路：本质上是BFS，由近及远找目标。 单调队列：干掉不可能成为答案的值，例如一个数组里想求每个数左边3个数中最大的那个，如果a[i]比a[i+1]小，那么a[i]永远不会是任何位置的答案，可以删掉。
O(nlgn)的最长不降子序列：核心就是单调队列。
KMP：重用字串自身的信息。方法是先对子串t预处理，建立一个数组存“下一跳”的信息，如果t[0...i-1]都匹配，t[i]不匹配，可以直接跳到下一个匹配位置。例如母串p是"abcdefg",字串t是"abd"。用"abc"和abd"匹配的时候，可发现c和d匹配不上，这时不需要再比较"bcd"和"abd"是否匹配，因为母串的"b"和字串的"a"必然不匹配。可以直接跳到"cde"和"abd"进行匹配。
Trie树：存很多字符串的时候合并相同前缀。
AC自动机：把KMP的思想扩展到Trie树上。
假设一个集合里总共有100人。其中
| 长发(A) | 短发(B) | 总计 | |
|---|---|---|---|
| 男(X) | 5 | 55 | 60 |
| 女(Y) | 30 | 10 | 40 |
| 总计 | 35 | 65 |
全概率：原因推结果。如果随机抽一人，求是长发P(A)的概率。
假设已知男人中长发的概率$P(A|X) = \frac{5}{60}$，男人的概率$P(X) = \frac{60}{100}$，女人中长发的概率$P(A | Y) = \frac{30}{40}$，女人的概率$P(Y) = \frac{40}{100}$，则
$$ P(A) = P(A |X) * P(X) + P(A|Y) * P(Y) = \frac{5}{60} * \frac{60}{100} + \frac{30}{40} * \frac{40}{100} = \frac{35}{100} $$
贝叶斯：结果推原因。随机抽一人，已知抽到一个男人，求他是长发的概率。