字典树 模板 struct TRIE { int nex100000, cnt; bool exist[100000]; // 该结点结尾的字符串是否存在 void insert(char* s, int l) // 插入字符串 { int p = 0; for (int i = 0; i < l; i++) { int c = s[i] - 'a'; if (!nexp) nexp = ++cnt; // 如果没有，就添加结点 p = nexp; } exist[p] ...

图 简介 相关概念 图 · Graph 是一个二元组 $G \ = \ (V(G), \ E(G))$。其中 $V(G)$ 是非空集，称为 点集 · Vertex set，对于 V 中的每个元素，我们称其为 顶点 · Vertex 或 节点 · Node，简称 点；$E(G)$ 为 $V(G)$ 各结点之间边的集合，称为 边集 · Edge set。 常用 $G \ = \ (V, \ E)$ 表示图。 当 V, E 都是有限集合时，称 G 为 有限图。 当 V 或 E 是无限集合时，称 G 为 *无限图...

AC 自动机 简介 AC 自动机是以 Trie 的结构为基础，结合 KMP 的思想建立的。 简单来说，建立一个 AC 自动机有两个步骤： 基础的 Trie 结构：将所有的模式串构成一棵 Trie。 KMP 的思想：对 Trie 树上所有的结点构造失配指针。 然后就可以利用它进行多模式匹配了。 构建字典树 AC 自动机在初始时会将若干个模式串丢到一个 Trie 里，然后在 Trie 上建立 AC 自动机。这个 Trie 就是普通的 Trie，该怎么建怎么建。 这里需要仔细解释一下 Trie 的结点的含义，尽管这很小儿科，但在之后的理解中极其重要。T...

MathJax 语法 基本 行内公式（Inline）$...$ 单独公式（Display）$$...$$ 运算符号 | 符号 | 命令 | | -------- | -------- | | $+$ | + | | $-$ | - | | $\times$ | \times | | $\div$ | \div | | $\cdot$ | \cdot | | $\cdots$ | \cdots | | $\pm$ | \pm | | ...

快速幂 简介 快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 $O(log \ n)$ 的时间内计算 $a^{n}$ 的小技巧，而暴力的计算需要 $O(n)$ 的时间。而这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。其中显然的是它可以应用于模意义下取幂、矩阵幂等运算，我们接下来会讨论。 算法 计算 a 的 n 次方表示将 n 个 a 乘在一起： $a^{n} \ = a \ \times \ a \ \times \ \cdots \ \times \ a$ （n 个 a） 然而当 a, n 太大的...

树 存储 邻接表 对于无根树：为每个结点开辟一个线性列表，记录所有与之相连的结点。 std::vector adj[N]; 对于有根树： 方法一：若给定的是无向图，则仍可以上述形式存储。下文将介绍如何区分结点的上下关系。 方法二：若输入数据能够确保结点的上下关系，则可以利用这个信息。为每个结点开辟一个线性列表，记录其所有子结点；若有需要，还可在另一个数组中记录其父结点。 std::vector children[N]; int parent[N]; ...

DP 基础 DP 最长公共子串 特点 连续 思路 动态转移方程 if (a[i] == b[j]) dpi = dpi-1 + 1; else dpi = 0; 模板 #define _CRTSECURE_NOWARNINGS #pragma warning(disable:4996) #include #include #include #include #include #inclu...

Vim What is Vim? Vim is a greatly improved version of the good old UNIX editor Vi. Many new features have been added: multi-level undo, syntax highlighting, command line history, on-line help, spell checking, filename completion, block operations, script language, etc. There is also a Graph...

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为...