一个Oier

引入 当我们需要维护很多字符串，并支持下面这类操作时： 插入一个字符串 查询某个字符串是否出现过 查询某个字符串是不是某些字符串的前缀 统计以某个前缀开头的字符串个数 如果直接用 std::set 或 std::map 当然也能做，但有时候我们更需要一个专门处理字符串前缀的信息结构。 这就是 Trie，也叫字典树。 它本质上是一棵树，每条边表示一个字符，从根到某个节点的一条路径，就对应一个字符串前缀。 基本思想 假设只处理小写字母，那么每个节点最多有 26 个儿子，分别表示字符 'a' 到 'z'。 从根节点出发： 插入字符串时，按字符一个一个往下走 如果某条边不存在，就新建节点 最后在字符串结尾位置打个标记，表示这里是某个字符串的结尾 例如插入： abc abd bcd 那么根节点会先分出 'a' 和 'b' 两条边。 其中 abc 和 abd 会共享前缀 ab，这就是 Trie 的意义：把公共前缀合并起来。 数组实现 竞赛里最常见的写法是数组实现。 12int trie[N][26], tot;bool ed[N]; 含义如下： trie[p][c] 表示节点...

引入 有这样一类问题：维护一个长度为 n 的序列，需要支持两种操作： 单点修改某个位置的值。 查询一个前缀和，或者区间和。 如果每次修改后都重新求和，复杂度会很难看。朴素做法单次查询是 O(n)，如果操作很多就会超时。 这时候就需要 树状数组（Binary Indexed Tree，简称 BIT）。 它可以在 O(log n) 的时间内完成单点修改和前缀和查询，代码短，常数也小，是竞赛里非常常见的数据结构。 lowbit 树状数组最核心的东西就是 lowbit。 123int lowbit(int x) { return x & -x;} lowbit(x) 表示 x 的二进制表示中，最低位的 1 以及它所代表的值。 例如： lowbit(6) = 2，因为 6 = (110)2 lowbit(8) = 8，因为 8 = (1000)2 lowbit(12) = 4，因为 12 = (1100)2 这个东西决定了树状数组中每个位置管辖的区间长度。 基本思想 设树状数组数组为 c[i]，它维护一段区间和： 也就是说，c[i] 存的是一个以 i 为右端点，长度为...

基本形式 两个集合 对于有限集合 A, B，有 |A ∪ B| = |A| + |B| − |A ∩ B| 三个集合 对于有限集合 A, B, C，有 |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C| 一般形式 对于有限集合 A1, A2, …, An，有 也可以写成 证明 证明 考虑任意一个元素 ，设 x 恰好属于 Ai1, Ai2, …, Aim（m ≥ 1）。 在左边，x 被计数了 1 次。 在右边，x 被计数的次数为 由二项式定理可知 故 因此每个元素在右边也恰好被计数 1 次，左右两边相等。 证毕。 补集形式 在实际应用中，正面计算 往往不太方便。更常见的是已知全集 U，通过容斥原理求不属于任何一个 Ai 的元素个数。 展开即得 其中 S = ⌀ 时 |⋂i ∈ SAi| = |U|。 这个形式又被称为容斥原理的对偶形式，在”至少”与”恰好”之间的转换中非常好用。 例题 不定方程非负整数解计数 例题：洛谷 P2167 [SDOI2009]...

积性函数 定义 若函数 f(n) 满足对于任意 a ⊥ b，有 f(ab) = f(a) ⋅ f(b)，则称 f 为积性函数。 若对于任意 a, b，均有 f(ab) = f(a) ⋅ f(b)，则称 f 为完全积性函数。 常见积性函数 恒等函数 I(n) = 1。 单位函数 ϵ(n) = [n = 1]。 欧拉函数 。 约数个数 d(n) = ∑i ∣ n1。 约数和 σ(n) = ∑i ∣ ni。 性质 若 f 为积性函数，n = ∏piαi，则 f(n) = ∏f(piαi)。 证明 对不同质因子的个数使用数学归纳法。 当 k = 1 时，显然成立。 假设 k = m 时成立，当 k = m + 1 时，设 ，pm + 1αm + 1，显然 n′ ⊥ pm + 1αm + 1，那么 证毕。 由此可知，只需求出 f(pk) 即可求出任意 f(n)。 莫比乌斯函数 定义 莫比乌斯函数 μ(n) 定义如下： 即无平方因子否则（即有平方因子，存在） 性质 ∑d ∣ nμ(d) = [n = 1] 即 ∑d ∣ nμ(d) = ϵ(n) 证明 当 n = 1...

引入 二分查找大家都很熟悉。但二分答案是一个更强大的思想：当答案具有单调性时，可以二分答案的值，然后通过一个判定函数 check 来验证该值是否可行。 具体地，如果问题满足： 答案在一个范围 [l, r] 内。 存在一个阈值 x*，使得 ∀ x ≤ x* 可行，∀ x > x* 不可行（或者反过来）。 那么就可以二分这个阈值。 基本模板 求最大的满足条件的值 “答案越小越容易满足”，即  ≤ x* 可行， > x* 不可行。 1234567int l = L, r = R; // 答案范围while (l + 1 != r) { int mid = l + r >> 1; if (check(mid)) l = mid; else r = mid;}// 答案为 l 也可以写成经典的 l <= r 形式，但我个人更喜欢这种写法，不容易写错边界。 求最小的满足条件的值 “答案越大越容易满足”，即  ≥ x* 可行， < x* 不可行。 1234567int l = L, r = R;while (l + 1 != r) { ...

