数位 DP 简介 给定区间 [L, R]，求该区间中符合某种条件的数的个数 与数的大小无关，与数的每一位的组成有关 本质：搜索 + 记忆化 用 f[n] 记录 [0, n] 之间满足条件的书的个数，结果：f[R] - f[L - 1] HDU 2089 · 不要 62 Description 给定两个数 L, R，计算 [L, R] 中数位上没有出现 4 或 62（ 连续）的数的个数 ...

归并排序 归并排序 · Merge Sort，是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法 · Divide and Conquer 的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并操作 归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。 如：设有数列 { 6, 202, 100, 301, 38, 8, 1 } 初始状态：6, 202, 100, 301, 38, 8, 1 第一次归并后：{ 6, 202 }, { 1...

字典树 模板 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...