P0 = 必会 · P1 = 高频 · P2 = 选学 · P3 = 冷门。共 372 个知识点，按优先级四档排列。
P0 必会P1 高频P2 选学P3 冷门基础中级高级前沿
P0 · 必会
94 个知识点
行列式P0高级G-C-14 线性代数族O(n^3)高斯消元法求行列式，矩阵树定理与计数应用基础
卢卡斯定理P0高级G-C-8 数论进阶族C(n,m) mod p当p为素数时分位计算，O(p log n)，大组合数取小素模
可持久化线段树(主席树)P0高级G-D-5 可持久化数据结构函数式线段树按版本共享节点，支持历史版本查询与区间k小值；保存每次修改的历史版本，区间第k小/历史查询
回溯法P0基础G-A-14 搜索算法族DFS+撤销操作，走不通就回头，排列/组合/棋盘类问题
BFS广度优先搜索P0基础G-B-1 图基础与遍历按层遍历图，队列实现O(V+E)，可求无权最短路；逐层扩展，队列实现，求无权图最短路，空间O(n)
快速幂P0基础G-C-7 数论基础族O(log n)计算a^n，二进制取幂，模意义下核心工具
二叉堆P0基础G-A-3 堆与优先队列族完全二叉树维护优先队列，O(log n)插入/删除最值
二分查找P0基础G-A-1 排序与基础算法族有序数组O(log n)查找，含lower_bound/upper_bound
二分图判定P0基础G-B-6 二分图与匹配族BFS/DFS染色法判定二分图O(V+E)
位运算基础P0基础G-E-2 位运算族与/或/异或/取反/移位运算，位运算优先级陷阱，整数低位操作
组合数P0基础G-C-10 组合计数基础族C(n,m)的计算：递推/预处理阶乘逆元/Lucas，竞赛计数核心
常见错误避免P0基础G-E-4 调试与对拍族int溢出/未初始化/运算符优先级/scanf格式符/变量重名shadow等竞赛高频错误清单
编译与调试P0基础G-E-9 工具链族g++编译选项(-O2/-g/-Wall/-Wextra)、gdb调试、编译器优化原理(常量折叠/死代码消除等)
时间/空间复杂度分析P0基础G-A-1 排序与基础算法族渐近符号(O/Theta/Omega)与复杂度分析方法
连通分量P0基础G-B-1 图基础与遍历无向图连通块，BFS/DFS遍历标记O(V+E)
比赛时间分配与策略P0基础G-E-8 竞赛策略族ICPC/OI比赛策略：读题顺序、时间分配、队友分工、罚时控制、封板策略
调试宏P0基础G-E-4 调试与对拍族#ifdef DEBUG / -DONLINE_JUDGE 编译宏控制调试输出，提交时无需删代码
DFS深度优先搜索P0基础G-B-1 图基础与遍历递归深入遍历O(V+E)，连通性判定与DFS生成树基础；沿一条路径深入到底再回溯，栈/递归实现，空间O(h)
Dijkstra算法P0基础G-B-2 最短路族非负权单源最短路，堆优化O((V+E)logV)，贪心松弛
离散化P0基础G-E-7 离线与杂项技巧族大值域映射到紧凑排名：排序+去重+lower_bound，保持偏序关系，压缩数组下标
分治与递归P0基础G-A-1 排序与基础算法族分解-解决-合并，递归处理子问题
动态规划基础P0基础G-A-11 动态规划基础族最优子结构/无后效性/子问题重叠，状态定义与转移方程
完全背包P0基础G-A-11 动态规划基础族每件物品无限取，正序遍历容量
0-1背包P0基础G-A-11 动态规划基础族每个物品取/不取，O(nW)转移，滚动数组优化空间
记忆化搜索P0基础G-A-11 动态规划基础族自顶向下DFS+缓存，DP的递归实现方式
枚举与暴力P0基础G-A-1 排序与基础算法族系统枚举所有可能，常结合剪枝优化
欧几里得算法(GCD)P0基础G-C-7 数论基础族辗转相除法求最大公约数，O(log min(a,b))，数论基础工具
快速读入P0基础G-E-1 IO与常数优化族整数快速读入：C++用getchar/fread，Python用sys.stdin.read批量读入+map(int,...split())
树状数组(BIT)P0基础G-A-5 区间查询与分块族lowbit分组，O(log n)单点修改+前缀查询，代码短常数小
图论基础概念P0基础G-B-1 图基础与遍历图的基本概念：点、边、有向/无向图、度、路径、环、子图
图的存储P0基础G-B-1 图基础与遍历邻接矩阵、邻接表、链式前向星等存图方式
贪心算法P0基础G-A-1 排序与基础算法族每步取局部最优，需证明最优子结构与交换论证
哈希表(散列表)P0基础G-A-10 哈希与链表族key-value映射，哈希函数+冲突处理(开链/开放寻址)
Kruskal算法P0基础G-B-3 生成树族最小生成树，贪心排序+并查集O(ElogE)
归并排序P0基础G-A-1 排序与基础算法族分治排序，O(n log n)稳定排序，可用于求逆序对
模算术P0基础G-C-7 数论基础族模意义下加减乘除运算，取模与负数处理，竞赛必备基础
骗分/部分分P0基础G-E-8 竞赛策略族namespace分治写暴力/特殊性质部分分；OI赛制核心技能，按数据范围分档拿分
前缀和与差分P0基础G-A-1 排序与基础算法族O(1)区间和查询/O(1)区间修改，一维与多维
Prim算法P0基础G-B-3 生成树族最小生成树，贪心+堆O(ElogV)，适合稠密图
素数判定(试除)P0基础G-C-7 数论基础族O(sqrt(n))试除法判定素数，基础方法，大数用Miller-Rabin
题型识别P0基础G-E-8 竞赛策略族传统题/交互题/提交答案题/通信题的识别与应对策略，评测结果类型(AC/WA/TLE/RE等)
二维列表正确创建P0基础G-E-3 Python竞赛特性族[[0]*n for _ in range(m)]创建独立行；[[0]*n]*m会导致所有行共享同一对象（引用陷阱）
Python批量读入P0基础G-E-3 Python竞赛特性族sys.stdin.read().split()一次性读入全部输入再map(int,...)，避免逐行input()超时
Python大整数原生支持P0基础G-E-3 Python竞赛特性族Python int无限精度，无需手写大数类；pow(a,b,mod)内置快速幂；2**512直接算
列表推导优化P0基础G-E-3 Python竞赛特性族Python for循环极慢，用列表推导式/filter/map/内置函数替代显式循环获10x+加速
PyPy差异与注意事项P0基础G-E-3 Python竞赛特性族PyPy JIT加速但递归反而更慢；大整数/内存差异；部分库不可用；递归限stack需手动设
递归栈限制设置P0基础G-E-3 Python竞赛特性族sys.setrecursionlimit(1<<20)避免深递归栈溢出；Python默认递归深度仅1000
队列P0基础G-A-2 栈队列与单调结构族FIFO先进先出结构，BFS基础组件
快速排序P0基础G-A-1 排序与基础算法族分治排序，期望O(n log n)，最坏O(n^2)，常数小
随机数据生成P0基础G-E-4 调试与对拍族对拍用随机数据生成器：mt19937/random模块，testlib generator框架
埃氏筛P0基础G-C-7 数论基础族O(n log log n)筛素数，标记合数，基础素数筛法
模拟P0基础G-A-1 排序与基础算法族按题意直接模拟过程，考察代码实现能力
排序基础概念P0基础G-A-1 排序与基础算法族排序算法总览：稳定性、复杂度、比较与非比较排序的分类
ST表(稀疏表)P0基础G-A-5 区间查询与分块族倍增预处理O(1)回答可重复贡献问题(RMQ/GCD)，不支持修改
栈P0基础G-A-2 栈队列与单调结构族LIFO后进先出结构，支持括号匹配/表达式求值等
对拍/压力测试P0基础G-E-4 调试与对拍族生成随机数据→暴力/正解分别运行→比对输出找bug，竞赛调试核心手段
拓扑排序P0基础G-B-1 图基础与遍历DAG节点线性排序，Kahn算法(入度BFS)或DFS逆序O(V+E)
树基础P0基础G-B-7 树算法族树的基本概念：根、叶、深度、子树、父亲
树的直径P0基础G-B-7 树算法族树上最长路径，两次DFS或树形DPO(V)
双指针P0基础G-E-7 离线与杂项技巧族同向/相向移动两指针维护区间信息：O(n)解决单调性区间问题，莫队基础
高精度(大整数)P0中级G-C-18 大整数与数制族大整数加减乘除，FFT加速乘法O(n log n)，压位优化
二分答案P0中级G-A-1 排序与基础算法族对答案值域二分，配合check函数求解最优化问题
中国剩余定理(CRT)P0中级G-C-8 数论进阶族求解同余方程组，将模互素的大模数分解为小模数合并，exCRT处理不互素
区间DPP0中级G-A-11 动态规划基础族f(i,j)表示区间[i,j]最优，枚举合并点k，O(n^3)
树形DPP0中级G-A-11 动态规划基础族树上递归DP，DFS后序传递子树最优解到父节点
欧拉函数P0中级G-C-7 数论基础族phi(n)表示1~n中与n互素的数个数，积性函数，欧拉定理基础
期望与方差P0中级G-C-15 概率族E[X]与Var(X)的线性性质，期望DP核心工具
扩展欧几里得P0中级G-C-7 数论基础族求ax+by=gcd(a,b)的一组整数解，模逆元与线性方程的基础
费马小定理P0中级G-C-7 数论基础族p素数时a^(p-1)≡1(mod p)，模逆元与素性检测的理论基础
斐波那契数列P0中级G-C-10 组合计数基础族F(n)=F(n-1)+F(n-2)，矩阵快速幂O(log n)求第n项，恒等式众多
高斯消元P0中级G-C-14 线性代数族O(n^3)解线性方程组/求秩/求行列式，线性代数核心算法
KMP算法P0中级G-C-1 字符串匹配族线性时间字符串匹配，利用前缀函数(pi数组)避免回溯，O(n+m)
最近公共祖先(LCA)P0中级G-B-7 树算法族倍增预处理O(VlogV)查询O(logV)，或Tarjan离线O(α)
线性基P0中级G-C-14 线性代数族异或空间基，O(n log max)插入，求最大/最小/第k小异或值
矩阵基础P0中级G-C-14 线性代数族矩阵加减乘与转置，矩阵快速幂O(k^3 log n)，递推加速核心
模逆元P0中级G-C-7 数论基础族求a在模m下的逆元，方法：扩展欧几里得/费马小定理/线性递推
单调队列P0中级G-A-2 栈队列与单调结构族维护滑动窗口最值，O(n)均摊，DP优化基础
单调栈P0中级G-A-2 栈队列与单调结构族维护单调性的栈，O(n)求左右第一个大/小于当前值
Nim游戏P0中级G-E-6 博弈论族N堆石子轮流取，Nim和(异或)为0则先手必败(P态)，非0则先手必胜(N态)；公平组合博弈，Nim和(异或)为0则先手必败，SG定理基础
离线算法思想P0中级G-E-7 离线与杂项技巧族已知全部数据后统一求解：CDQ分治/整体二分/莫队等离线框架的基础思想
概率基础P0中级G-C-15 概率族概率公理、古典概型与几何概型，期望DP的理论基础
内置库利用P0中级G-E-3 Python竞赛特性族bisect二分/heapq堆/collections.deque双端队列/itertools排列组合/math.gcd等竞赛常用内置库
lru_cache记忆化P0中级G-E-3 Python竞赛特性族functools.lru_cache(None)装饰器一行实现函数记忆化，递归DP利器
线段树基础P0中级G-A-6 线段树族O(log n)单点修改+区间查询，递归建树合并子节点信息
懒标记线段树P0中级G-A-6 线段树族区间修改+区间查询，lazy tag延迟下发均摊O(log n)
SG函数/Sprague-Grundy定理P0中级G-E-6 博弈论族所有公平组合游戏等价于单堆Nim；SG(x)=mex{SG(后继)}；多子游戏SG值异或得总局面SG；Sprague-Grundy定理：公平组合博弈等价于Nim，SG(x)=mex{SG(后继)}
线性筛(欧拉筛)P0中级G-C-7 数论基础族O(n)筛素数，每个合数只被最小质因子筛一次，可同时求积性函数
字符串哈希P0中级G-C-1 字符串匹配族将字符串映射为多项式哈希值，O(1)比较子串哈希，需双哈希防碰撞
Trie字典树P0中级G-C-2 字典树与AC自动机族树形结构存储多字符串公共前缀，O(L)插入查询，AC自动机与可持久化Trie的基础
P1 · 高频
113 个知识点
AC自动机P1高级G-C-2 字典树与AC自动机族Trie+KMP失配指针，多模式串匹配自动机，O(n+m+z)
反常Nim/Anti-NimP1高级G-E-6 博弈论族misère规则：最后行动者输；反常Nim判定比正常复杂，需分类讨论全1堆与非全1堆
分块数组P1高级G-D-6 分块与根号算法块状数组实现区间修改/查询，块内整体保存散块暴力；将数组分为O(sqrt n)块，块间维护聚合信息
BSGS(大步小步)P1高级G-C-8 数论进阶族O(sqrt(p))求离散对数a^x≡b(mod p)，baby-step giant-step算法
CDQ分治P1高级G-E-7 离线与杂项技巧族分治处理点对问题：三维偏序/DP优化/动态转静态；陈丹琦(IOI2008)提出
分治优化DPP1高级G-A-12 DP优化族决策点单调时利用分治缩小决策空间，O(n log n)
斜率优化DPP1高级G-A-12 DP优化族转移方程化为一次函数，凸壳上二分/单调队列维护最值
最小覆盖圆P1高级G-D-1 凸包族随机增量法 O(期望n) 求覆盖所有点的最小圆(Welzl)
FFT(快速傅里叶变换)P1高级G-C-12 多项式与FFT族O(n log n)计算多项式乘法，基于DFT与蝴蝶操作，NTT为模意义版本
分数规划/01分数规划P1高级G-E-7 离线与杂项技巧族求Σa/Σb极值：二分答案→Σw_i(a_i-mid·b_i)≥0判定；Dinkelbach迭代法
有向图游戏P1高级G-E-6 博弈论族任意有向图(可能有环)上的博弈：逆拓扑/BFS标记胜负平局态，O(m)线性求解
半平面交P1高级G-D-1 凸包族S&I 算法 O(nlogn) 求半平面交，结果为凸多边形
大整数分解P1高级G-C-9 数论高级族合数分解为质因子乘积，Pollard-Rho为主流方法，试除法为基础
Link-Cut TreeP1高级G-D-4 树链剖分与动态树基于 Splay 维护实链剖分，支持动态连断边与路径查询；动态树问题，Splay维护森林路径/子树操作，O(log n)均摊
左偏树(可并堆)P1高级G-A-3 堆与优先队列族支持O(log n)合并的可并堆，利用偏侧树高
李超线段树P1高级G-D-8 高级线段树与离线线段树维护线段/直线集合，标记永久化求横坐标处最值；维护区间最值线段，O(log n)插入线段/O(log n)查询最值；动态线段维护下凸包：线段插入O(log C)、线段插入O(log²C)；2026年有形式化规范论文
莫比乌斯反演P1高级G-C-8 数论进阶族利用莫比乌斯函数mu进行数论反演，将gcd计数问题转化为求和
最近点对P1高级G-D-2 平面扫描与几何求交分治 O(nlogn) 求平面最近点对，合并时按扫描线对检查
NTT(数论变换)P1高级G-C-12 多项式与FFT族模意义下FFT，用原根替代单位根避免浮点误差，998244353为常用模数
珂朵莉树/ODTP1高级G-E-7 离线与杂项技巧族用平衡树维护颜色段均摊：区间赋值操作下split/assign均摊O(log)，起源CF896C；颜色段均摊，随机数据下区间赋值均摊 O(logn)，源自 CF896C
整体二分/并行二分P1高级G-E-7 离线与杂项技巧族多询问一起二分：把操作和询问按答案值域分治，O(T·log n)同时处理所有询问
可持久化 TrieP1高级G-D-5 可持久化数据结构每次只新建被改节点，保留旧版本，支持历史版本字符串查询；保存历史版本的Trie，支持区间异或最值等查询
Pollard-RhoP1高级G-C-9 数论高级族期望O(n^1/4)大整数分解，基于生日悖论与伪随机序列环检测
多项式基础P1高级G-C-12 多项式与FFT族多项式表示、求值、乘法、求导积分，FFT/NTT的前置知识
原根P1高级G-C-8 数论进阶族模p下阶为phi(p)的元素g，NTT与离散对数的基础，最小原根O(sqrt)求解
旋转卡壳P1高级G-D-1 凸包族在凸包上枚举对踵点，O(n) 求凸包直径/最小矩形覆盖
动态开点线段树P1高级G-A-6 线段树族按需创建节点，支持大值域离散化无需预先开空间
线段树合并与分裂P1高级G-A-6 线段树族合并多棵动态开点线段树，用于树上信息合并；按权值线段树合并实现集合操作，分裂还原，用于树上信息合并
线段树分治(离线)P1高级G-D-8 高级线段树与离线将时间轴建成线段树，把只存在于某时段的信息离线分发到节点
空间优化P1高级G-E-7 离线与杂项技巧族滚动数组/bitset压位/信息熵下界/利用数据特性(并查集单数组)等节省内存技巧
Splay(伸展树)P1高级G-A-8 平衡二叉搜索树族伸展操作将访问节点旋至根，均摊O(log n)，LCT基础
后缀数组P1高级G-C-3 后缀结构族SA+rank+height数组，对字符串所有后缀排序，配合LCP做子串统计与匹配
扫描线P1高级G-D-2 平面扫描与几何求交线扫过平面处理事件，求矩形面积并/周长并/二维数点
Treap(树堆)P1高级G-A-8 平衡二叉搜索树族BST+堆随机优先级，旋转维护平衡，期望O(log n)
零和博弈/MinimaxP1高级G-E-6 博弈论族序贯零和：V(s)=max/min{V(后继)}；Minimax+Alpha-Beta剪枝；同时零和：纳什均衡/混合策略
二维几何基础P1基础G-D-3 计算几何基础与度量向量运算/点积叉积/多边形面积/有向面积/线段转直线等基础
缓冲区刷新P1基础G-E-1 IO与常数优化族交互题必须fflush(stdout)；Python用sys.stdout.flush()或print(...,flush=True)
堆排序P1基础G-A-1 排序与基础算法族基于二叉堆的O(n log n)原地排序，不稳定
I/O优化策略P1基础G-E-8 竞赛策略族关闭同步/解除关联/快读快写；Python批量读入；I/O瓶颈识别与优化决策
链表P1基础G-A-10 哈希与链表族节点指针串联，O(1)插入删除，需处理边界
三分法P1基础G-A-1 排序与基础算法族在单峰函数上找极值，O(log n)三分查找；O(log n)求单峰函数极值，基于中点比较缩小区间
均摊分析P1中级G-A-1 排序与基础算法族聚合法/势能法/记账法分析均摊复杂度
A*算法P1中级G-A-14 搜索算法族f=g+h优先队列搜索，可采纳启发函数保证最优性
0-1 BFSP1中级G-B-2 最短路族双端队列处理0/1权边最短路O(V+E)
倍增P1中级G-A-1 排序与基础算法族预处理2^k次幂跳跃，用于ST表/LCA/稀疏表等
bitset压位P1中级G-E-2 位运算族用bitset将O(n^2/64)bitset操作优化，莫队配合bitset加速，bitset集合运算
割边(桥)P1中级G-B-4 连通性族删除后使图不连通的边，DFS+low判定O(V+E)
二叉搜索树基础P1中级G-A-8 平衡二叉搜索树族左<根<右性质，期望O(log n)操作，最坏O(n)退化
笛卡尔树P1中级G-A-9 高级树结构族数组下标BST+值堆性质，单调栈O(n)构建，RMQ转化；键满足 BST、权满足堆性质，可将 RMQ 转为 LCA 实现线性
卡特兰数P1中级G-C-10 组合计数基础族C_n=C(2n,n)/(n+1)，括号序列/二叉树/出栈序列等计数
条件概率P1中级G-C-15 概率族P(A|B)=P(AB)/P(B)，贝叶斯公式与全概率公式
常数优化P1中级G-E-1 IO与常数优化族循环展开、局部性利用、代码布局优化、编译器O2优化等常数级加速技巧
构造题P1中级G-A-1 排序与基础算法族构造满足条件的解，需洞察问题结构
割点(关节点)P1中级G-B-4 连通性族删除后使图不连通的点，DFS+low判定O(V+E)
Dinic最大流P1中级G-B-5 网络流族分层图+多路增广O(V²E)，二分图O(E√V)
计数DPP1中级G-A-11 动态规划基础族利用DP记忆化求计数问题，划分子集不重不漏
DAG上的DPP1中级G-A-11 动态规划基础族有向无环图上的最长/最短路，拓扑序转移
分组背包P1中级G-A-11 动态规划基础族物品分组，每组最多选一件
多重背包P1中级G-A-11 动态规划基础族每件物品有限数量，二进制拆分或单调队列优化
数位DPP1中级G-A-11 动态规划基础族按数位逐位枚举，记忆化记录合法状态，大区间计数
数据结构优化DPP1中级G-A-12 DP优化族用线段树/BIT/平衡树加速转移中的查询/修改操作
DP优化概述P1中级G-A-12 DP优化族利用数据结构/数学性质/状态设计降低DP转移复杂度
概率/期望DPP1中级G-A-11 动态规划基础族概率顺推/期望逆推，可能需高斯消元处理环依赖
状压DPP1中级G-A-11 动态规划基础族集合状态编码为二进制整数，适合小规模状态空间
树上背包P1中级G-A-11 动态规划基础族树形DP+背包结合，依赖关系物品选择
并查集应用P1中级G-D-9 专题(topic 域)扩展域/带权/可撤销并查集与 Kruskal 重构树处理连通性问题
欧拉路/回路P1中级G-B-8 欧拉与哈密顿族判定(度数条件)+Hierholzer算法O(V+E)
表达式求值P1中级G-E-7 离线与杂项技巧族中缀→后缀(逆波兰)→栈求值；表达式树；运算符优先级+双栈法O(n)
快速输出P1中级G-E-1 IO与常数优化族整数快速输出：putchar/fwrite；Python用'\n'.join(map(str,...))批量输出
扩展树状数组P1中级G-A-5 区间查询与分块族差分实现区间修改+区间查询，或双BIT维护不可差分信息
博弈图与必胜必败态P1中级G-E-6 博弈论族博弈图DAG上N态(存在后继P态)/P态(所有后继N态)；O(|V|+|E|)标记所有状态
启发式搜索P1中级G-A-14 搜索算法族估价函数引导分支选择，可行性/最优性剪枝
树链剖分(HLD)P1中级G-B-7 树算法族重链剖分，路径查询/修改O(log²V)，可求LCA；按轻重边将树剖为链，配合线段树 O(log^2 n) 维护路径/子树
哈夫曼树P1中级G-A-3 堆与优先队列族最优前缀编码树，贪心构造，WPL最小
IDA*算法P1中级G-A-14 搜索算法族迭代加深+A*剪枝，限制路径成本而非深度
容斥原理P1中级G-C-11 组合进阶族|A1∪A2∪...|=sum(-1)^k S(k)，多集合并集计数与莫比乌斯反演基础
迭代加深(IDDFS)P1中级G-A-14 搜索算法族逐步增加DFS深度限制，DFS方式实现BFS效果，空间优
Johnson算法P1中级G-B-2 最短路族全源最短路，势能法处理负权，n次Dijkstra O(VElogV)
约瑟夫问题P1中级G-E-7 离线与杂项技巧族n人围圈报数出列：递推f(n,k)=(f(n-1,k)+k)%n，O(n)；大n小k有O(k log n)解法；递推 f(i)=(f(i-1)+m)%i 求 n 人循环报数幸存者
KM算法P1中级G-B-6 二分图与匹配族二分图最大权匹配(Kuhn-Munkres)O(V³)
线性方程组P1中级G-C-14 线性代数族高斯消元求解Ax=b，判断唯一/无穷/无解，异或方程组变体
最小割P1中级G-B-5 网络流族最大流最小割定理转化，s-t最小割=最大流
莫队算法P1中级G-D-7 莫队算法族离线区间询问：排序后双指针移动，O(n√n)处理多类区间查询；离线排序区间询问，块长 sqrt n，O(n sqrt n) 处理可 O(1) 扩展的区间
数值二分P1中级G-C-16 数值方法族二分搜索求方程近似解/极值，实数二分控制精度
可持久化数据结构概念P1中级G-A-7 可持久化数据结构族保存历史版本，部分可持久化vs完全可持久化
Rabin-KarpP1中级G-C-1 字符串匹配族基于滚动哈希的字符串匹配，O(n+m)期望，字符串哈希的匹配应用
随机化技巧P1中级G-E-5 随机化与元启发式族随机覆盖目标元素/随机命中目标集合/随机打乱消除最坏情况，概率上界分析
RMQ 专题P1中级G-D-9 专题(topic 域)区间最值查询：ST 表 O(1)/线段树/±1RMQ 线性预处理
搜索剪枝优化P1中级G-A-14 搜索算法族可行性剪枝/最优性剪枝/搜索顺序优化，减少搜索量
线段相交判定与求交P1中级G-D-2 平面扫描与几何求交跨立实验判两线段是否相交并求交点，几何求交基础
SPFA算法P1中级G-B-2 最短路族Bellman-Ford队列优化，均摊快但最坏O(VE)
根号分块(通用)P1中级G-D-6 分块与根号算法按块长 sqrt(n) 分块，整块维护+散块暴力，O(sqrt n) 操作；O(sqrt n)块内暴力+块间预处理，通用性最强的区间结构
子集枚举P1中级G-E-2 位运算族枚举位掩码所有子集的O(3^n)技巧，子集DP常用
testlib对拍框架P1中级G-E-9 工具链族testlib.h：generator/generator/checker/interactor/validator，标准对拍与出题工具
树的重心P1中级G-B-7 树算法族删除后最大子树最小的节点，分治基础
2-SATP1中级G-B-4 连通性族2-适定性问题，建图+SCC判定可行性与拓扑逆序
Z函数P1中级G-C-1 字符串匹配族Z数组z[i]表示S与S[i..]的最长公共前缀长度，线性构造，可用于匹配与周期判断
P2 · 选学
116 个知识点
15谜题可解性判定P2高级G-E-7 离线与杂项技巧族N-puzzle可解性判定：逆序对数奇偶性+空格行距，不可解则无解；N 数码可解性判据：逆序对奇偶性(奇数阶)或行距+逆序对(偶数阶)
三维几何P2高级G-D-3 计算几何基础与度量三维向量/平面/法向量/多面体体积与表面积，由二维推广
防卡Hash随机化P2高级G-E-5 随机化与元启发式族字符串哈希用随机base/双哈希/随机化seed防止构造数据碰撞攻击
AVL树P2高级G-A-8 平衡二叉搜索树族严格平衡(高度差<=1)，旋转维护
位运算技巧P2高级G-E-2 位运算族Gray码、lowbit(x&-x)、popcount、前导零、位运算交换/去重等进阶技巧
分块链表P2高级G-D-6 分块与根号算法块状链表，链式分块支持插入删除与区间查询；链表+分块混合，支持插入删除的O(sqrt n)区间操作
Boyer-MooreP2高级G-C-1 字符串匹配族基于坏字符与好后缀规则的字符串匹配算法，子线性平均复杂度
Burnside引理P2高级G-C-11 组合进阶族群作用下不等价轨道数=|G|^{-1} sum |Fix(g)|，Polya计数基础
猫树P2高级G-D-6 分块与根号算法分治预处理静态区间，跨越中点的查询 O(1)；分治预处理O(1)静态区间查询，不支持修改
点分治P2高级G-B-7 树算法族重心递归分解，路径统计O(nlogn)
特征多项式P2高级G-C-14 线性代数族det(λI-A)，特征值与Cayley-Hamilton定理，线性递推加速基础
圆与直线/圆求交P2高级G-D-2 平面扫描与几何求交解几何方程求圆与直线、圆与圆交点
连分数P2高级G-C-9 数论高级族实数的有理逼近，渐近分数递推，Pell方程与Stern-Brocot基础
凸包优化(CHT)P2高级G-D-1 凸包族维护下/上凸壳按斜率二分求 DP 转移最值，斜率优化经典
矩阵对角化P2高级G-C-14 线性代数族A=PDP^{-1}，矩阵快速幂优化，特征值分解
狄利克雷卷积P2高级G-C-9 数论高级族数论函数的卷积运算，莫比乌斯反演与杜教筛的理论框架
离散k次根P2高级G-C-8 数论进阶族求x^k≡a(mod p)的解，基于原根将问题转化为离散对数
支配树P2高级G-B-4 连通性族支配关系树结构，Lengauer-Tarjan算法O(Eα(V))
动态DP(DDP)P2高级G-A-13 高级DP族带修改的树上DP，广义矩阵乘法+LCT维护转移矩阵
EGF(指数生成函数)P2高级G-C-13 生成函数族a_n的指数生成函数=sum a_n x^n/n!，标号结构计数工具
Euler Tour TreeP2高级G-D-4 树链剖分与动态树将动态树转为欧拉序上的平衡树区间操作，支持连断边；欧拉序维护动态树，平衡树支持换根/连边/断边
有限状态机P2高级G-E-7 离线与杂项技巧族FSM用于字符串匹配/自动机DP/AC自动机基础，竞赛中处理模式匹配问题
FWT(快速沃尔什变换)P2高级G-C-12 多项式与FFT族O(n log n)计算位运算(and/or/xor)卷积，FFT的位运算推广
生成函数基础P2高级G-C-13 生成函数族形式幂级数基本运算：加乘求导积分复合逆，OGF/EGF的前置
反演变换P2高级G-D-3 计算几何基础与度量圆/直线相切问题经反演简化，保角变换
爬山算法P2高级G-E-5 随机化与元启发式族局部择优启发式搜索，每次在当前最优解附近找更优解；易陷入局部最优，单峰函数有效
整数划分P2高级G-C-11 组合进阶族将n拆为正整数之和的方案数，生成函数与五边形数定理O(n sqrt n)
Kahan求和P2高级G-E-7 离线与杂项技巧族补偿求和法降低浮点累加误差：维护误差补偿变量c，精度接近double但只多一个变量
KD 树P2高级G-D-6 分块与根号算法k 维空间分块树，高效处理 k 维最近邻/范围查询；k维空间分块树，最近邻/矩形查询，O(n^{1-1/k})
k短路P2高级G-B-2 最短路族第k短路径，A*或可并堆方法
格点计数P2高级G-D-3 计算几何基础与度量线段/多边形内整点计数，结合皮克定理与整除递推
LTE引理P2高级G-C-9 数论高级族Lift the Exponent引理，求v_p(a^n-b^n)的公式，简化幂次整除问题
线性递推P2高级G-C-12 多项式与FFT族常系数线性齐次递推O(k log k log n)求第n项，BM+NTT+Cayley-Hamilton
Lyndon分解P2高级G-C-6 Lyndon与周期族Duval算法O(n)将字符串分解为字典序递减的Lyndon串，用于最小表示法
矩阵秩P2高级G-C-14 线性代数族高斯消元求矩阵秩，线性无关向量组最大个数
矩阵树定理P2高级G-B-3 生成树族Laplace矩阵行列式求生成树计数
最大平均值区段P2高级G-E-7 离线与杂项技巧族求长度≥L的最大平均值子数组：二分+前缀和判定，分数规划经典应用；Kadane 算法 O(n) 求最大子段和，前缀和+单调队列求限制长度的最大/小子段
最小费用最大流P2高级G-B-5 网络流族SSP算法，SPFA/Dijkstra找最短增广路
最小环P2高级G-B-8 欧拉与哈密顿族图中权值和最小的环，Floyd扩展或无向图方法
最小表示法P2高级G-C-6 Lyndon与周期族O(n)求循环字符串字典序最小的起始位置，基于Lyndon分解或双指针
闵可夫斯基和P2高级G-D-1 凸包族两凸多边形 Minkowski 和仍为凸多边形，用于碰撞检测/半平面并
二维莫队P2高级G-D-7 莫队算法族将莫队扩展到二维矩阵区间询问，分块大小n^(2/3)或n^(3/4)；四方向扩展指针，块长 n^(2/3)，处理矩阵区域询问
莫队+bitsetP2高级G-D-7 莫队算法族bitset 维护状态，莫队转移后位运算加速判定类统计
带修莫队P2高级G-D-7 莫队算法族支持单点修改的莫队：增加时间维，块大小n^(2/3)，复杂度O(n^(5/3))；增加时间维三元组排序，支持单点修改的区间询问
树上莫队P2高级G-D-7 莫队算法族欧拉序将树上路径询问转化为序列区间询问，再用莫队处理；用括号序将树压成序列，对路径询问跑莫队
回滚莫队P2高级G-D-7 莫队算法族不支持删除只支持插入的莫队变体：左右端点同块时暴力，否则只回滚不删除；只增不删，按左端点块排序后回滚，处理难删除的转移
牛顿法P2高级G-C-16 数值方法族O(log log eps)求函数零点，平方收敛，多项式牛顿迭代基础
OGF(普通生成函数)P2高级G-C-13 生成函数族a_n的普通生成函数=sum a_n x^n，组合计数的代数工具
配对堆P2高级G-A-3 堆与优先队列族均摊O(1)插入/O(log n)删除，Fibonacci堆的简单替代
回文自动机(PAM)P2高级G-C-5 回文族存储字符串所有回文子串的最小DFA，O(n)构造，fail链指向最长回文后缀
非公平组合博弈P2高级G-E-6 博弈论族双方可采取行动不同(如棋类)；Conway surreal number理论；较公平博弈复杂，竞赛少见；双方行动集不同的博弈，超实数理论与Surreal Number
可持久化平衡树P2高级G-D-5 可持久化数据结构可持久化无旋转 Treap，函数式节点复用实现历史版本；可持久化无旋Treap，保存历史版本
可持久化分块数组P2高级G-D-5 可持久化数据结构可持久化思想与分块结合，按版本复用块信息
可持久化并查集P2高级G-A-4 并查集族基于可持久化线段树实现历史版本回溯的并查集
可持久化堆P2高级G-D-5 可持久化数据结构可持久化可并堆(左偏树)，常用于 k 短路问题；支持历史版本的堆，基于左偏树实现
点在多边形内判定P2高级G-D-1 凸包族射线法判一般多边形，凸多边形用有序二分 O(logn)
Polya计数P2高级G-C-11 组合进阶族Burnside+置换群下的染色计数，利用循环指标多项式
Prüfer序列P2高级G-B-7 树算法族树与序列双射，标号树计数Cayley公式
二次剩余P2高级G-C-8 数论进阶族求x^2≡a(mod p)的解，Cipolla算法O(log p)，Tonelli-Shanks
随机增量法P2高级G-D-3 计算几何基础与度量按随机序逐点加入并增量维护结构，期望线性复杂度
随机变量P2高级G-C-15 概率族离散/连续随机变量及其分布，概率DP建模工具
单机调度P2高级G-D-10 调度与其他专题单机作业排序使最大延迟/完工时间最优，按截止期贪心
次小生成树P2高级G-B-3 生成树族严格次小生成树，树链最大边替换法
线段并集长度P2高级G-D-2 平面扫描与几何求交扫描线求一维/二维线段并集长度，离散化+区间合并
序列自动机P2高级G-C-4 后缀自动机族next数组记录每个位置后各字符出现位置，O(n|Σ|)构造，子序列匹配自动机
Simpson积分P2高级G-C-16 数值方法族自适应Simpson法数值积分，O(1)抛物线逼近，处理难以解析的积分
模拟退火P2高级G-E-5 随机化与元启发式族以概率e^(-ΔE/T)接受劣解跳出局部最优；初始温度/降温系数/终止温度三参数；卡时技巧clock()；基于Metropolis准则的概率搜索，以一定概率接受劣解逃离局部最优
sqrt 树P2高级G-D-6 分块与根号算法O(n sqrt n) 预处理静态序列，支持结合律运算 O(1) 查询；O(1)静态区间查询，O(sqrt n)重建，分块递归
Steiner树P2高级G-B-3 生成树族给定关键点集最小连通子图，NP-hard，状压DP
斯特林数P2高级G-C-11 组合进阶族第一类(循环排列)与第二类(集合划分)Stirling数，递推与显式公式
后缀自动机(SAM)P2高级G-C-4 后缀自动机族识别字符串所有子串的最小DFA，O(n)在线构造，endpos等价类
后缀树P2高级G-C-3 后缀结构族压缩所有后缀的Trie，Ukkonen算法O(n)在线构造，SA/SAM的等价结构
两圆公切线P2高级G-D-2 平面扫描与几何求交求两圆内外公切线，几何方程或向量构造
三角剖分P2高级G-D-2 平面扫描与几何求交将平面点集细分为三角形，常用耳切与对偶图
范德蒙德卷积P2高级G-C-10 组合计数基础族C(n+m,k)=sum C(n,i)C(m,k-i)，组合恒等式的重要工具
向量空间P2高级G-C-14 线性代数族线性空间、基与维数，线性基与矩阵秩的理论基础
垂直剖分(梯形剖分)P2高级G-D-2 平面扫描与几何求交将平面按线段端点垂直切分为梯形单元，支持点定位与求交
虚树P2高级G-B-7 树算法族关键点集压缩树结构O(klogk)，配合DP
数制转换P2基础G-C-18 大整数与数制族任意进制间转换，除K取余法与大数进制转换
杜教筛P2前沿G-C-9 数论高级族O(n^2/3)求积性函数前缀和，基于Dirichlet卷积与数论分块
广义后缀自动机P2前沿G-C-4 后缀自动机族多字符串的SAM，Trie上建SAM或离线BFS建，支持多串子串查询
单调栈优化DPP2前沿G-E-10 前沿趋势组Pareto frontier单调栈优化转移：双单调性(值递增/DP递减)使内层循环均摊O(1)；2025-12 CF教程
吉司机线段树(Segment Beats)P2前沿G-D-8 高级线段树与离线区间取 min/max 等操作利用势能标记，均摊高效维护复杂区间信息；维护区间最值操作(区间取min/max)与历史最值；区最值操作(chmin/chmax)的懒标记线段树：mapping失败时下传递归，均摊高效
括号序列专题P2中级G-D-9 专题(topic 域)合法括号序列判定/计数/线段树维护匹配(CF380C)
学习资源与刷题路线P2中级G-E-8 竞赛策略族OI Wiki roadmap、CF/AtCoder/Luogu刷题路线、经典教材推荐、进阶学习路径
错排问题P2中级G-C-11 组合进阶族D(n)=n!(1-1/1!+...+(-1)^n/n!)，全排列中无固定点的方案数
距离度量P2中级G-D-3 计算几何基础与度量欧氏/曼哈顿/切比雪夫距离及其变换(切比雪夫↔曼哈顿)
状态设计优化P2中级G-A-12 DP优化族改变状态定义降低维度/状态数，题目特异性优化
编辑器配置P2中级G-E-9 工具链族VSCode/Vim/CLion等编辑器的CP竞赛配置：代码片段、调试、编译任务
字节序P2中级G-E-7 离线与杂项技巧族大端序/小端序差异，网络字节序转换，二进制文件读写时需注意
Git版本管理P2中级G-E-9 工具链族代码模板版本管理、团队协作、代码回溯与备份
格雷码P2中级G-C-18 大整数与数制族相邻二进制仅一位不同，G(i)=i^(i>>1)，汉密尔顿路径应用
交互题策略P2中级G-E-8 竞赛策略族交互次数优化、二分交互、随机撒点、flush时机、STDIO vs Grader交互模式
直线交点P2中级G-D-2 平面扫描与几何求交用叉积判定两直线位置关系并求交点坐标
OJ工具P2中级G-E-9 工具链族在线评测工具、代码提交辅助工具、评测机使用
皮克定理P2中级G-D-3 计算几何基础与度量A=i+b/2-1 关联整点多边形面积与内部/边上格点数
随机打乱防hackP2中级G-E-5 随机化与元启发式族shuffle打乱输入顺序防止构造数据卡哈希/快排；CF hack常见反制手段
Special JudgeP2中级G-E-9 工具链族非唯一解题目的自定义评测器：testlib checker编写，多解/最优解判定
Floyd环检测P2中级G-E-7 离线与杂项技巧族龟兔赛跑算法：快慢指针检测链表/序列环，O(n)O(1)找环起点与周期；Floyd 双指针 O(1) 空间检测链表/序列中的环并定位
P3 · 冷门
49 个知识点
贝尔数P3高级G-C-11 组合进阶族B(n)表示n个元素集合划分的方案数，Stirling数之和，Bell三角形
圆方树P3高级G-B-4 连通性族点双连通缩点为圆方树结构，树上路径查询
上下界网络流P3高级G-B-5 网络流族有容量上下界的可行流/最大流/最小流转化
弦图P3高级G-B-9 图论高级专题完美消除序列(PES)，极大团与色数
DP套DPP3高级G-A-13 高级DP族外层DP的状态是内层DP的结果，状态空间需分析
斐波那契堆P3高级G-A-3 堆与优先队列族均摊O(1)decrease-key，理论最优堆，实现复杂
一般图匹配P3高级G-B-6 二分图与匹配族带花树算法(Blossom)，一般图最大匹配O(V³)
哈密顿路P3高级G-B-8 欧拉与哈密顿族NP-hard，状压DP O(2ⁿn²)
交互题调试P3高级G-E-4 调试与对拍族交互题对拍困难，需模拟交互过程；封装输入输出函数；静态查错能力重要
LGV行列式引理P3高级G-B-9 图论高级专题Lindström-Gessel-Viennot引理，不相交路径计数
最大团P3高级G-B-9 图论高级专题NP-hard，Bron-Kerbosch回溯或状压DP
同余最短路P3高级G-B-2 最短路族利用同余类建图求最小权值，模数优化
平面图P3高级G-B-9 图论高级专题欧拉公式V-E+F=2，对偶图与面着色
Polygon出题平台P3高级G-E-9 工具链族Codeforces Polygon：题目打包、测试数据生成、validator/checker配置
红黑树P3高级G-A-8 平衡二叉搜索树族弱平衡BST，C++ std::map底层，竞赛中少用
截止期限-工期调度P3高级G-D-10 调度与其他专题给定截止期限与工期求最优调度可行性，贪心+堆
树分块P3高级G-A-9 高级树结构族树上Sqrt分块，配合莫队处理树上路径查询
树哈希P3高级G-B-7 树算法族树同构判定，哈希递归子树
AI竞赛编程趋势P3前沿G-E-10 前沿趋势组2026年GrandCode/Solvita等AI系统在CF live round超越人类GM；test-time RL+agentic loop趋势
二叉化树DP TrickP3前沿G-E-10 前沿趋势组多叉树添加虚节点链转为二叉树，使O(n²)树形DP的合并复杂度天然成立；2026 CF Round 1100
位掩码DP优化P3前沿G-E-10 前沿趋势组2^n·n·log(A)位掩码DP+二分搜索求最大化最小值；2026 CF Round 1100 Editorial
初等生成函数P3前沿G-C-13 生成函数族常见序列的生成函数闭式：几何/二项/指数/三角等
欧拉数P3前沿G-C-11 组合进阶族A(n,k)表示排列中恰好k个上升段的个数，Worpitzky恒等式
生成函数平移P3前沿G-C-13 生成函数族指数平移与系数平移技巧，生成函数的高级操作
交互题兴起趋势P3前沿G-E-10 前沿趋势组ICPC 2024-2025 Nanjing连续出袋鼠交互题；NOI/WC系列恢复交互题；交互题成为高频题型
拉格朗日反演P3前沿G-C-12 多项式与FFT族O(n log n)求复合逆的系数，生成函数计数的高级工具
Main-LorentzP3前沿G-C-6 Lyndon与周期族O(n log n)找出字符串所有平方串(重复子串)的出现位置
Min_25筛P3前沿G-C-9 数论高级族O(n^3/4/log n)求积性函数前缀和，基于埃氏筛思想与状态转移
二次离线莫队P3前沿G-D-7 莫队算法族单次转移非 O(1) 时再离线一次，降低整体复杂度
多点求值与插值P3前沿G-C-12 多项式与FFT族O(n log^2 n)多项式多点求值与插值，基于分治与NTT
线段树嵌套(树套树)P3前沿G-D-8 高级线段树与离线seg-in-seg/seg-in-bit/seg-in-balanced 等多维信息维护结构；线段树套线段树/BIT/平衡树，支持二维或多维区间操作
多项式牛顿迭代P3前沿G-C-12 多项式与FFT族O(n log n)求多项式开根/对数/指数/逆，基于牛顿法推广到形式幂级数
佩尔方程P3前沿G-C-9 数论高级族x^2-Dy^2=1的整数解，连分数法求解，最小解递推通项
多项式复合与求逆P3前沿G-C-13 生成函数族O(n log^2 n)多项式复合与复合逆，拉格朗日反演的应用
前缀GCD变化优化P3前沿G-E-10 前沿趋势组前缀GCD至多变化O(log A)次，利用此性质将O(n²)优化到O(n log A)；2026 CF Insomnia'26
最优原地后缀数组P3前沿G-C-3 后缀结构族线性时间O(n)且O(1)额外空间构造后缀数组的变体(SA-IS等)
后缀平衡树P3前沿G-C-3 后缀结构族用平衡BST维护后缀排序，支持动态插入删除字符的后缀结构
符号化方法P3前沿G-C-13 生成函数族组合类到生成函数的系统化映射(SEQ/SET/MSET等构造子)
Top TreeP3前沿G-D-4 树链剖分与动态树Self-Adjusting Top Tree 维护完全动态森林的路径与子树信息；维护树上层和路径信息的通用框架，LCT的扩展
平衡三进制P3中级G-C-18 大整数与数制族用{-1,0,1}表示的三进制，无符号位自然表示负数
随机化堆P3中级G-A-3 堆与优先队列族随机合并的可并堆，期望O(log n)
TimsortP3中级G-A-1 排序与基础算法族归并+插入混合稳定排序，Python/Java标准库使用
锦标赛排序P3中级G-A-1 排序与基础算法族基于锦标赛树的排序，O(n log n)