一、复杂度估算：10⁸ 法则
估算复杂度时可用 10⁸ 次量级作粗略参照；硬件、语言、访存和操作类型都会影响速度，不能把它当作固定的每秒吞吐量。拿到题目先看数据范围，反推能用什么复杂度的算法——这是选题方向的第一判断：
| n 的规模 | 候选复杂度（需估算） | 典型算法 |
|---|---|---|
| n ≤ 20 | O(2ⁿ · n)，或优化后的 O(2ⁿ · n²) | 状压 DP、爆搜 + 剪枝 |
| n ≤ 400 | O(n³) | Floyd、区间 DP |
| n ≤ 5000 | O(n²) | 二维 DP、中心扩展 |
| n ≤ 2×10⁵ | O(n log n) | 排序 + 堆 / 二分 / 线段树 / 树形 DP |
| n ≤ 10⁶ ~ 10⁷ | O(n) | Manacher、AC 自动机、双指针 |
口诀：看到 20 想状压，看到 400 想三方，看到 10⁵ 想 log，看到 10⁷ 必须线性。算完复杂度再动手写代码。
二、STL 速查（考场最常用的六件工具）
| 工具 | 声明 | 核心操作 | 用途 |
|---|---|---|---|
| 动态数组 | vector<int> a; | push_back / size / a[i] | 邻接表 vector<int> g[N]、一切变长数据 |
| 排序 | sort(a, a+n); sort(v.begin(), v.end(), cmp); | 贪心第一步、离散化 | |
| 二分查找 | lower_bound(v.begin(), v.end(), x) | 离散化求排名、有序数组查找 | |
| 队列 | queue<int> q; | push / front / pop / empty | BFS |
| 栈 | stack<int> s; | push / top / pop | 括号匹配、单调栈 |
| 集合/映射 | set<int> / map<int,int> | insert / count / find | 动态维护有序集合，O(log n) |
三、堆（优先队列）：反悔贪心的武器
堆是一棵满足"父 ≤ 子（小根堆）"的完全二叉树，支持两个操作，都是 O(log n)：
- 插入 push：新元素放到末尾，一路"上浮"到合适位置；
- 取最值 top + pop：堆顶永远是最大/最小值，删顶后末尾元素补位"下沉"。
priority_queue<int> big; // 大根堆（默认，堆顶最大）
priority_queue<int, vector<int>, greater<int>> small; // 小根堆（堆顶最小）
small.push(x); small.pop(); // O(log n)
small.top(); // O(1)，仅访问堆顶生活类比：医院急诊叫号屏永远显示"当前最紧急"的病人。新病人来了按紧急程度插入队伍，屏上自动更新——你不需要知道队伍内部怎么排，只要知道屏上永远是最紧急的。这就是堆。
懒删除技巧：堆不支持"删除任意元素"。变通做法：要删的元素先打个标记，等它浮到堆顶时再跳过（见于 种树、Dijkstra）。
四、取模与 long long：爆零重灾区
- 什么时候用 long long：两个 int 相乘前先估上界。n ≤ 10⁵、数值 ≤ 10⁹ 时，求和/乘积轻松超过 2.1×10⁹（int 上限）。拿不准就开 long long，代价几乎为零。
- 取模三律：加法、乘法注意先避免溢出；减法在 0 ≤ a,b < mod 且不溢出时可写成
(a - b + mod) % mod；除法不能直接取模，使用逆元前还要确认逆元存在。 - 常见模数：998244353、10⁹+7。输出前确认答案已取模且非负。
五、文件读写：freopen 与防爆零
CSP-S 复赛是 文件 IO：从 xxx.in 读入、向 xxx.out 输出（xxx 是题目英文标识）。程序开头固定写：
int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
// ... 正常用 scanf/printf 或 cin/cout
return 0;
}每年都有人因此爆零：① 文件名与题目英文标识不一致（大小写也要一致）；② 调试时注释掉 freopen，提交前忘改回；③ 提交目录里留了 .in/.out/可执行文件。考前把防爆零清单过一遍。
读入加速：数据量 ≥ 10⁶ 时用 scanf/printf，或 cin 前加 ios::sync_with_stdio(false); cin.tie(nullptr);（加完不要再混用 scanf）。
六、对拍：找 bug 的终极武器
写完一个"聪明做法"但不确定对不对？再写一个笨但显然正确的暴力版，用随机数据比对两者输出：
- 暴力版 brute.cpp：O(n²) 甚至 O(n!) 都行，只要逻辑简单到不可能错。
- 数据生成器 gen.cpp：随机出小规模合法输入（小数据才能让暴力跑得动）。
- 对拍脚本：循环执行 gen → 两份程序 → diff 比对，输出不同就停下保留现场。
# bash 对拍循环
while true; do
./gen > in.txt
./a < in.txt > out1.txt
./brute < in.txt > out2.txt
diff out1.txt out2.txt || { echo "FOUND!"; break; }
done