117 个考点，一张图练完信奥

语言基础与 STL 0/10

• 数据类型与溢出 int 上限 2.1e9，累加 / 乘法默认想 long long。 J
• 运算符与位运算 与或非异或、移位；判断奇偶、枚举子集、lowbit 都靠它。 J
• 分支与循环 循环边界差一是 WA 高发区，左闭右开要统一。 J
• 函数与递归 递归三要素：出口、规模缩小、返回值含义。 J
• 数组与字符串 数组开全局防炸栈；char 与 string 的转换要熟。 J
• 结构体与 pair 自定义排序（sort + cmp）是结构体的核心用法。 J
• STL 容器：vector / deque / set / map 会按场景选容器：随机访问 vector、去重 set、映射 map。 J
• STL 算法：sort / lower_bound / unique lower_bound 返回第一个 ≥ x 的位置，离散化的基石。 J
• IO 效率与文件读写 cin 关同步、endl 换 '\n'；freopen 按题目要求开。 J
• 调试技巧：断点 / 打印 / assert 打印中间量与手算比对，比盯屏幕快十倍。 J

基础算法当前段位主攻 0/14

• 枚举与模拟 照题意一步步写，关键是把流程拆成小步骤不跳步。 J
• 排序：归并 / 快排 / 桶 / 基数 会手写归并（逆序对）、会用 sort 自定义比较器。 J
• 贪心 先找「交换不变差」的局部最优；反例一票否决。 J
• 二分查找 有序或单调即可二分；边界用 l + (r-l)/2。 J
• 二分答案 答案有单调性 → 二分答案 + check 验证。 J
• 前缀和 O(1) 查区间和；二维前缀和容斥。 J
• 差分 区间整体 +1 变两点修改，最后前缀和还原。 J
• 双指针 单调性保证指针只前进，O(n) 替代 O(n²)。 J
• 滑动窗口 双指针的特化：右扩左收，维护窗口内统计量。 S
• 离散化 值域大但个数少 → 排序去重映射到下标。 S
• 递归与分治 大问题拆独立子问题：归并、快速选择、平面最近点对。 S
• 倍增 预处理 2^j 级跳转：LCA、ST 表、序列倍增的基础。 S
• 离线处理 询问可乱序时按某维排序批量处理（扫描线的前置）。 S
• 扫描线 事件按坐标扫，配合multiset/线段树维护区间状态。 T

搜索当前段位主攻 0/9

• DFS 与回溯 恢复现场是回溯的灵魂；指数级复杂度靠剪枝续命。 J
• BFS 与网格最短路 队列 + vis，第一次到达即最短。 J
• 连通块与洪水填充 网格图 DFS/BFS 标块，数块数 / 块大小。 J
• 剪枝：可行性 / 最优性 / 对称性 估价函数剪掉不可能的分支，搜索题的分水岭。 S
• 记忆化搜索 搜索 + memo = 递归版 DP，状态相同直接返回。 S
• 迭代加深 IDDFS 按深度限制逐层加深，空间 O(d)，解浅时快。 S
• 双向 BFS 从起终点同时扩，相遇即答案，状态数开根号。 S
• A* 启发式搜索 带估价的优先队列搜索，估价必须 ≤ 真实值。 T
• Dancing Links（精确覆盖） 十字双向链表 + dancing links，数独类精确覆盖。 T

动态规划 0/12