问题描述 给定一个 n 个点 m 条边的有向图（或无向图），每条边有一个权值 w，求从源点 s 到其他所有点的最短路径长度。 Dijkstra 算法 适用范围 非负权图，即所有边的权值 w ≥ 0。 算法思想 Dijkstra 是一种贪心算法。维护一个集合 S，表示已经确定最短路的点。初始时 S = {s}，dis(s) = 0。 每次从未确定的点中选出 dis 值最小的点 u，将其加入 S，然后用 u 的出边更新邻居的 dis 值： dis(v) = min  (dis(v), dis(u) + w(u, v)) 这个过程称为松弛（relaxation）。 正确性 证明（简要） 每次选出的 u 的 dis 值已经是最短路。反证法：如果存在更短的路径，该路径上必经过某个不在 S 中的点 v，而 dis(v) ≥ dis(u)（因为 u 是 dis 最小的），加上后续边权  ≥ 0，所以路径长度  ≥ dis(u)，矛盾。 这也是为什么 Dijkstra 不能处理负权边的原因：如果有负边权，上述不等式不成立。 朴素实现 每次暴力扫描所有点找最小值，时间复杂度...

定义 对于一个 有向无环图（DAG），其拓扑排序是将所有节点排成一个线性序列，使得对于每一条有向边 (u, v)，u 在序列中都排在 v 的前面。 一个 DAG 的拓扑排序可能不唯一。 一个直观的理解：如果将图看作一组”先后依赖关系”（如课程的先修关系），拓扑排序就是一种合法的执行顺序。 判定 一个有向图存在拓扑排序，当且仅当它是 DAG（即无环）。 证明 充分性：若图无环，则必定存在入度为 0 的点（否则可以沿边一直走，经过 n + 1 个点后必定有重复，产生环）。不断删去入度为 0 的点即可构造拓扑序。 必要性：若图有环，设环上节点为 v1 → v2 → ⋯ → vk → v1。在拓扑序中，v1 必须在 v2 前，v2 在 v3 前，……，vk 在 v1 前。这与 v1 在 v2 前矛盾。故有环时不存在拓扑排序。 证毕。 Kahn 算法（BFS） 例题：洛谷 B3644 【模板】拓扑排序 / 家谱树。 算法流程 统计每个节点的入度 degi。 将所有入度为 0 的节点加入队列。 每次从队列中取出一个节点 u，将其加入拓扑序。 遍历 u 的所有出边...

引入 给定两个字符串 s 和 t，如何快速判断 s 的某个子串是否等于 t？ 暴力比较每个字符的时间复杂度为 O(|t|)，在需要多次比较时开销较大。 字符串哈希的思想是：将字符串映射为一个整数（称为哈希值），通过比较哈希值来代替逐字符比较，从而实现 O(1) 判断两个字符串是否相等。 当然，不同字符串的哈希值可能相同（称为哈希冲突），所以哈希判断是概率正确的。但通过合理选取参数，冲突的概率可以做到极低。 多项式哈希 定义 对于一个长度为 n 的字符串 s = s1s2⋯sn，定义其哈希值为 其中 b 为基数（base），M 为模数。 本质上是将字符串看作一个 b 进制数。 展开即 H(s) = s1 × bn − 1 + s2 × bn − 2 + ⋯ + sn − 1 × b + sn (mod  M) 参数选取 b 通常取一个大于字符集大小的质数，如 131 或 13331。 M 通常取一个大质数，如 109 + 7 或 109 + 9。 也有不少人直接用 unsigned long long 自然溢出，等价于...

引入 在数论问题中，我们经常需要计算如下形式的和： 如果暴力枚举每一个 i，时间复杂度为 O(n)，当 n 较大时无法接受。 观察 的值，可以发现其取值种类数远小于 n，并且相同的取值是连续的一段。 i 1 2 3 4 5 6 7 8 9 10 11 12 12 6 4 3 2 2 1 1 1 1 1 1 以 n = 12 为例， 只有 6 种不同的取值。 数论分块（又称整除分块）就是利用这个性质，将连续的、 相同的一段 i 一起计算，从而大幅降低时间复杂度。 核心结论 取值种类数 （1 ≤ i ≤ n）的取值种类数为 。 证明 分两种情况讨论： 当 时，i 最多有 种取值，故 最多有 种取值。 当 时，，故 最多有 种取值。 综合两种情况，取值种类数为 。 块的右端点 对于给定的 i，所有满足 的最大的 j 为 证明 设 ，则 。 那么满足 的最大的 j 就是满足 的最大的 j，即 。 由于 j 取整数，故 。 证毕。 算法实现 有了上述结论，我们就可以从 l = 1...

引入 给定 n 个元素和若干组关系，每组关系表示两个元素属于同一集合。需要支持以下操作： 合并：将两个元素所在的集合合并为一个集合。 查询：判断两个元素是否在同一集合中。 这就是经典的并查集（Disjoint Set Union，DSU）问题。 例题：洛谷 P3367 【模板】并查集。 基本实现 核心思想 用一棵有根树表示一个集合，树的根节点作为该集合的代表元素。 用 fa[x] 记录节点 x 的父节点。初始时，每个元素独立成一个集合，即 fa[x] = x。 查找 查找元素 x 所在集合的代表元素（即树的根）： 1234int find(int x) { while (fa[x] != x) x = fa[x]; return x;} 合并 将 x 和 y 所在的集合合并，只需让一棵树的根指向另一棵树的根： 123void merge(int x, int y) { fa[find(x)] = find(y);} 查询 123bool query(int x, int y) { return find(x) ==...