图论
图论图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形。 存图方式用 n 代指图的点数，用 m 代指图的边数。 邻接表使用一个支持动态增加元素的数据结构构成的数组，如 vector<int> adj[n + 1] 来存边，其中 adj[u] 存储的是点 u 的所有出边的相关信息（终点、边权等）。 1234567891011121314struct edge { int v, w;};int main { int n, m; cin >> n >> m; vector<vector<edge>> adj(n + 1); for (int i = 1; i <= m; ++i) { int u, v, w; cin >> u >> v >> w; adj[u].emplace_back(v, w); ...
字符串
字符串字符串，就是由字符连接而成的序列。 常见的字符串问题包括字符串匹配问题、子串相关问题、前缀/后缀相关问题、回文串相关问题、子序列相关问题等。 字符串哈希Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。 双值哈希 / 前缀哈希序列令 $f_i(s) = f(s[1..i])$ 为字符串 s 的前缀哈希序列，预处理字符串 s 的前缀哈希序列。 123456constexpr u64 M = 1e9 + 7, M2 = (u64) 1e16 + 61, B = 133;vector<u64> hs1(n + 2), hs2(n + 2);for (int i = 1; i <= n; i++) { hs1[i] = (hs1[i - 1] * B + s[i - 1]) % M; hs2[i] = (hs2[i - 1] * B + s[i - 1]) % M2;} 获取子串哈希值注意到 $f(s[l+1..r])=f_r(s)-f_{l}(s) \times...
数学与计算
数学与计算数论数论主要研究整数的性质。 素数筛筛法是一种在数论中通过系统排除不满足条件的数来识别符合条件的数集合的方法，使用筛法可以快速筛选出指定区间的素数，也可以拓展到求积性函数。 埃拉托斯特尼筛如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了，注意 0 和 1 要特殊处理，时间复杂度 $O(n\log{\log{n}})$。 注意到筛法求素数的同时也得到了每个数的最小质因子，因此筛法可以在 $O(n\log{n})$ 的时间复杂度内对 $[1,n]$ 区间所有数分解质因数，或者在 $O(k\log{n})$ 的时间复杂度内将 $[1,n]$ 区间的所有数分解出至多 $k$ 个质因数。 基于埃拉托斯特尼筛法可以还可以实现区间素数筛，由于每个合数只会被其最小质因数标记，且最小质因数不大于 $\sqrt{n}$，因此只需筛至 $\sqrt{n}$ 即可，复杂度 $O(\sqrt{n}\log{\log{n}})$ 。 123456789101112131415vector<int> p,...
数据结构
数据结构不同的数据结构各有优劣，能够处理的问题各不相同，而根据具体问题选取合适的数据结构，可以大大提升程序的效率。 并查集含有路径压缩和按集合大小合并优化的并查集实现，可以查询集合元素数量，每个操作的均摊复杂度为 $O(\alpha(n))$ 。 12345678910111213141516171819202122struct DSU { vector<int> p; explicit DSU(int n) : p(n, -1) { } int find(int x) { return p[x] < 0 ? x : p[x] = find(p[x]); } bool same(int x, int y) { return find(x) == find(y); } bool merge(int x, int y) { x =...
简介
竞赛算法模板 算法尽量精简成函数和公开变量，数据结构尽量使用类包装并减少冗余操作。 除存在溢出或特殊需求时，整数使用 int 类型，需要自行修改类型以符合需求。 涉及区间问题使用易于实现的区间定义，一般采用左闭右开实现，特殊情况有标注。 竞赛技巧代码模板包含万能头文件，类型别名，随机数生成器和关闭输入输出同步。 1234567891011121314151617181920#include <bits/stdc++.h>using namespace std;using f80 = long double;using u128 = unsigned __int128;using i128 = __int128;using u64 = unsigned long long;using i64 = long long;using u32 = unsigned;constexpr int inf = 1e9;constexpr i64 infl = 1e18;random_device rd;mt19937_64 rnd(rd());int...
语言特性
标准模板库一些常用的库。 algorithm 库 algorithm 库提供通用算法函数（如 sort、find、reverse、max），用于排序、搜索、遍历及容器操作，支持迭代器模式，适用于数据批量处理和竞赛编程优化。 algorithm 库中的函数基本都有 ranges 版本。 基于比较的函数可传入 cmp 以指定比较函数。 find(v.begin(), v.end(), val)：顺序查找，其中 val 为需要查找的值。 reverse(v.begin(), v.end())：翻转序列，如数组、字符串。 sort(v.begin(), v.end(), cmp)：内省排序，不保持相对顺序，其中 cmp 为自定义的比较函数。 stable_sort(v.begin(), v.end(), cmp)：归并排序，保持相对顺序，用法同 sort。 unique(v.begin(), v.end())：将序列相邻的重复元素移动到序列末尾，返回指向去重后序列结尾的迭代器，原容器大小不变。与 sort 结合使用可以实现序列去重。 shuffle(v.begin(),...
通用算法
通用算法基础算法常作为其它算法的基础。 快速乘 & 快速幂快速乘可避免模数大于 $int$ 取值范围时溢出，可将快速幂中乘法替换为快速乘版本以避免乘法溢出。 123456789101112131415i64 qmul(i64 x, i64 y, i64 m) { i64 z = (f80) x / m * y + 0.5L; u64 c = (u64) x * y - (u64) z * m; return c < m ? (i64) c : (i64) (c + m);}i64 qpow(i64 a, i64 n, i64 m) { i64 res = 1; while (n) { if (n & 1) res = res * a % m; a = a * a % m; n >>= 1; } return res;} Barrett 模乘Barrett...