• 线性 DP（LIS / LCS） dp[i] 以 i 结尾的最优值；LIS 的 O(n log n) 写法必背。 J
• 背包：01 / 完全 / 多重 01 倒序枚举容量、完全正序；多重用二进制拆分。 J
• 分组背包与树形依赖背包 每组至多选一个；树上依赖由子树体积合并。 S
• 区间 DP 枚举区间长度与分割点：石子合并、回文串。 S
• 树形 DP dfs 合并子树信息；「选/不选父亲」两类经典。 S
• 状压 DP n ≤ 20 时状态存集合；合法子集枚举要会写。 S
• 数位 DP 逐位决策 + 记忆化，处理「数字中含某特征」计数。 S
• 概率与期望 DP 期望倒推：E[x] = Σ p·(代价 + E[next])。 S
• 单调队列优化 DP 转移取滑动区间最值 → 单调队列 O(1) 转移。 S
• 斜率优化 DP 转移是 (i,j) 乘积项 → 决策单调，凸壳上二分。 T
• 数据结构优化 DP 转移查询区间最值/和 → 线段树维护 dp 值。 T
• CDQ 分治优化 三维偏序统计，左半贡献右半的离线分治。 T

图论 0/14

• 图的存储与遍历 邻接矩阵适合稠密图，链式前向星/ vector 适合稀疏图。 J
• 拓扑排序 入度删点；判有向环 + DP on DAG。 J
• 最短路：Dijkstra / SPFA / Floyd 非负权堆优化 Dijkstra；Floyd 三重循环过 n ≤ 500。 S
• 分层图最短路 状态扩展成 (点, 已用次数)，建多层图跑最短路。 S
• 最小生成树 Kruskal / Prim 边排序 + 并查集；次小生成树会枚举替换边。 S
• 并查集 路径压缩 + 按秩合并；带权并查集维护相对关系。 S
• 二分图：染色判定与匈牙利匹配 奇环非二分；匈牙利算法 O(VE) 求最大匹配。 S
• LCA 与树上差分 倍增求最近公共祖先；路径修改用差分落在端点与 LCA。 S
• 树的直径与重心 两次 DFS 或树形 DP 求直径；重心分割经典应用。 S
• 欧拉路径与回路 度数奇偶性判存在性，Hierholzer 求方案。 S
• 强连通分量（Tarjan / Kosaraju） 缩点后变 DAG，再跑拓扑 DP。 T
• 网络流：最大流 / 费用流 Dinic 求最大流；建图（拆点、超级源汇）是核心。 T
• 树链剖分 重链剖分把树路径转成 O(log n) 段区间，配线段树。 T
• 基环树（环 + 外挂树） n 点 n 边的特殊图：断环成树分别处理。 T

数据结构当前段位主攻 0/15

• 栈与队列 括号匹配、表达式求值用栈；宽搜用队列。 J
• 链表 数组模拟双向链表，O(1) 删除（约瑟夫问题）。 J
• 单调栈 求「下一个更大元素」：维护递减栈，弹栈即答案。 S
• 单调队列 滑动窗口最值：队头出界、队尾保单调。 S
• 堆与优先队列 multiset / priority_queue；懒惰删除的写法要会。 J
• 哈希表 unordered_map 均摊 O(1)；手写哈希防卡常。 J
• 树状数组 单点改区间查 / 区间改单点查，代码短常数小。 S
• 线段树（lazy 标记） 区间修改查询的万能结构；lazy 下传是关键。 S
• 权值线段树与动态开点 值域上建线段树求第 k 小；空间不够就动态开点。 T
• 线段树合并 / 分裂 多棵动态开点线段树合并，树上统计利器。 T
• ST 表与 RMQ O(n log n) 预处理 O(1) 查区间最值，不支持修改。 S
• Trie 字典树 前缀树：异或最值、字符串前缀统计。 S
• 平衡树（Treap / Splay） 名次树：插入删除查第 k 大；fhq-Treap 好写。 T
• 分块与莫队 根号平衡：分块处理区间修改；莫队离线区间查询。 T
• 可持久化数据结构 主席树查区间第 k 小：只改一条链。 T

数论 0/9

