常用 ACM 算法竞赛笔记与模板(整理版)
目录
环境与 IO
标准输入 / 输出 重定向
说明
- PowerShell 不支持
<作为 stdin 重定向(与 CMD 不同)。
示例
# python os.system / powershell / bashtype A.in | std.exe > A.ans# PowerShell — 方式 1:使用管道Get-Content in.txt -Raw | A.exe > out.txt
# PowerShell — 方式 2:调用 cmd(/C 表示执行指定的命令后关闭命令提示符窗口)cmd /c "A.exe < in.txt > out.txt"# Linux / 通用./A.exe < in.txt > out.txtC++ 输出固定小数位
cout << fixed << setprecision(2) << num << '\n';注意
- 若不加
fixed,setprecision表示有效数字位数而非小数位数**
常用模板与输入加速
Template
#include <bits/stdc++.h>using namespace std;using ll = long long;const int N = 2e5 + 5;string s;int n;void solve() {
}int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); freopen("A.in", "r", stdin); // freopen("A.out", "w", stdout); int T = 1; // cin >> T; while(T--) solve();}快读
#include<iostream>#include<cstdio>#include<vector>using namespace std;namespace INPUT{ char buf[1 << 20], *p1, *p2; #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)}using namespace INPUT;template<typename T>inline T read(){ T x = 0, p = 1; char ch = gc(); for(; ch < '0' || ch > '9'; ch = gc()) if(ch == '-') p = -1; for(;ch >= '0' && ch <= '9'; ch = gc()) x = (x<<3) + (x<<1) + (ch^48); return x * p;}void solve(){ // ...}int main(){ freopen("A.in", "r", stdin); freopen("A.out", "w", stdout); int T = read<int>(); while(T--) solve();}Python 随机 / 生成 / 校验工具
扔到另一个post去了喵
数据结构 DSU / BIT / multiset / fenwick
差分与前缀和技巧
区间覆盖次数最大值
给定若干区间 ([l, r]),只需计算某点被覆盖的最大次数(不关心具体点)。
- 对每个区间:
c[l]++,c[r + 1]--
- 对
c求前缀和,维护最大值即可
说明:
- 若坐标范围小,用数组
- 若坐标范围大 / 稀疏,用
map - 不同区间权值不同,直接把
++ / --改为对应权值
map<ll, ll> c;for (auto [l, r] : intervals) c[l]++, c[r + 1]--;
ll cur = 0, ans = 0;for (auto& [_, v] : c) { cur = (v += cur); ans = max(ans, cur);}二次差分:区间加 等差数列
对原数组做 两次差分,用 c[] 维护。
区间 [l,r] 加 首项为 , 公差为 的等差数列:
c[l] += a0c[l+1] += d - a0c[r+1] -= a_n + dc[r+2] += a_n最后对 c 做两次前缀和还原。
忘公式:直接对目标序列手推两次差分反推更新点。
带权并查集
// 带权并查集(a[x] = a[y] + d; 模 M)struct DSU { std::vector<size_t> pa, size, dist;
explicit DSU(size_t size_) : pa(size_), size(size_, 1), dist(size_) { std::iota(pa.begin(), pa.end(), 0); }
size_t find(size_t x) { if (pa[x] == x) return x; size_t y = find(pa[x]); (dist[x] += dist[pa[x]]) %= M; return pa[x] = y; }
bool unite(size_t x, size_t y, int d) { // a[x] = a[y] + d; find(x), find(y); (d += M - dist[y]) %= M; (d += dist[x]) %= M; x = pa[x], y = pa[y]; if (x == y) return d == 0; if (size[x] < size[y]) { std::swap(x, y); d = (M - d) % M; } pa[y] = x; size[x] += size[y]; dist[y] = d; return true; }
int check(size_t x, size_t y) { // a[x] - a[y] find(x), find(y); if (pa[x] != pa[y]) return -1; return (dist[y] - dist[x] + M) % M; }};二维树状数组(Fenwick)
struct fenwick{ // 二维树状数组 void add(int x, int y, int v) { for (int i = x; i <= n; i += lowbit(i)) for (int j = y; j <= m; j += lowbit(j)) c[i][j] += v; }};multiset 常见用法与效率提示
-
查找某值:
s.find(val)— 推荐用于判断存在性(不要用count在 multiset 上查元素的存在性:multiset::count()的复杂度为O(k + log n),其中k为该值出现的次数)。 -
删除:
s.erase(val)删除所有等值元素(C++11 以后返回删除个数)s.erase(it)删除迭代器s.erase(s.find(val))删除单个点
-
最小/最大:
*s.begin()最小值*prev(s.end())最大值
图论与最小生成树 (MST) / 桥
桥(割边)的性质
1 → n 路径与桥的关系
首先,我们将所有位于 任意一条从 到 的路径上的边的集合记作 。 接着,找出图中的所有 桥(割边),将这些边的集合记作 。 然后,任选一条从 到 的简单路径,将路径上的边的集合记作 。 那么:
对图 ,若 是 的一棵最小生成树,加入若干新点 并连接若干边后,新图 的最小生成树中,不会使用原图中不在 中的边。
即:。
结论(简洁):也就是说加入新点可在原最小生成树上做
数论与位运算技巧
位运算内建函数
__lg(x):返回__builtin_popcount(x):返回int中二进制 1 的个数__builtin_popcountll(x):返回long long中二进制 1 的个数
常见用法
- 判断是否为 2 的幂:
__builtin_popcount(x) == 1 - 所有
1 << x建议写为1ll << x防止溢出
异或性质
结论:
- 若 ,则 。
- 若 ,则 。
- 若 ,则 。
- 若 ,则 。
选择型异或问题 → 线性基
模型
- 每位可选: 或
- 等价变形: ,
性质
任意平方数关于模 3 的结果只可能是 0 或 1()。 推论:任意平方数可表示为若干个 3 的和,或若干个 3 加上一个偶数(用于构造题目证明时)。
计数某一位为 1 的快速方法( 计算区间)
def count_up_to(x, k): """计算 [0, x] 中二进制第 k 位为 1 的整数个数""" if x < 0: return 0 T = 1 << (k + 1) # 周期长度 2^(k+1) L = 1 << k # 每个周期中 1 的数量 2^k full_cycles = (x + 1) // T remainder = (x + 1) % T return full_cycles * L + max(0, remainder - L)
def query_range(l, r, k): """查询 [l, r] 中二进制第 k 位为 1 的整数个数""" return count_up_to(r, k) - count_up_to(l - 1, k)平面
极坐标排序
给定一组坐标点,可以通过极坐标的角度(theta)对其进行排序。首先,定义一个 getPos 函数,返回每个点在四个象限中的位置,用于决定排序时的优先级:
int getPos(array<int, 2> p) { auto [x, y] = p; if (x == 0 && y == 0) return -1; // 原点 if (x >= 0 && y > 0) return 1; // 第一象限 if (x > 0 && y <= 0) return 2; // 第二象限 if (x <= 0 && y < 0) return 3; // 第三象限 if (x < 0 && y >= 0) return 4; // 第四象限 assert(false); return 0;}sort(a + 1, a + 1 + n, [](array<int, 2>& A, array<int, 2>& B){ int pA = getPos(A); int pB = getPos(B);
if (pA != pB) return pA < pB; // 先按照象限排序
ll res = 1ll * A[0] * B[1] - 1ll * B[0] * A[1]; return res < 0; // 判断同象限点的顺逆时针});控制排序方向
- 修改
getPos中的边界情况来调整原点或特殊情况的处理。- 通过
res < 0可以控制顺时针或逆时针的排序,修改为res > 0则为逆时针。
距离变换:曼哈顿与切比雪夫
- 曼哈顿距离:
- 切比雪夫距离:
转换技巧:
将 ,则原坐标系中的 曼哈顿距离 等于新坐标系中的 切比雪夫距离。
将 ,则原坐标系中的 切比雪夫距离 等于新坐标系中的 曼哈顿距离。
哈希与模数表
| 类型 | 模数 (mod) | 常用基数 (base) | 说明 |
|---|---|---|---|
| 单模数常用 | 1,000,000,007 (1e9+7) | 131, 137, 911382323 | 经典,OJ 通用 |
| 单模数常用 | 1,000,000,009 (1e9+9) | 131, 233, 911382323 | 常和 1e9+7 搭配 |
| 单模数常用 | 998,244,353 | 61, 107, 131, 233 | NTT 质数,代码里常见 |
| 双模数组合 | (1e9+7, 1e9+9) | (131, 137) | 最经典的双模哈希 |
| 双模数组合 | (998244353, 1e9+7) | (233, 911382323) | 抗碰撞性更高 |
| 64位自然溢出 | 2^64 (unsigned long long) | 随机奇数 ~ 1e5..1e9 | 无需取模,溢出即模 2^64 |
C++20 ranges / STL / 小技巧
Lambda 递归
写法一:auto self
auto dfs = [&](auto self, int u) -> void { for (int v : adj[u]) self(self, v);};dfs(dfs, root);写法二:std::function
function<void(int)> dfs = [&](int u) { for (int v : adj[u]) dfs(v);};dfs(root);:: 全局作用域运算符
- 使用
::x显式访问全局变量,避免与局部变量 / 形参重名 - 例:
dfs(u, fa)中用::fa[u] = fa
内存占用估算技巧
计算空间,所有变量定义之前bool Be; 之后bool Ed;, 然后输出:cout << ((&Ed - &Be) >> 20) << endl; 就是使用变量的总空间,单位为 MB (可能cout的时候需要调换Be,Ed的位置,原因:大端小端)
views
for (auto i : views::iota(1, n + 1)) {}
auto p = std::ranges::partition_point(v, odd);std::cout << *p << '\n';iota_view(0, 10^9)是虚拟范围,O(1) 表示无需构造实际容器,适合用于二分答案。partition_point要求check在范围内单调(先true后false),必要时反转返回值。
std::map<int, std::string> mp = {{1, "a"}, {2, "b"}, {3, "c"}}; // 反向迭代mapfor (auto&& [k, v] : std::views::reverse(std::views::all(map))) { ... }for (auto&& [k, v] : mp | rv::all | rv::reverse) std::cout << k << " " << v << "\n";平板电视(pbds)
动态第 小
#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>using namespace __gnu_pbds;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
os.insert(x); // 插入os.erase(x); // 删除os.order_of_key(x); // < x 的元素个数*os.find_by_order(k); // 第 k 小(0-indexed)生成下一个排列(字典序)
#include <algorithm>bool next_permutation(iterator start, iterator end);- 复杂度:
O(n)(单次)
debug 宏
#define debug(x) cout << #x << "= " << x << endlunordered_map pair 哈希
struct PairHash { size_t operator()(const std::pair<int,int>& p) const noexcept { return std::hash<long long>()(((long long)p.first << 32) ^ p.second); }};std::unordered_map<std::pair<int, int>, ll, PairHash> count;⚠️ 注意:自实现 hashmap 在性能上可能不如嵌套
std::unordered_map<int, std::unordered_map<int, ll>>,后者在很多场景更稳定。
常见数学结论(快查)
-
-
对于大小为 的方格,若 为奇数,则可以从 到 一次性走完所有方格( 型)
-
素数计数函数:。
-
多边形成立条件(给定边长能否构成多边形):
若有 根边长 ,当且仅当 。
偏序与线性扩展(排序 / LIS 技巧)
对直积偏序 ,可通过“主序升序、次序逆序”的线性扩展消除等值冲突。
代码片段速查(零散但常用)
C++ 随机数(可复现 / 不可复现)
#include <iostream>#include <random>using namespace std;// 用随机设备作为种子random_device rd;mt19937 gen(rd());// 直接使用gen() 返回一个unsigned int类型的数// 所以你需要使用 int x = gen() >> 1; 来截断
// 或者用固定种子mt19937 gen2(42);uniform_int_distribution<int> dist(1, 6); // [1,6] 区间cout << dist(gen) << endl; // 模拟掷骰子清空容器(swap trick)
template<typename T>void clear(T& v){ T().swap(v); }实用命令
测时
PowerShell:Measure-Command {A.exe} 测程序运行时间(PowerShell 专用)。
返回目录
AI持续维护Prompt
零碎知识点整理
你是 ACM 算法竞赛 Markdown 笔记整理助手。我会输入一些零碎、口语化、不成体系的知识点。
请你将它们整理为简短、清晰、易理解的总结,要求:1. 控制在几句话内2. 偏向比赛时快速翻笔记能看懂3. 使用算法竞赛常用表述4. 适合直接写进 Markdown 笔记
输出要求:- 不讲背景、不写推导- 不废话,只保留结论和用法- 表述尽量精炼、好记✅ Prompt 1(推荐长期使用)
你是 ACM 算法竞赛 Markdown 笔记的结构维护助手。
下面是我当前笔记的【完整多层目录结构】,请你严格基于该目录来判断我新增内容的插入位置。
【目录结构】(粘贴当前 md 的完整多层目录,包括一级 / 二级 / 三级)
【我新增的内容】(粘贴新的算法、结论、模板或技巧)
请你按以下格式输出,并且【每一层都要写全】:
1️⃣ 推荐插入路径(从一级到最深层):- 一级标题:- 二级标题:- 三级标题(若无则写“无”):- 四级标题(若无则写“无”):
2️⃣ 是否需要新建标题:- 新建层级:(二级 / 三级 / 四级 / 不需要)- 原因说明:
3️⃣ 若存在多个可选位置:- 给出所有候选路径- 指出最推荐的一条,并说明理由
4️⃣ 若内容与现有笔记有重叠:- 指出应合并的具体小节- 或说明为何应独立成新小节