数位 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...