• 质数筛（埃氏 / 欧拉线性筛） 线性筛 O(n) 顺手筛出最小质因子。 J
• 质因数分解 试除到 √n；因子个数与因子和公式要熟。 J
• gcd / exgcd 辗转相除；扩展欧几里得解 ax+by=gcd。 S
• 快速幂 平方倍增 O(log n)，矩阵快速幂同理。 S
• 逆元 模质数下除法变乘逆元：费马小定理 / exgcd。 S
• 同余方程与中国剩余定理 CRT 合并同余方程组，EXCRT 处理模数不互质。 T
• 原根与离散对数 BSGS 求离散对数；原根判定与求法。 T
• 二次剩余 Cipolla 算法解 x² ≡ n (mod p)。 T
• 莫比乌斯反演 数论分块 + μ 函数前缀和，处理 gcd 计数。 T

组合数学与计数 0/7

• 排列组合基础 加法乘法原理、组合数公式 C(n,m) 的计算。 J
• 组合数递推与 Lucas 定理 杨辉三角递推；大组合数取模用 Lucas。 S
• 常见计数序列 卡特兰数、错排、斯特林数：认出模型直接套。 S
• 容斥原理 「至少」转「恰好」；奇加偶减。 S
• 鸽巢原理 n+1 个物品 n 个抽屉，构造存在性证明。 S
• 群论与 Pólya 计数 置换群 burnside / Pólya 数本质不同方案。 T
• 生成函数入门 把递推变成幂级数运算，OGF/EGF 基础。 T

博弈论 0/3

• Nim 游戏与 SG 函数 SG 异或非零先手胜；mex 运算是核心。 S
• 经典博弈模型 巴什、威佐夫、斐波那契博弈：结论 + 证明都要会。 S
• 反 Nim 与变形博弈 胜负条件反转（取最后一颗者输）的奇偶讨论。 T

字符串 0/8

• 字符串基础与处理 遍历、分割、大小写转换；getline 与混合读入。 J
• 字符串哈希 双哈希防冲突，O(1) 比较任意子串相等。 S
• KMP fail 指针 O(n) 匹配所有出现位置。 S
• 扩展 KMP / Z 函数 每个后缀与原串的 LCP 长度。 T
• Manacher O(n) 求最长回文子串，插入 # 统一奇偶。 T
• AC 自动机 Trie + fail 指针，多模式串匹配。 T
• 后缀数组（SA） 倍增构造 + height 数组，处理子串排名问题。 T
• 后缀自动机（SAM） O(n) 构建，统计本质不同子串个数。 T

计算几何 0/5

• 向量与叉积 叉积判方向、求面积；浮点误差用 eps 控制。 S
• 凸包（Andrew 算法） 排序后单调栈维护上下凸壳。 S
• 旋转卡壳 凸包上对踵点，求直径 / 最小矩形覆盖。 T
• 半平面交 线性规划交区域，单调队列维护。 T
• 扫描线求矩形面积并 x 排序 + 线段树维护 y 覆盖长度。 T

数学与矩阵 0/5

• 矩阵快速幂加速递推 f(n) 线性递推 → 转移矩阵幂，n 到 1e18 也能算。 S
• 高斯消元 解线性方程组 / 期望方程；异或版处理开关灯。 T
• 线性代数：行列式与矩阵秩 矩阵树定理计数生成树、判断线性无关。 T
• 拉格朗日插值 k+1 个点值确定 k 次多项式，求自然数幂和。 T
• 简单数值方法 三分求单峰极值、二分求方程根、自适应辛普森积分。 T

提高技巧与优化 0/6

• 复杂度分析与卡常 算操作数对照 1e8/s 预算；读入优化与 O2。 S
• 启发式合并 小集合合并到大集合，均摊 O(n log n)。 T
• 根号平衡思想 操作分块：O(√n) 修改 O(1) 查询或反之。 T
• 随机化算法 随机划分、爬山、模拟退火骗分。 T
• 对拍与随机数据生成 随机数据 + 暴力对拍，考场上查错神器。 S
• 部分分策略 先写暴力与特判拿稳 30~50 分，再冲正解。 S