KMP 问题引入 给定 2 个字符串 text 和 pattern，在 text 中寻找是否存在 pattern 这个子串（连续） 传统方法 · 暴力 做法 从第一位开始，对两个字符串进行逐位比对， 不相等则从下一位开始逐位比对 复杂度 · O(mn) 简介 KMP 算法是一种改进的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称 KMP 算法）。KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目...

计算几何 基础 高精度圆周率 const double pi = acos(-1.0); 偏差值 const double eps = 1e-8; sgn int sgn(double x) // 判断x是否等于0 { if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; } dcmp int dcmp(double x, double y) // 比较两个浮点数，0为相等，-1为...

博弈论 巴什博弈 简介 一堆物品有 n 个，两个人轮流从这堆物品中取物，规定每次可以取走 1 ~ m 个，最后取光者得胜。 解法 显然，如果 n = m + 1，那么由于一次最多只能取 m 个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果 n = (m + 1) r + s，（r 为任意自然数，s ≤ m），那么先取者要拿走 s 个物品，如果后取者拿走 k(≤ m) 个，那么先取者再拿走 m + 1 - k 个，结果剩下 (m + 1)(r - 1) 个，以后保持这样的取法，那么先取者肯定获胜。...

LCA 定义 对于有根树 T 的两个结点 u、v，最近公共祖先 LCA(T, u, v) 表示一个结点 x，满足 x 是 u 和 v 的祖先且 x 的深度尽可能大。在这里，一个节点也可以是它自己的祖先。 ——百度百科 记某点集 $S \ = \ v_{1}, \ v_{2}, \ \cdots, \ v_{n}$ 的最近公共祖先为 $LCA(v_{1}, \ v_{2}, \ \cdots, \ v_{n})$ 或 $LCA(S)$ 性质 $LCA (u) \ = \ u$； u 是 v 的祖先，当且仅当 $LCA(u, \ v) \ = ...

数论 素数 简介 一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数 1既不是质数也不是合数 判断方法 暴力 · $O(\frac{n}{2})$ bool isPrime(a) { if (a < 2) return 0; for (int i = 2; i * i < a; ++i) if (!(a % i)) return 0; return 1; } Miller-Rabin 素性测试 · $ O(k \ log^{3}n)$ ...

背包 背包问题 定义 背包问题 (Knapsack problem) 是一种组合优化的 NP 完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。 ——百度百科 分类 01 背包：有 N 件物品和一个容量为 V 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。每样物品可取1件 完全背包：有 N 种物品和一个容量为 V 的背包，每种物品都有 无限 件可用。第 ...

最小生成树 定义 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 ——百度百科 Kruskal 思路 用贪心的思想，把所有的边从短到长排序，从最短的边开始判断，如果连接的两个点不是已经联通的，那就把这条边连起来。如果已经联通，则忽略这条边。 用并查集维护所有的点，联通的点在同一集合，从而判断点是否联通。 模板 #define _CRTSECURE_NOWARNINGS #pragma warning(disable:4996) #include...

最短路 定义 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 ——百度百科 名词解释 Chain · 链：一个点和边的交错序列 $v_0 - e_1 - v_1 - e_2 - v_2 - \cdots - e_k - v_k$ Trail · 迹：对于一条路径 $w$，若$e_1, e_2, \cdots, e_k$ 两两互不相同，则 $w$ 是一条迹 Path · 路径：对于一条迹 $w$，除...

基础 DP 斐波那契数列 斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 即： an = 1 (n = 1 or n = 2) an = an-1 + an-2 (n >= 3) 求斐波那契的第 n 项 递归 思路 找到了其中的 最优子结构（递归公式）：f(n) = f(n - 1) + f(n - 2) 实现 long long func(int n) { if (n...

线段树 问题引入 假设需要反复对一个数组 a[] 进行以下两个操作： Query · 求和 对 a[l] ~ a[r] 求和 Update · 修改 将 a[idx] 的值修改为 val 则有如下解决办法： 朴素做法 Build for (int i = 1; i <= n; i++) scanf ("%d", &a[i]); Query for (int i = l; i <= r; i++) sum += a[i]; O(n) Update a[idx] = val; O(1) ...