落萱_Love 的博客

图论 图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形。 存图方式 用 n 代指图的点数，用 m 代指图的边数。 邻接表 使用一个支持动态增加元素的数据结构构成的数组来存边，其中 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 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。 双值哈希 / 前缀哈希序列 令 fi(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]) = fr(s) − fl(s) × br − l 。 其中...

数学与计算 数论 数论主要研究整数的性质。 筛法 筛法是一种在数论中通过系统排除不满足条件的数来识别符合条件的数集合的方法，使用筛法可以快速筛选出指定区间的素数，也可以拓展到求积性函数。 埃拉托斯特尼筛 如果我们从小到大考虑每个数，将每个遍历到的素数的倍数（大于等于自己的平方，即该素数作为最小质因数）记为合数，那么运行结束的时候没有被标记的数就是素数，注意 0 和 1 要特殊处理。时间复杂度 O(nlog log n)。 注意到筛法求素数的同时也得到了每个数的最小质因子，因此筛法可以在 O(nlog n) 的时间复杂度内对 [1, n] 区间所有数分解质因数，或在 O(nk) 的时间复杂度内将 [1, n] 区间的所有数分解出至多 k 个质因数，同时判定每个数是否分解完全。 基于埃拉托斯特尼筛法可以还可以实现区间筛，由于每个合数只会被其最小质因数标记，且最小质因数不大于 $\sqrt{n}$，因此只需筛至 $\sqrt{n}$ 即可，在筛的过程中标记所求区间素数即可，复杂度 $O(\sqrt{n}\log{\log{n}})$...

数据结构 不同的数据结构各有优劣，能够处理的问题各不相同，而根据具体问题选取合适的数据结构，可以大大提升程序的效率。 珂朵莉树 珂朵莉树通过将序列划分为多个值相同（或性质相同）的连续区间来高效处理区间赋值和查询操作，是一种基于区间合并的暴力数据结构。 在 perform 以后立即对同一区间调用 assign 的情况下，珂朵莉树的时间复杂度为均摊 O(log n) ，而在操作随机的情况可以达到更优的期望时间复杂度 O(log log n) 。 若以上要求均不满足，则最坏情况下操作的复杂度退化为 O(n) ，其中 m 为操作次数，n 为珂朵莉树中最大区间个数。 1234567891011121314151617181920map<int, int> odt; odt[1] = 1; auto split = [&](int x) { auto it = odt.upper_bound(x); return odt.emplace_hint(it, x, prev(it)->second); ...

竞赛算法模板 本模板目标是尽量全地收集典型的算法与数据结构，并为所有内容均添加合理的介绍。 算法尽量精简成函数和公开变量，数据结构尽量使用类包装并减少冗余操作。 除存在溢出或特殊需求时，整数使用 int 类型，需要自行修改类型以符合需求。 涉及区间问题使用易于实现的区间定义，一般采用左闭右开实现，特殊情况有标注。 竞赛技巧 代码模板 包含万能头文件，类型别名，随机数生成器和关闭输入输出同步。 随机数生成器可以使用时间戳 chrono::steady_clock::now().time_since_epoch().count() 作为种子。 12345678910111213141516171819202122232425262728293031#include <bits/stdc++.h> using namespace std; using f80 = long double; using u128 = unsigned __int128; using i128 = __int128; ...

标准模板库 一些常用的库函数。 __buildin 位运算 高效位运算，bit 库的替代品。 注意在给 64 位整数使用时须在函数名末尾添加 ll 。 __builtin_ctz()：返回括号内数的二进制表示数末尾 0 的个数。 __buitlin_clz()：返回括号内数的二进制表示数前导 0 的个数。 __builtin_popcount()：返回括号内数的二进制表示数 1 的个数。 __builtin_parity()：判断括号中数的二进制表示数 1 的个数的奇偶性（偶数返回 0 ，奇数返回 0 ）。 algorithm 库 algorithm 库提供通用算法函数（如 sort、find、reverse、max），用于排序、搜索、遍历及容器操作，支持迭代器模式，适用于数据批量处理和竞赛编程优化。 algorithm 库中的函数基本都有 ranges 版本。 基于比较的函数可传入 cmp 以指定比较函数。 find(v.begin(), v.end(), val)：顺序查找，其中 val...

通用算法 基础算法 常作为其它算法的基础。 快速乘 & 快速幂 快速乘可避免模数大于 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...