admin 的博客
CSP-S自查表
admin SU @ 2026-10-10 1:01:52

CSP-S / NOIP 提高组知识自查表

提高级知识、复杂度与实现检查

示例基线：C++14（-O2 -std=c++14 -static），以当年比赛公告为准。

使用说明：按知识点检查适用条件、正确实现及时间、空间复杂度，并用边界数据或反例验证。星号说明：带 * 的内容不属于提高级大纲的知识类别，属于 NOI 级或补充内容；提高级类别下的常见实现、变体和应用不标星。

章节	内容
1	C++ 语言与实现
2	基础算法与问题求解
3	字符串
4	数据结构
5	图论
6	树论
7	动态规划
8	数学
9	算法复杂度索引
10	空间复杂度与内存估算
11	时间复杂度估算基准
12	* C++ 未定义行为与实现风险
13	* 对拍与差分测试
14	* NP、NP 完全与 NP-hard 识别
15	能力缺口与复习重点
—	创作声明与许可

1 C++ 语言与实现

知识点	适用范围与要点	掌握要求
整数类型范围与溢出	乘法、平方及累计值可能超过 $2^{31}-1$ 时需要扩大类型。两个 `int` 的乘法在赋值给 `long long` 之前已经按 `int` 计算；比例乘积、平方和及组合数递推均需检查中间值。	写非负数版安全乘法 `mul_ok(a,b,limit)`：先处理 `a==0`，并在 $0\le a,b\le limit$ 时判断 `b<=limit/a`；任意有符号输入需完整分情况，或用 `__int128` 检查中间值。
整数除法、取模与模运算陷阱	整除、向上取整与负数取模需要明确符号和边界；C++14 的整数除法向零取整，余数与被除数同号。模减法应先将操作数归一化；仅在中间值不溢出时可写 `(a-b+MOD)%MOD`。两个 `int` 相乘后取模可用 `1LLab%MOD`，任意64 位因子则需 `__int128` 或安全乘法。	实现分数加法输出最简分数并检查中间溢出；求组合数取模时，区分质数模下阶乘逆元法的适用条件，以及合数模下按规模选择杨辉递推、质因数分解与CRT 等方法。
浮点误差与精确比较	概率、期望DP 中使用浮点传递通常合理；几何相交判定能改写为整数运算时，应优先使用平方距离、叉积等精确式。浮点比较需按题目误差要求和数值量级选择绝对/相对容差，不能把固定的 `1e-8` 当作通用规则。	写结合绝对误差与相对误差的比较函数，并在几何谓词中统一 `eps` 的符号约定；实现整数二分 `isqrt(n)`，或用 `sqrt` 给出初值后再以整数比较修正。
数组、字符串与解析	字符串题需要精确逐字符处理。`stoi` 不检查前导零，解析题（IP 地址、表达式格式）必须实现解析器。读一整行用 `getline`，注意 `cin>>` 后接 `getline` 会读到空串。	实现解析器：读入格式串严格拒绝空段、前导零、越界值；对比 `stoi` 的行为差异。
文件输入输出	题面要求使用指定文件时，可用 `freopen("name.in","r",stdin)` 和 `freopen("name.out","w",stdout)` 重定向标准流，之后仍使用 `cin/cout`；也可用 `ifstream/ofstream` 直接打开文件。文件名、扩展名和大小写必须完全一致，源码不得依赖本机绝对路径。	能分别用 `freopen` 和 `ifstream/ofstream` 完成文件读写；能说明 `"r"`、`"w"` 与 `stdin`、`stdout` 的对应关系；提交前在独立目录按正式文件名复测，并确认输出中没有调试信息。
递归与调用栈	树深度达到 $3\times10^5$ 到 $5\times10^5$ 时，默认栈空间通常不足。正式程序应使用迭代或显式栈；仅在评测环境允许且限制明确时调整栈上限。	写链上DFS 的递归版和显式栈版，在 $n=10^5$ 的链上测试递归版是否崩溃。
STL 容器与迭代器	`priority_queue`（默认大根堆，Dijkstra 需改比较器）、`set/multiset`（有序且去重/不去重，赛道修建式配对）、`map`（值域大替代数组）、`bitset`（位运算加速、状压 DP）、`vector` 扩容导致迭代器失效。	写Dijkstra 用最小堆；对 `multiset` 用 `lower_bound` 找配对元素；解释 `erase(val)` vs `erase(iter)` 的区别。
运算符优先级与位运算	`&`、`	`和异或运算符的优先级低于、`!=`，故` if (x&10)`不表示最低位判定。移位量必须满足 $0\le k<$ 左操作数提升后的位宽，否则为UB；构造位掩码时优先使用无符号类型，如`1ULL<<k`，并特判 $k=64$ 。
C++14 版本与编译选项	以 `-std=c++14` 为基线。`std::gcd`（C++17）、结构化绑定（C++17）不可用。`__int128` 是GCC 扩展，可用于中间计算；标准流没有直接的 `<<`、`>>` 重载，十进制输入输出需手写转换。	用 `g++ -std=c++14 -O2 -static` 编译代码；确认未使用C++17 特性。
Linux、计时与调试工具	常见Linux 命令、文本编辑工具、`g++` 选项、`time` 和GDB 可用于定位CE、RE、TLE、栈溢出、越界及首个错误状态。	能用 `pwd/ls/cd/cp/mv`、`time ./sol < in`、`g++ -g -O0` 与GDB 的 `run/break/next/print/bt` 完成一次崩溃定位；再用正式 `-O2 -std=c++14 -static` 复测。
STL 与算法模板库	掌握 `pair/tuple`、`set/multiset`、`map/multimap`、`deque`、`priority_queue`、`bitset` 及迭代器，并掌握 `sort/stable_sort/lower_bound/upper_bound/nth_element`。容器操作复杂度与迭代器失效规则需要同时核对。	给每个容器写出插入、查询、删除的典型复杂度；不用C++17 结构化绑定遍历 `map`；构造一个比较器不满足严格弱序的反例。
引用、指针、结构体与对象生命周期	递归邻接表、数组传参、结构体排序和动态分配会涉及引用/指针；悬空引用、未初始化指针和越界访问会直接产生UB。	写一个接收 `const vector<int>&` 的函数并解释为何避免复制；指出返回局部变量地址、`vector` 扩容后继续使用元素引用这两种错误的生命周期问题。
类（class）与运算符重载	结构体成员对齐与布局模拟需要理解 `struct` 内存模型。运算符重载用于自定义排序比较或min-plus 矩阵乘法。	写 `struct Mat{long long a[2][2];};` 并重载 `*` 实现min-plus 矩阵乘法；只有两项均非 `INF` 时才计算 $a\_{ik}+b\_{kj}$ ，并保证 `INF` 与有限值上界不会使加法溢出。

2 基础算法与问题求解

知识点	适用范围与要点	掌握要求
模拟与枚举	模拟常用于第一题及部分分，须按题意逐步执行环形移动、日期推进或递归结构生成。子集或位状态枚举常在 $n\le20$ 左右考虑；全排列是 $n!$ 级，通常只适合 $n\le10$ 左右，具体仍需按分支数、常数和时限估算。剪枝影响实际运行量，但不自动改变最坏复杂度。	把日期模拟从“逐日”改为“按月/按年跳”，说明为何能加速并验证历法切换边界。
贪心	贪心规则必须绑定明确的目标与约束，并给出交换论证或数学证明。例如，最大化满足 $x+y\ge T$ 的不交配对数时，可处理当前最小值 $x$ ：若存在搭档，则取最小的可行 $y$ ；否则丢弃 $x$ 。调度问题也需明确作业时长、依赖关系和优化目标。	对区间最少点覆盖证明“按右端点排序选右端点”正确，并构造“按左端点贪心”的反例；为配对规则写出无可行搭档时的处理及交换论证。
* 贡献计算	把总答案拆成每个元素、位置、边或区间的独立贡献求和：$\mathrm{ans}=\sum\_i\mathrm{val}\_i\times\mathrm{count}\_i$。常见场景：所有子数组的max/min/sum 之和、每个结点对多少条路径有贡献。配合单调栈求左右边界、前缀和、差分等手段，常能把 $O(n^2)$ 降到 $O(n)$ 。	用单调栈求每个元素作为最大值的左右边界；重复值须固定一侧严格、另一侧非严格，使每个子数组唯一归属，再用全相等数组验证；推导所有子数组元素和中 $a\_i$ 的出现次数。
二分答案	“最大化最小值”或“最小化最大值”的默认框架。判定函数必须满足单调性。典型场景：二分赛道长度、完成天数或花费。整数二分轮数为 $\lceil\log\_2(\text{答案区间长度}+1)\rceil$ ；32 位范围约30余轮，64 位范围约60余轮。	写出整数二分模板（闭区间不变量），解释中值取 `l+(r-l+1)/2` vs `l+(r-l)/2` 的场景差异，处理无解和全可行边界。
* 三分查找	目标函数需满足所用模板要求的严格单峰/单谷，或另行证明等值平台下的舍弃规则仍保留至少一个最优点。整数三分收缩到常数长度后枚举；实数迭代次数由初始区间和目标误差决定。最优值平台可以妥善处理，但上升段或下降段中的等值区间、多个分离局部极值都可能破坏简单舍弃规则。	写整数三分并明确等号分支；分别构造“最优平台仍可处理”和“非严格形状导致错误舍弃”的例子；说明不满足模板单峰性时为何失败。
前缀和、差分与树上差分	前缀和 $O(1)$ 回答区间和；差分 $O(1)$ 区间加法最后扫描还原。树上差分：点差分在 $u,v$ 处加 $1$ ，在 $\operatorname{LCA}(u,v)$ 处减 $1$ ，在 $\operatorname{parent}(\operatorname{LCA}(u,v))$ 处减 $1$ ；边差分在 $u,v$ 处加 $1$ ，在 $\operatorname{LCA}(u,v)$ 处减 $2$ 。	在树上实现点差分和边差分的DFS 还原，构造一条路径验证每个点/边的统计次数。
双指针、滑动窗口、单调队列	双指针与滑动窗口要求端点移动具有可维护的单调性；单调队列用于区间最值，每个元素至多入队、出队一次，因而总计均摊 $O(n)$ 。三队列替代优先队列只适用于特定模型：初始序列有序、每次取出的值保持单调，且两种生成变换分别保持各自产生序列单调。	为滑动窗口证明端点不回退；在三队列模型中逐项证明三个队列的单调性，并说明任一前提破坏后为何不能替代堆。
离散化	值域很大但有效值较少时可离散化。离线流程为 `sort+unique+lower_bound`；静态编号不能随意插入新坐标而保持原秩，在线新坐标应改用有序映射、动态开点结构或可重构方案。	写离线收集所有坐标 $\to$ 排序去重 $\to$ `lower_bound` 映射的完整代码，验证映射后索引范围。
扫描线	把区间或矩形的开始、结束变成按坐标排序的事件，扫描时用计数器、堆、BIT 或线段树维护活动集合。必须规定同坐标事件顺序及闭区间/半开区间语义。仅对离散整数闭区间，且 `r+1` 不溢出时，才可把 $[l,r]$ 写成 $(l,+1),(r+1,-1)$ 。	分别处理离散整数与连续坐标的区间重叠；写矩形面积并时，先用当前覆盖长度累计 $[x\_{prev},x)$ 的面积，再批量应用坐标为 $x$ 的全部事件。
分治算法	归并排序与逆序对把序列递归分成两半并在线性合并时统计跨区间贡献；CDQ 通常按下标或时间分治并统计跨半贡献。整体二分则递归划分答案域，依据单调判定把操作与询问稳定分流，不能与“只统计跨区间贡献”混为同一模板。	实现归并排序并统计逆序对；分别写出CDQ 的分治维度和跨区间贡献，以及整体二分的答案域、单调判定和事件分流不变量。
经典排序与稳定性	需要掌握归并、快速、堆、计数/桶和基数排序。比较模型下排序的最坏比较次数下界为 $\Omega(n\log n)$ ；归并、堆排序与标准要求下的 `std::sort` 可达 $O(n\log n)$ ，朴素快速排序最坏仍为 $O(n^2)$ 。计数/桶/基数排序依赖键和值域。	独立写归并排序、堆排序、计数/桶排序与LSD 基数排序；说明稳定性、额外空间和值域条件，并构造全相等或已有序输入检查快排退化。
搜索、剪枝与记忆化	DFS/BFS 是暴力和部分分基础；剪枝必须保持正确性，记忆化状态必须足以决定后续。双向BFS 与按深度迭代加深通常面向无权或等权状态图；有向图的反向搜索还必须能生成前驱。A* 树搜索用可采纳启发函数可保证最优；图搜索若永久关闭结点而不重开，通常还需一致启发函数。	写朴素DFS、可证明剪枝和记忆化版本并分析最坏复杂度；实现双向BFS 与IDDFS；分别说明A* 中“可采纳”“一致”和“允许重开”的作用。
* 折半搜索 (Meet in the Middle)	$n$ 的上限约为 $30$ 到 $40$ 且 $2^n$ 太大但 $2^{n/2}$ 可接受时使用。将元素集均分为两半，分别枚举所有子集并排序，再对一侧的每种状态在另一侧二分/双指针找最优配对。典型场景： $n\le40$ 的四景点选择和、子集和等于目标值。	写“ $n$ 个数选若干使和恰好为 $K$ 的方案数”的折半搜索版（ $n\le40$ ），枚举前 $n/2$ 和后 $n/2$ 各自所有子集和，排序后用双指针合并计数。
倍增	树上跳 $k$ 级祖先（LCA 预处理）、树路径 min-plus 矩阵倍增合并、DP 矩阵倍增。核心是把 $k$ 按二进制拆位，每次合并两段 $2^{j-1}$ 的结果。	写出 $\operatorname{up}[j][v]=\operatorname{up}[j-1][\operatorname{up}[j-1][v]]$ 转移式；实现LCA 查询。
复杂度分析	不只看循环嵌套层数，还要分析：每个元素被处理的总次数（均摊）；分层图DP 状态数 $N\times K$ ；线段树每次 $O(\log n)$ 的总操作数；递归/分治的主定理。	分析分层DP $O(K(N+M))$ 在 $K=50,\ N=10^5$ 时的可行性；对比 $O(n\log n+m)$ vs $O(m\log n)$ 的适用场景。
* 部分分与测试点设计	测试点表通常按规模、固定参数、图结构或数值性质分组。部分分方案应分别利用 $n$ 的上限约为 $10$ 到 $20$ 、 $m=0$ 、 $K=0$ 、 $k=1$ 、链结构、全正数或小值域等条件，并计算各组覆盖范围。	仅根据数据范围表列出各档测试点可用的算法、时间复杂度、空间复杂度及分值并集。
* 边界数据构造	提高组关键边界：零权边/环、 $k=64$ 移位 UB、同值破平规则、严格vs 非严格不等式、 $k\_i\in\{0,1\}$ 的概率边界。全相等/全负/退化树链/稠密图/最大值边界也需要覆盖。	为廊桥分配式问题构造“所有事件同时到达”的数据；为策略游戏式问题构造“A 区间全正且 B 区间全负”的符号边界。
* 循环不变量与正确性	循环或递归应有明确的不变量。DP 需要区分“前 $i$ 个”与“以 $i$ 结尾”等状态语义；贪心需要交换论证；二分需要固定开闭区间及循环前后的边界含义。	为核心循环注明进入条件与结束后的变量含义；为DP 状态写出完整定义，并据此推导初始化、转移和答案位置。

3 字符串

知识点	适用范围与要点	掌握要求
字符串解析与格式转化	适用于复杂度格式、IP/端口及类型定义等结构化文本。解析过程需要处理分段数量、前导零、值域和非法字符；`stoi` 不能代替完整的格式校验。	实现表示 $O(n^{100})$ 与 $O(1)$ 的格式解析，分别得到指数100 与0，并拒绝字段缺失或指数格式非法的输入。
* 栈规约（相邻消除）	删除相邻相同字符的最终规约结果唯一。子串可完全消除 $\Longleftrightarrow$ 两端前缀规约状态相同。可用精确状态编号（每节点至多 $\lvert\Sigma\rvert$ 条子边）替代哈希，规避碰撞风险。	证明“规约唯一性”（无论删除顺序如何，最终结果相同），用所有长度 $\le10$ 的三字符串穷举验证。
Trie（前缀树）	大量字符串的前缀查询、字典维护。字符集大小决定节点空间（ $\lvert\Sigma\rvert$ 乘以节点数）。数组式 `nxt[node][c]` 比指针式更紧凑，但要注意 $\lvert\Sigma\rvert$ （小写26、扩展可能更大）。	用数组写Trie，支持插入、精确查找、前缀计数；估算 $10^5$ 个总长 $5\times10^6$ 的字符串在26 元字符集下的内存。
字符串哈希	快速比较子串相等。约定半开区间 $[l,r)$ ：$\operatorname{hash}(l,r)=H[r]-H[l]\times\mathrm{base}^{r-l}$。双模只能降低碰撞概率，仍是概率算法；需要确定性保证时，应使用精确状态编号、后缀数组/LCP、直接比较或其他无碰撞结构。	推导哈希公式；根据实际比较次数估计生日碰撞风险，不能只看字符串长度下结论；实现双模哈希并说明它仍是概率算法。
KMP / Z-algorithm	KMP 是线性匹配算法；前缀函数 $\pi[i]$ 表示最长相等真前后缀。若 $p=n-\pi[n-1]$ 且 $n\bmod p=0$ ，则 $p$ 是最短循环节长度。Z-algorithm 求每个后缀与原串的LCP，也是重复段分析的常用工具。	实现KMP 求前缀函数和匹配；实现 Z-algorithm；对比两者在重复段检测场景的适用性。
Manacher（马拉车）	在线性时间内求以每个中心为中心的最长奇/偶回文半径，进而统计回文子串、求最长回文或回答离线回文判定。哨兵改造串时必须明确原下标与新下标的映射。	分别实现奇偶半径版或统一插入分隔符版；用空串、单字符、全相同和偶长度回文检查边界，并说明为何总扩展次数为 $O(n)$ 。
* 扩展KMP / ExKMP	先求模式串的Z 数组，再在线性时间求文本每个后缀与模式串的LCP（extend 数组）；适合批量前缀匹配、边界比较和重复结构。	实现Z 与extend 两阶段，解释当前最右匹配盒的复用；用模式比文本长、全相同和无匹配数据验证 $O(n+m)$ 时间、 $O(n+m)$ 空间。
*AC 自动机	Trie 上建立失败指针，把多模式匹配转成自动机遍历。定长数组补全转移时构建和空间为 $O(S\lvert\Sigma\rvert)$ ，匹配 $O(T+\mathrm{occ})$ ；稀疏边可降空间，但转移查询复杂度取决于映射与缓存。	实现BFS 建fail、沿fail 树累计出现次数；说明重复模式、一个模式是另一个后缀、字符集过大时数组转移的空间处理。
* 后缀数组与 LCP	倍增排序构造SA 常为 $O(n\log n)$ ，Kasai 求 height/LCP 为 $O(n)$ ；适合后缀排序、最长重复子串和结合RMQ 的后缀LCP。	实现倍增SA（计数排序优化可保持 $O(n\log n)$ ）与height；用全相同、严格递增字符和重复前缀检查排名、下标和哨兵边界。
括号序列与语法DP	规范化区间DP 的核心：枚举“第一个原子括号块的右括号”作为唯一分割点，消除同一串的多种语法推导导致的重复计数。将所有中间状态（ $SAS$ 、 $A+S$ 等）写成互斥类。	构造一个会被“枚举任意 $AB$ 分割”重复计数的括号串，说明首原子规范化为何唯一。

4 数据结构

知识点	适用范围与要点	掌握要求
栈、队列、双端队列	BFS（队列）、括号/表达式解析（栈）、0-1 BFS（deque）、滑动窗口最值（单调队列）。元素最多进出一次是均摊核心。	分别用“留一个空位”和“额外维护 `size`”实现循环队列，并解释两种方案如何区分空与满。
堆与优先队列	Dijkstra 取最小距离、逆序调度取最大截期、多路归并取最大。默认大根堆，最小堆需改比较器。Dijkstra 中同一点可能入堆多次，旧状态必须跳过（懒删除）。	写Dijkstra 的懒删除堆；实现逆序调度：维护叶子集合，每轮取截期最大的安排到最后。
并查集	用于连通性判定、逆序加边或加点、带权关系和奇偶约束。二倍点并查集可表示 $x\oplus y=1$ 等否定关系，也可用于缩点后的分量维护。	实现带路径压缩的 `find` 和按大小合并的 `merge`；实现二倍点并查集，并说明变量 $x$ 与 $\lnot x$ 属于同一集合时所表示的矛盾关系；掌握删边问题的离线时间倒流：先加入最终保留的边，再逆序把删边还原为加边，记录查询答案后按原顺序输出。
树的孩子兄弟表示法	用“第一个孩子与下一个兄弟”把任意有根树表示成二叉树，适合递归结构、语法树和只允许二叉指针字段的存储；它不是原树的左右儿子。	将一棵每个点儿子数不同的有根树转换为孩子兄弟表示，再还原儿子列表；说明空间 $O(n)$ 、遍历仍为 $O(n)$ 。
树状数组（Fenwick）	单点修改与前缀和查询。维护非负频次时，前缀和单调，BIT 上二分可查找满足前缀和至少为 $k$ 的最小位置；若更新后可能出现负频次，该二分不再保证正确。区间修改需结合差分技巧。	实现 `add/sum`；在所有频次非负且总数不少于 $k$ 时实现BIT 二分；用BIT 模拟序列删除与追加。
线段树	区间最值、区间和与区间修改常用线段树和懒标记。常见1-based递归堆式编号可开约 $4n$ 保证安全；迭代线段树等其他布局可以使用约 $2n$ 。懒标记必须在访问依赖子结点真实信息前下传。	实现区间加与区间和；在线段树上找第一个位置时，证明结点聚合信息能判定整段中是否可能有答案，只有可剪枝谓词才能保证对数级定位。
ST 表（稀疏表）	静态RMQ，预处理 $O(n\log n)$ 、查询 $O(1)$ 、不支持修改。常用于区间min/max 预处理后 $O(1)$ 回答大量询问。	实现ST 表，解释 $\log\_2$ 预处理和查询时两段重叠覆盖的原理（重叠不影响 min/max 的幂等性）。
哈希表与冲突处理	会构造整数、字符串、复合键哈希；理解拉链法和开放寻址。`unordered_map` 查找期望 $O(1)$ 、最坏 $O(n)$ ，需要最坏保证或键值可离散化时改用数组/排序/`map`。	实现拉链哈希或开放寻址表；给出装载因子、扩容、删除标记的处理；构造大量同桶键并解释为何不能把期望复杂度写成最坏保证。
单调队列/ 单调栈	单调队列用于固定窗口最值和具有区间转移窗口的DP。单调栈可求每个元素左右第一个更大或更小的位置，并统计它作为区间最值的次数；重复值必须固定一侧严格、另一侧非严格。三队列替代堆是依赖生成序列单调性的题型特例。	实现滑动窗口最大值；用全相等数组验证“所有子数组最小值之和”中严格/非严格边界的唯一归属；单独证明三队列模型的单调性。
* 分块、块状链表与莫队	分块、块状链表和离线处理适用于需要灵活维护序列或静态区间询问的场景。序列按约 $B\approx\sqrt{n}$ 划块，单点修改、区间查询常做到 $O(1)$ 与 $O(\sqrt{n})$ 的组合；块状链表用块内数组和分裂/重构支持插入；莫队把静态区间询问离线排序，通过四个端点移动维护答案。	写静态莫队并证明端点移动为 $O((n+q)\sqrt{n})$ 量级；写块状链表的定位、插入和超长块重构，给出典型均摊 $O(\sqrt{n})$ ；说明莫队不能直接处理在线询问，带修改版本还需时间维。
* 可持久化线段树	每次修改只复制根到叶路径，旧版本结点不变；主席树用前缀版本差回答静态区间第 $k$ 小。离散化后预处理常为 $O(n\log V)$ 时间和空间，查询 $O(\log V)$ 。	写版本根数组和动态开点，检查结点池上界约 $(n+q)(\log V+1)$ ；解释查询 $[l,r]$ 为什么使用版本 $\operatorname{root}[r]-\operatorname{root}[l-1]$ 的计数差。
* 左偏树/ 可合并堆	在保持堆序的同时维护零路径长，使两堆合并沿右链递归；合并、插入、删除堆顶为 $O(\log n)$ ，空间 $O(n)$ 。	实现 `merge(x,y)`，在交换左右儿子后更新距离；构造大量单点堆连续合并并核对堆序和父子关系。
笛卡尔树	同时满足下标的二叉搜索树性质和值的堆性质；单调栈 $O(n)$ 建树。可把区间最值的递归分治结构显式化。相等值时的优先规则必须固定，否则树形不唯一。	用单调栈建最小笛卡尔树，验证中序遍历还原原下标序列、父值不大于子值；写出 $O(n)$ 时间和 $O(n)$ 空间分析。
平衡树/ 有序集合	`std::set/multiset` 用于动态有序集合，配对问题常使用 `lower_bound`。AVL、Treap、Splay 可用于实现排名、第 $k$ 小或自定义聚合信息；仅需有序集合操作时可使用STL。	用 `multiset` 正确完成重复值配对；再写支持插入、删除一个、排名和第 $k$ 小的旋转Treap，说明期望 $O(\log n)$ 与随机优先级退化风险。

5 图论

知识点	适用范围与要点	掌握要求
图存储与遍历	稀疏图用邻接表/前向星；稠密小图可用邻接矩阵。BFS 在无权图或所有边具有相同非负权值时求最少边数最短路，通常在入队时标记；一般带权图不能直接套用BFS。DFS 注意递归深度；有向图与无向图的建图和判环条件不同。	对有向图和无向图分别写无权BFS 最短路与DFS 判环；用一张带不等边权的图说明普通BFS 为何不能求加权最短路。
建图优化	根据问题真正需要表示的状态、可达关系和路径代价设计图，避免照搬题意连出过多边。常见思路包括删去不影响答案的冗余边、建反图处理逆向可达关系、按阶段或操作次数建立分层图，以及利用虚点、超级源汇、前后缀结点等特殊构图压缩批量关系。优化前后必须保证所需的可达性、路径代价或约束等价。	能估算朴素建图的点数和边数并判断是否超限；能根据问题方向选择原图或反图；能为“至多使用 $k$ 次特殊操作”建立分层图；能用中转结点等特殊构图减少边数，并说明新图与原问题等价。
拓扑排序与 DAG DP	有向无环图（DAG）的线性排序。DAG 上可DP 计数路径数或求最长路。典型场景：函数调用依赖分析、排水系统分流、最短路 DAG 上的路径计数。DAG 反向处理：当操作序列中的函数在DAG 上存在共享子调用时，从序列末尾向前处理，维护“后续乘数累积”以避免指数级展开。	实现Kahn 算法（BFS 维护入度）和 DFS 后序反转两种拓扑排序；在含环图上验证两者都能检测环。写出函数调用问题的反向处理：先拓扑序求每个函数的乘数贡献，再从执行序列末尾向前累加。
单源最短路	Bellman-Ford 为 $O(VE)$ ，可处理负边，并以第 $V$ 轮仍可松弛作为可达负环的判据；堆优化Dijkstra 为 $O((V+E)\log V)$ ，仅适用于非负边；SPFA 的最坏复杂度仍为 $O(VE)$ 。	分别实现Bellman-Ford 与Dijkstra，并以含负边的数据验证Dijkstra 的适用条件。SPFA 的严格负环判定可记录当前最短路边数，或改用Bellman-Ford 的第 $V$ 轮松弛；单个顶点的入队次数不能单独构成证明。
Floyd-Warshall 与传递闭包	$O(V^{3})$ 时间、 $O(V^{2})$ 空间求全源最短路，允许负边。若存在负环，只有满足 $i\leadsto k$ 、 $d[k][k]<0$ 、 $k\leadsto j$ 的点对 $(i,j)$ 没有有限最短路；其他点对仍可正常定义。布尔Floyd 可求传递闭包。	实现Floyd 并把 $k$ 放最外层；相加前判断两段均非INF并防止有限值溢出；根据负对角线与可达性识别受负环影响的点对。
单源次短路	在非负边权图上，双距离Dijkstra 可维护从源点到各点的最短与严格次短walk距离；是否把等长但边序列不同的路线算作“第二条”，以及是否禁止重复点或边，必须由题意确定。第二短简单路径不能直接由通用双距离模板解决。	写非负权图的严格次短walk双距离Dijkstra；构造等长路线检查定义差异，并说明第二短简单路径为何需要其他算法。
0-1 BFS	边权仅为0 或1 时用deque：0 边推前端，1 边推后端。复杂度 $O(V+E)$ ，比 Dijkstra 少一个 $\log$ 因子。不能用于边权含2 或更大的图。	实现0-1 BFS，并与Dijkstra 对比；用含权值2 的数据说明该算法只适用于 0/1 边权。
最小生成树（Kruskal / Prim）	Kruskal（并查集与边排序， $O(E\log E)$ ）适合边表；堆优化Prim 为 $O(E\log V)$ ，邻接矩阵Prim 为 $O(V^{2})$ ，适合稠密小图。图不连通时得到的是最小生成森林，不存在 MST。	实现Kruskal 与两种Prim；检查最终选边数是否为 $V-1$ ；解释负边不影响 MST 正确性。
欧拉道路与欧拉回路	所有边恰走一次。无向图看奇度点数与非零度点连通性；有向图看入度/出度差与弱连通性。Hierholzer 算法 $O(V+E)$ ，必须按边编号标记无向边的两条弧。	写有向、无向两版判定与构造；处理孤立点、重边、自环，最后检查输出边数恰为 $E$ 。
强连通分量（SCC / Tarjan）	有向图的SCC 缩点后得到DAG。用途：零环检测、依赖环压缩和分量级DP；2-SAT 作为更高阶应用单独判断。	实现Tarjan（DFN、LOW 与栈），解释“ $\mathrm{DFN}=\mathrm{LOW}$ 意味着是 SCC 根”；完成缩点并处理重边；在零边子图上检测零环时，分量大小大于1必含环，大小为1还要检查零权自环。
桥、割点与双连通分量	无向图树边 $(u,v)$ 是桥当 $\operatorname{low}[v]>\operatorname{dfn}[u]$ ；非根 $u$ 是割点当存在儿子 $v$ 使 $\operatorname{low}[v]\ge\operatorname{dfn}[u]$ ，DFS 根需至少两个DFS 儿子。重边图必须按边编号跳反向边，不能按父结点跳过全部平行边。	实现桥、割点与边双连通分量缩点；用重边及DFS 根只有一个儿子的数据验证父边和根结点处理；连通图缩点后应得到桥树。
二分图判定	染色法BFS/DFS：相邻点必须不同色。含奇环的图不是二分图。	实现染色法判定二分图；说明为什么含奇环的图不是二分图。
* 二分图最大匹配/ 匈牙利算法	匈牙利增广路算法逐个处理左部点，每次 DFS 寻找增广路，时间 $O(VE)$ 、空间 $O(V+E)$ ；Hopcroft-Karp 为 $O(E\sqrt{V})$ 。根据柯尼希定理，二分图最小点覆盖数等于最大匹配数。	实现DFS 增广，访问标记必须每轮更新；处理非连通图、左右部大小不同与重边；用“ $\text{最大匹配数}=\text{最小点覆盖数}$ ”构造覆盖集合。
*2-SAT	每个布尔变量拆成两个文字，限制转成蕴含边；可满足当且仅当任一变量与其否定不在同一SCC，时间和空间均 $O(V+E)$ 。	把“至少一个”、“至多一个”、“二者相同/不同”分别转成边；Tarjan/Kosaraju 后按SCC 拓扑关系构造一组赋值并验证原约束。
* 最大流/ 最小割	Dinic 用BFS 分层图和DFS 当前弧增广；一般图常用上界 $O(V^{2}E)$ ，空间 $O(V+E)$ 。最大流等于最小割，建模时容量、反向边和无穷容量上界必须可靠。	实现Dinic（每条正向边配反向边），从残量网络找最小割两侧；用64 位容量，构造平行边、零容量边和无法到汇点的情况。
* 最小费用最大流	在残量网络中反复寻找最短费用增广路。SPFA 版每次最短路最坏 $O(VE)$ ；势能配合Dijkstra 在约化费用非负后每次 $O(E\log V)$ 。容量为非负整数且每次至少增广1单位时，增广次数 $A\le F$ 。标准逐次最短增广以当前流在同流量下已最优为不变量；等价判据之一是残量网络中不存在可增广的负费用环。	实现正反边容量与费用互为相反数的建边；若初始或中途不满足最优流不变量，需先做负环消去或改用相应算法；势能Dijkstra 还需可行势能使约化费用非负，并检查不可增广与溢出。
差分约束（Bellman-Ford 应用）	将 $x\_v\le x\_u+w$ 表示为边 $u\to v$ 、权 $w$ ，从而把上界约束转为最短路不等式。加入超级源后，可用Bellman-Ford 或SPFA 求可行解并检测负环；不小于关系应先统一变形，再确定边的方向。	将 $x\_a-x\_b\le c$ 、 $x\_a-x\_b\ge c$ 、 $x\_a=x\_b$ 分别转边；写Bellman-Ford $O(VE)$ 的严格可行性判定，并说明SPFA 最坏仍为 $O(VE)$ 。
* 平面图对偶	在给定平面嵌入的特殊最小割模型中，原图割边可对应对偶图中的环或路径；例如 $s,t$ 位于同一外部面时，可把该面沿 $s,t$ 两段边界拆开，将 $s$ - $t$ 最小割转为一次对偶最短路。多终端推广还必须明确终端所在边界、配对关系与非交叉条件。	在固定嵌入的网格图上标出原边与对偶边，演示同一外部面两终端最小割到对偶最短路的转换；逐项写清多终端推广的前提。

6 树论

知识点	适用范围与要点	掌握要求
树的直径	从任意点找最远点、再从该点找最远点的两次DFS/BFS 方法仅适用于边权非负的树；加权树遍历时需累计距离。树形DP 可处理负权，但必须先规定直径是否允许零条边：若要求两个不同端点，全负树的答案应是最大的一条边。	实现非负权树的两次遍历与任意权树的DP；用含负权边和全负权两组数据验证适用条件及空路径定义。
树的重心	删去重心后所有连通块大小均不超过 $\lfloor n/2\rfloor$ 。快速求删边后两侧子树的重心时，可沿重儿子链倍增定位。树可能有1 或2 个重心，两个时必相邻。	实现找重心（DFS 求子树大小）；实现沿重儿子链下跳，并处理换根后补树大小的变化。
LCA（最近公共祖先）	倍增法预处理 $O(n\log n)$ 、查询 $O(\log n)$ 。用途：路径拆分（上行/下行段分别差分）、树上距离查询、路径DP 矩阵倍增合并。Tarjan 离线LCA 用于批量查询。	实现倍增LCA（`up[k][v]` 表+ 深度数组）；实现树上两点距离查询；对比 Tarjan 离线LCA 的适用场景。
DFS 序与子树操作	子树在DFS 序中是一个连续区间 $\bigl[\operatorname{in}[u],\operatorname{out}[u]\bigr]$，将子树操作转化为区间操作。结合线段树/BIT 维护子树和/子树加。	写DFS 序预处理，实现子树加法与子树求和。
* 树链剖分	重链剖分把整棵树拆成至多 $O(n)$ 条重链；任意根到结点的路径至多跨 $O(\log n)$ 条重链，因而任意两点路径可拆成 $O(\log n)$ 个DFS序区间。配合线段树通常每次路径操作为 $O(\log^2 n)$ ，空间 $O(n)$ 。	实现两遍DFS 的 `size/heavy/top/dfn`，处理路径时每次跳较深链顶；分别验证点权、边权映射以及LCA位置是否应计入。
树上差分	见第2 节“前缀和、差分与树上差分”。提高组核心应用：将玩家路径拆为上行段和下行段，在DFS 过程中用全局桶（进入前记录、退出后求差）统计经过每个结点的路径数。	在树上模拟“多条路径从不同起点到不同终点”的场景，用树上差分与桶统计每个结点被经过的次数。
树形DP	状态为 $f[u][0/1]$ （选/不选 $u$ 时子树的最优值）最为常见。强制条件的加入方式：将禁止状态的DP 初值设为 `INF`。 $u$ 不选 $\to$ 儿子必选； $u$ 选 $\to$ 儿子可选。除 $f[u][0/1]$ 形态外，另一类常见形态是树上背包：以子树为阶段、枚举子树内选取个数或占用容量做合并，见下条。	写树上最小点覆盖DP；加入强制条件（某点必须选/不选）；冲突判断（相邻两点都不选 $\to$ 无解返回 $-1$ ）；掌握树上背包的子树合并写法（见下条）。
树上背包（子树合并）	树形DP 中以子树为阶段，按子树内选取个数或容量合并儿子。典型有依赖背包与按儿子分组的背包。复杂度必须对每次父子合并的有效状态范围求和：倒序枚举用于避免同一组重复使用，本身不会把通用的 $O(nV^2)$ 卷积自动降为 $O(nV)$ 。	实现依赖背包与分组背包；写清已合并大小和儿子子树大小的枚举上界，再对所有合并求和；只有利用子树大小、容量上界或特殊转移结构并完成证明后才能降阶。
* 换根DP（二次扫描）	第一遍DFS 求子树信息，第二遍DFS 从根向下传递父方向的补树信息。用途：求每个点到其他所有点的距离和、删边后补树的重心/直径。	写换根DP 求每个点到其他所有点的距离和。
* 基环树	连通无向图满足 $m=n$ 时恰有一个环。可先拓扑删叶找环，并一次性计算每个环点所挂树的信息，再断环成链，用环上DP、前后缀或滑动窗口合并。枚举删去每条环边并每次重新树DFS 最坏为 $O(n^2)$ ，只适合小环或部分分。	拓扑删叶找环；计算挂树贡献并写一个环上DP；估算逐环边重跑DFS 的最坏复杂度。
树上倍增与矩阵合并	树路径转移可写成 $2\times2$ 或 $3\times3$ 的min-plus矩阵，并按二进制长度倍增合并。矩阵乘法虽有结合律但通常没有交换律，合并路径段时必须保持行进方向；双向路径查询常需分别维护正向、反向乘积。	写出 $k=2$ 时的转移矩阵与min-plus单位矩阵；用两个不交换的矩阵验证合并次序；实现同时维护正向和反向信息的倍增。

7 动态规划

知识点	适用范围与要点	掌握要求
状态定义与初始化	DP 状态必须明确表示“前 $i$ 个”或“以 $i$ 结尾”等范围。求最大值时，不可达状态设为 $-\infty$ ；求最小值时设为 $+\infty$ 。“恰好”与“至多”的初始化不同。	分别写出“恰好 $j$ 次申请”和“至多 $j$ 次申请”的初始化；用全负网格取数验证不可达状态不能初始化为0。
背包DP	0/1 背包（倒序）、完全背包（正序）、多重背包（二进制拆分或单调队列优化）。用途：判定面额冗余（等价货币系统）、计数型背包（选木棍拼多边形）。	写0/1 和完全背包，解释循环方向不同的原因；用单调队列实现多重背包 $O(nC)$ 。
区间DP	枚举长度 $\to$ 枚举左端点 $\to$ 枚举分割点， $n\le500$ 时 $O(n^3)\approx1.25\times10^8$ 。规范化技巧：用“第一个原子块的结束位置”作为唯一分割点，消除同一结果的多条语法推导。	写括号序列的规范化区间DP，设计互斥的状态类别，构造一个会被“任意 $AB$ 分割”重复计数的串。
状态压缩DP	$n$ 的上限约为 $18$ 到 $20$ 常提示 $2^n$ 状态。预处理每对或每组元素对应的覆盖mask；在划分、精确覆盖等具有唯一规范化性质的模型中，可从第一个未覆盖位转移以减少等价顺序，但必须证明不漏解且不重复计数。一般集合覆盖不能仅凭该规则断言每种方案只计算一次。	写状压DP与子集枚举模板；分别在最优化集合覆盖和方案计数中分析最低未覆盖位转移是否安全，以及是否需要额外去重。
树形DP	见第6 节树论。提高组的树形DP 常结合：强制条件INF 设定、子树信息与补树信息合并、路径min-plus 矩阵倍增、子树内配对。	完成“每次询问强制两个结点的状态，求树的最小点覆盖”的 $O(n)$ 暴力DP 实现；实现树上背包的子树合并并分析复杂度；用两次DFS 实现换根DP（如求每个点到其他所有点的距离和）。
* 概率/ 期望 DP	NOIP 2016《换教室》直接涉及基本概率DP，故保留为真题边界。核心是状态含义、全概率分解与期望线性性。	推导完整转移公式（含四种位置组合的概率乘积），与概率为0/1 的确定性版本对比；说明该条来自真题。
分层DP / 多维DP	“不超过最短路加 $K$ ”可按额外代价 $0\ldots K$ 分层；对最短距离有限的边 $u\to v$ ，若不存在使相关最短路无定义的负环，则 $\Delta=\operatorname{dist}[u]+w-\operatorname{dist}[v]\ge0$。层内零增量边可能成环，不能直接按层当作DAG。	写按 $\Delta$ 的分层转移；仅当题目计数允许重复点边的walk，且零环从起点可达、能到终点并落在预算内时，方案数才无穷，并在相关零边子图上用SCC检测。
DP 常用优化	包括滚动数组、前缀最值/前缀和、单调队列、数据结构优化、值域驱动的伪多项式 DP、交换枚举次序消去一维，以及把形如 $\mathrm{dp}\_i=\min\_j(k\_j x\_i+b\_j)$ 的转移改写成直线最值查询。斜率与查询点均单调时可用单调凸包做到总 $O(n)$ ；否则需二分凸包或李超树等结构，不能仍声称 $O(n)$ 。	把一个 $O(nW^{2})$ 窗口转移优化为单调队列 $O(nW)$ ；推导一个斜率优化转移，明确直线斜率、截距、查询横坐标、取 min/max 及相等斜率处理；分别计算优化前后时间与空间。
* 进位/ 逐位组合DP	按二进制位从低到高处理：枚举当前位使用次数 $t$ ，令 $s=\mathrm{carry}+t$ ；当前位对popcount 的贡献为 $s\bmod2$ ，新进位为 $\lfloor s/2\rfloor$ 。每步乘组合数 $C(n-j,t)$ 和权值的 $t$ 次幂。	推演小规模进位DP 的全过程并与枚举结果对照；解释处理完最高位后仍需计入最终进位popcount 的原因。

8 数学

知识点	适用范围与要点	掌握要求
基本运算与边界	max/min、绝对值和向上取整都需检查边界；`abs(INT_MIN)` 因结果不能由 `int` 表示而产生UB。快速幂需处理指数0与底数0。用除法预判乘法溢出时必须先限定符号：在 $0\le a,b\le limit$ 下先处理 `a==0`，再判断 `b<=limit/a`。	先转到足够宽的有符号类型再取绝对值；一般用商余数处理有符号向上取整；分别实现非负数与任意有符号数的乘法溢出检查。
位运算	格雷码公式 $g=k\oplus(k\gg1)$ ；位集合分析 $2^{k-\lvert S\rvert}-n$ ；`1ULL << k` 在 $k=64$ 时是UB，必须特判。popcount 用 `__builtin_popcountll`。	用无符号类型写popcount与lowbit，避免对最小有符号整数取负产生UB；枚举子集；写出 $k=64$ 时安全表示或处理 $2^{64}$ 的方法。
质数筛法（埃氏筛 / 线性筛）	批量筛质数。埃氏筛 $O(n\log\log n)$ 简单快速；线性筛 $O(n)$ 同时维护最小质因子用于 $O(\log x)$ 质因数分解。含特定数码因数的倍数筛法（调和级筛）用于预处理后继合法数。	实现线性筛（维护 `prime[]` 和 `lp[x]`），解释 `i%prime[j]==0` 时break 的原因。
因数分解与约数个数	若 $n=\prod\_i p\_i^{a\_i}$ ，正约数个数 $\tau(n)=\prod\_i(a\_i+1)$ ，约数和 $\sigma(n)=\prod\_i(1+p\_i+\cdots+p\_i^{a\_i})$ 。试除分解/枚举约数为 $O(\sqrt{n})$ ；批量维护最小质因子后单次分解为 $O(\log n)$ 。约数对在完全平方数处只能计一次。	写枚举全部约数并排序、由质因数分解递归生成约数、求 $\tau(n)$ 和 $\sigma(n)$ ；用 $n=1$ 、完全平方数和大质数验收。
* 整除分块 / 数论分块（阶段补充）	对 $q=\lfloor n/l\rfloor$ ，所有 $i\in[l,\lfloor n/q\rfloor]$ 的 $\lfloor n/i\rfloor$ 相同，因此可按商值段跳跃；不同商只有 $O(\sqrt{n})$ 个。常用于求 $\sum\_i\lfloor n/i\rfloor$ 、整除对计数和带前缀和的分段求和。	写循环 `for(l=1;l<=n;l=r+1) r=n/(n/l)`，证明段数 $O(\sqrt{n})$ 、额外空间 $O(1)$ ；两个或多个 floor 同时出现时，右端点取各自不变区间右端点的最小值。
gcd / exgcd	约分、分数化简。扩展欧几里得 `exgcd(a,b,x,y)` 求 $ax+by=\gcd(a,b)$ 的一组解，进而求模逆元（ $\gcd(a,M)=1$ 时）或解线性同余方程。	实现exgcd；用其求 $a$ 在模 $M$ 下的逆元；计算 $15x\equiv1\pmod{26}$ 。
模运算与快速幂	快速幂为 $O(\log k)$ 。模加减前先归一化操作数并防止中间溢出；`1LLab%MOD` 可安全承接两个有符号 `int` 因子的乘积，任意无符号32位或64位因子仍需核对上界，必要时用 `__int128` 或安全乘法。质数模且预处理范围小于模数时可用阶乘与逆元；合数模不能无条件套费马逆元阶乘法，应按规模选择杨辉递推、质因数分解与CRT等方法。	写快速幂；在质数 $p$ 且 $n<p$ 时预处理阶乘与逆元；解释 $n\ge p$ 或模数合数时失效的原因，并给出一种适用的替代方案。
同余与完全剩余系	模 $m$ 的完全剩余系由 $m$ 个两两不同余的整数构成。	能用“两两不同余”判定一组数是否构成模 $m$ 的完全剩余系。
模逆元与裴蜀定理	模逆元可用费马小定理（模数为质数且数不被模数整除）、exgcd（数与模数互质）或质数模下递推求 $1\ldots n<p$ 的逆元。裴蜀定理说明 $ax+by=\gcd(a,b)$ 有整数解。Frobenius两数结论是：当 $a,b>1$ 且互质时，不能表示成 $ax+by$ （ $x,y$ 为非负整数）的最大非负整数为 $ab-a-b$ 。	证明各种逆元算法的前提；写递推逆元；计算 $a=7,b=11$ 的最大不可由非负系数组合表示的整数，并与允许任意整数系数的裴蜀表示区分。
欧拉函数（Euler $\varphi$ ）、欧拉 / 费马 / 威尔逊定理	$\varphi(n)=n\prod\_{p\mid n}(1-1/p)$ ； $\gcd(a,n)=1$ 时 $a^{\varphi(n)}\equiv1\pmod n$ 。费马小定理是质数模特例。威尔逊定理 $(p-1)!\equiv-1\pmod p$ 当且仅当 $p$ 为质数，但通常不是高效判素算法。	线性筛求 $1\ldots N$ 的 $\varphi$ ；逐条写出定理前提并构造“不互质”、“模数合数”的反例，禁止无条件把指数按 $\varphi(M)$ 取模。
线性同余与中国剩余定理	$ax\equiv b\pmod m$ 有解当且仅当 $\gcd(a,m)\mid b$ ；解模 $m/\gcd(a,m)$ 唯一。互质模数用经典CRT；模数不互质时逐式合并并先检查余数相容，合并的lcm 乘法要防溢出。	用exgcd 解线性同余；实现互质CRT 和非互质扩展合并，构造“无解”、“模数不互质但有解”、“lcm 超64 位”三组边界。
*Lucas 定理（阶段补充）	它是质数模组合数的常见后续；对质数 $p$ ，$C(n,m)\equiv C(n\bmod p,m\bmod p)C(\lfloor n/p\rfloor,\lfloor m/p\rfloor)\pmod p$。预处理 $0\ldots p-1$ 阶乘后，单次 $O(\log\_p n)$ 、空间 $O(p)$ ；只适合 $p$ 可预处理。	实现Lucas 递归/循环，处理某一位 $m\_i>n\_i$ 时答案为0；说明模数合数不能直接使用，扩展Lucas 属另一套质因数分解与 CRT 算法。
* 原根与 BSGS	理解模质数乘法群、元素阶和原根；BSGS 用 meet-in-the-middle 解离散对数 $a^x\equiv b\pmod m$ ，经典互质版本期望 $O(\sqrt{m})$ 时间和空间（哈希表）。	实现互质条件下的BSGS 并处理无解情况；说明哈希复杂度是期望值， $\gcd(a,m)\ne1$ 时需使用扩展BSGS。
多重集合、等价关系与基础计数	会区分集合/多重集合；多重集排列数为 $n!/\prod\_i c\_i!$ 。等价关系必须满足自反、对称、传递，等价类构成划分；并查集正是维护等价类的算法实现。	推导多重集排列/组合的小例子；判断给定关系是否为等价关系并列出等价类；解释为何只满足对称性不能直接用并查集合并。
错排列、圆排列与二项式定理	错排列 $D\_n=(n-1)(D\_{n-1}+D\_{n-2})$ ，也可由容斥推导；互不相同元素的圆排列为 $(n-1)!$ （若镜像也视为相同需另除2，且要处理小 $n$ ）。二项式定理连接组合数、卷积和逐项贡献。	推导错排列递推与 $\sum\_{k=0}^n(-1)^k n!/k!$ ；说明圆排列的“旋转同一”条件；用二项式定理求系数并核对杨辉三角。
容斥原理与卡特兰数	容斥必须明确事件及各阶交集；两集合满足 $\lvert A\cup B\rvert=\lvert A\rvert+\lvert B\rvert-\lvert A\cap B\rvert$，若互斥则交集为0。三集合还需加回三重交集，不能在交集非空时只做一层修正。卡特兰数可计合法括号、栈序列等，但必须先建立双射。	推导 $n$ 对括号的卡特兰数；完整写出三集合容斥公式；为关键边子集容斥列出每个子集的符号和剩余约束。
高斯消元与矩阵运算	需要掌握向量/矩阵概念、向量运算、矩阵加减乘转置、单位/三角/对称矩阵与高斯消元。高斯消元 $O(n^{3})$ 解方程组；实数域选绝对值最大主元，模意义下只对可逆主元求逆。	实现实数与质数模两版高斯消元，区分唯一解/无解/多解；实现普通、min-plus 矩阵乘法和矩阵快速幂，检查维数与单位元。
* 几何与浮点	二维向量叉积可判方向、共线与线段相交；鞋带公式 $O(n)$ 求多边形有向面积，单调链凸包排序 $O(n\log n)$ 、扫描 $O(n)$ 。应先按坐标范围和项数估算差、叉积及累计和的上界；若落入有符号128位范围，须先转为 `__int128` 再做减法和乘法；若仍可能超界，则需大整数或其他精确方法。	实现方向判定、线段相交、鞋带公式和单调链凸包；明确是否保留边界共线点，并按题目坐标上界验证中间差、乘积与累计和。
* 差分不变量与数学转化	对特定“方差”操作，需先证明一次操作如何改变相邻差分，并确定可达序列。目标可写为 $n\sum\_i a\_i^2-(\sum\_i a\_i)^2$ 。把差分逐个插入两端的DP只覆盖具有相应单峰/单谷结构的排列，必须先证明该结构及其符号条件；一般含负差分时不能断言最优排列必为单谷。	证明操作与差分交换的对应；写出方差整数公式；用差分 $(-2,-1,0)$ 检验“最优必为单谷”的断言，并在使用两端插入DP前补全适用条件。
整数开方与判别式	对 $n\ge0$ 求 $\lfloor\sqrt n\rfloor$ 可用整数二分，并以 `mid<=n/mid` 防止平方溢出。一元二次方程需先处理 $a=0$ ；当 $a\ne0$ 时，候选根 $r\_\pm=(-b\pm\sqrt\Delta)/(2a)$ 分别为整数，当且仅当 $\Delta$ 为非负完全平方数且对应分子能被 $2a$ 整除；存在整数根只要求至少一个候选满足。	写整数二分开方；分别实现整数根判定与规范根式输出，覆盖 $a=0$ 、 $\Delta<0$ 、重根、仅一个候选为整数及两个候选都非整数的情况。

9 算法复杂度索引

算法	时间复杂度	空间复杂度	限制与易错点
线性扫描/ 模拟	$O(n)$	$O(1)$ 或 $O(n)$	可行规模取决于单步常数、输入量与内存；注意 I/O 瓶颈。
比较排序（`std::sort`）	$O(n\log n)$	$O(\log n)$ 栈	比较器须满足严格弱序；是否改用计数/基数排序应根据键类型、值域、时限与内存判断。
归并/ 计数/ 基数排序	$O(n\log n)$ / $O(n+A)$ / $O(d(n+B))$	$O(n)$ / $O(A)$ 或 $O(n+A)$ / $O(n+B)$	计数排序要求整数键且依赖值域 $A$ ；稳定实现通常另需输出数组。基数排序依赖位数 $d$ 与基数 $B$ 。
分治/ 扫描线	取决于模型；扫描线常为 $O(n\log n+nT\_{ds})$	常见 $O(n)$	分治复杂度需按递推式计算；扫描线先排序事件，再做 $n$ 次维护结构操作。同坐标事件顺序要固定。
二分答案与判定	整数 $O(\log R\cdot T(n))$ ；实数 $O(\log((r-l)/\varepsilon)\cdot T(n))$	取决于判定	判定必须单调；轮数由整数范围或实数误差决定，不能固定为30到60轮。
前缀和/ 差分	前缀和预处理 $O(n)$ 、区间查询 $O(1)$ ；差分区间修改 $O(1)$ 、最终还原 $O(n)$	$O(n)$	两者解决的问题不同；二维前缀和注意减两遍后加回交集。
双指针/ 滑窗	满足端点单调时 $O(n)$ 均摊	$O(1)$ 或 $O(n)$	左右端点只向一个方向移动，且各自总移动次数为 $O(n)$ 。
单调队列/ 单调栈	$O(n)$ 均摊	$O(n)$	维护结构内部的单调不变量；每个元素至多入队/栈、出队/栈一次。
* 分块/块状链表/静态莫队	常见 $O(\sqrt{n})$ 每次 / $O((n+q)\sqrt{n})$	$O(n+q)$	块长需按 $n,q$ 与操作代价选择；块状链表需控制块大小并适时重构；莫队离线且端点增删要快。
BFS / DFS	$O(V+E)$		标记在入队/入栈时做； $V=3\times10^5$ 注意递归栈。
双向BFS / IDDFS	约 $O(b^{d/2})$ / $O(b^d)$	约 $O(b^{d/2})$ / 搜索栈 $O(d)$ ，保存未展开子结点时 $O(bd)$	只是不含原图存储的典型树状估算；状态重复、分支数和最短性条件会改变实际量。
Bellman-Ford	$O(VE)$	$O(V)$ 或 $O(V+E)$	可处理负边；第 $V$ 轮仍能松弛说明存在从初始源可达的负环。检测全图需加超级源或令全点初距为0。
Dijkstra（堆）	$O((V+E)\log V)$	$O(V+E)$	非负权；懒删除跳过旧堆项。
SPFA	最坏 $O(VE)$	可处理负边；求有限最短路须无从源可达的负环，且不存在稳定的平均复杂度保证。
Floyd	$O(V^{3})$	$O(V^{2})$	$V=300$ 时约有 $2.7\times10^7$ 次状态更新；实际可行规模另估， $k$ 循环必须最外层。
Kruskal	$O(E\log E)$	$O(V+E)$	并查集判环；排序是瓶颈。
Prim（堆/矩阵）	$O(E\log V)$ / $O(V^{2})$	$O(V+E)$ / $O(V^{2})$	前者稀疏图，后者稠密小图。
次短路（双距离）	$O((V+E)\log V)$	$O(V+E)$	双距离Dijkstra 要求非负边权，通常允许重复点或边；先确认严格次短、第二条不同路径以及是否要求简单路径。
欧拉路（Hierholzer）	$O(V+E)$	每条边恰使用一次；无向边按编号配对。
* 匈牙利 / Hopcroft-Karp	$O(VE)$ / $O(E\sqrt{V})$	二分图最大匹配；不是带权 KM。
*2-SAT	$O(V+E)$	文字建蕴含图后求SCC。
*Dinic 最大流	一般上界 $O(V^{2}E)$	实际依网络结构；容量与反向边必须正确。
* 最小费用流（逐次增广）	势能版 $O(VE+A(V+E)\log V)$ ；SPFA 版最坏 $O(AVE)$	$A$ 为增广次数；整数容量且每次至少增广1时 $A\le F$ 。初始费用非负或已有可行势能，且残量网络无相关可达负费用环时，可省略前项 $VE$ ；注意反向边与溢出。
差分约束	增广图上Bellman-Ford $O(VE)$ ；SPFA 最坏 $O(VE)$	统一成 $x\_v\le x\_u+w$ ；加超级源或令全点初距为0后，检测到负环才表示无可行解。
Tarjan（SCC / 桥 / 割点）	$O(V+E)$	根割点特判；重边不能只按父结点跳过。
拓扑排序	仅DAG；入度0 入队。
并查集	均摊 $O(\alpha(n))$	$O(n)$	路径压缩与按秩合并；可维护额外信息。
树状数组（BIT）	$O(\log n)$	按前缀值二分要求前缀和单调，例如各位置频次非负。
线段树	递归堆式常开约 $4n$ ；迭代式常为约 $2n$	布局决定空间；懒标记的 `pushdown` 时机必须正确。
* 可持久化线段树	完整建树 $O(V)$ 或动态空树 $O(1)$ ；修改/查询 $O(\log V)$	完整建树 $O(V+U\log V+P)$ ；动态开点 $O(U\log V+P)$	$U$ 为修改/插入次数， $P$ 为版本数；旧版本不可修改，先估结点池。
ST 表	预处理 $O(n\log n)$ ，查询 $O(1)$	$O(n\log n)$	静态RMQ；不支持修改。
哈希表	期望 $O(1)$ ，最坏 $O(n)$ 每次	$O(n+B)$	装载因子、冲突和恶意键会导致退化。
笛卡尔树	建树 $O(n)$	$O(n)$	单调栈；相等值破平规则要固定。
平衡树	Treap 期望 $O(\log n)$ ；AVL/红黑树单次最坏 $O(\log n)$ ；Splay 均摊 $O(\log n)$	Splay 单次操作最坏可达 $O(n)$ ；不同结构的“期望、最坏、均摊”口径不能混用。
* 左偏树	合并/插入/删顶 $O(\log n)$	维护堆序与零路径长。
离散化	$O(M\log M)$	$O(M)$	$M$ 是收集到的坐标数。
LCA（倍增）	预处理 $O(n\log n)$ ，查询 $O(\log n)$	$O(n\log n)$	先跳到同深度，再一起跳。
* 树链剖分与线段树	预处理 $O(n)$ ，每次 $O(\log^{2} n)$	$O(n)$	点权/边权映射与LCA 是否计入。
树上差分	已知LCA 后， $q$ 次差分更新 $O(q)$ ，DFS 还原 $O(n)$	$O(n)$ ，LCA 结构另计	LCA 的预处理与查询另计；点差分和边差分公式不同。
Trie（数组）	建树 $O(S)$ ，查询 $O(\lvert s\rvert)$	$O(S\lvert\Sigma\rvert)$	字符集大小决定空间。
区间哈希	预处理 $O(L)$ ，查询 $O(1)$	$O(L)$	双模降碰撞率；非绝对证明。
KMP / Z-algorithm	$O(n+m)$ / $O(n)$	$O(m)$ / $O(n)$	匹配过程文本串指针不回退。
Manacher	$O(n)$		奇偶回文和改造串下标映射不能混用。
*ExKMP / AC 自动机	$O(n+m)$ / $O(S\lvert\Sigma\rvert+T+\mathrm{occ})$	$O(n+m)$ / $O(S\lvert\Sigma\rvert)$	AC 稀疏转移可降低字符集空间。
* 后缀数组与 LCP	倍增加计数/基数排序 $O(n\log n)$ ；使用比较排序为 $O(n\log^{2}n)$ ；Kasai $O(n)$	$O(n)$	排名、下标与哨兵边界必须统一。
埃氏筛/ 线性筛	$O(n\log \log n)$ / $O(n)$	线性筛同时维护最小质因子。
gcd / exgcd	$O(\log \min(a, b))$	迭代 $O(1)$ ；递归栈 $O(\log \min(a,b))$	C++14 下 `gcd` 需自行实现；`exgcd` 通常使用递归。
试除分解 / 枚举约数	$O(\sqrt{n})$	$O(1)$ 或 $O(\tau(n))$	完全平方根只计一次； $n=1$ 特判。
* 整除分块	$O(1)$	$r=n/(n/l)$ ；多个 floor 取右端点最小值。
快速幂	$O(\log k)$	底数和指数都可能大；注意取模。
组合数（预处理）	$O(n^2)$ 递推或 $O(n)$ 阶乘与逆元	$O(n^2)$ 或 $O(n)$	阶乘逆元法通常还要求质数模且 $n<p$ 。
*Lucas（质数模）	预处理 $O(p)$ ，查询 $O(\log\_p n)$	$O(p)$	$p$ 必须为质数且小到能预处理。
*BSGS	期望 $O(\sqrt{m})$	$O(\sqrt{m})$	经典版要求互质；哈希存在退化风险。
* 单调链凸包	$O(n\log n)$	$O(n)$	叉积防溢出；共线边界点保留规则必须统一。
斜率优化DP	单调条件下总 $O(n)$ ，一般实现常为 $O(n\log n)$	先推成直线查询；相等斜率、min/max 与查询顺序决定实现。
区间DP	常见 $O(n^3)$ ；部分模型或优化为 $O(n^2)$	常见 $O(n^2)$	按区间数、额外状态维度与每状态转移数重算； $n=500$ 时 $n^3=1.25\times10^8$ 。
状压DP	$O(n^2\cdot2^n)$ 或 $O(n\cdot3^n)$	$O(2^n)$ 或 $O(n\cdot2^n)$	按完整状态维数估算；例如 $\mathrm{dp}[\mathrm{mask}][\mathrm{last}]$ 需要 $O(n\cdot2^n)$ 空间。
树形DP	固定状态常为 $O(n)$	常为 $O(n)$	子树背包合并可能到 $O(n^2)$ 或更高，必须按状态与合并循环重算。
背包DP	$O(nC)$	$O(C)$ 滚动	0/1 倒序、完全正序。
分层图DP	状态/边规模为 $O(KV)$ / $O(K(V+E))$ ；求解复杂度另计	复用原图 $O(V+E+KV)$ ；显式建层 $O(K(V+E))$	DAG/线性DP 可按状态图规模处理；堆Dijkstra 还需乘相应对数。显式建层会复制边。
高斯消元	$O(n^{3})$	$O(n^2)$	普通模高斯消元须在域上进行，竞赛中通常取质数模；只有非零主元可求逆，合数模不能直接照搬。
矩阵快速幂	$O(s^{3}\log n)$	$O(s^2)$	min-plus 半环用于DDP。

10 空间复杂度与内存估算

内存按二进制单位估算：1 MiB = $2^{20}$ 字节，1 GiB = $2^{30}$ 字节。理论元素数为 $\lfloor M/\operatorname{sizeof}(T)\rfloor$ ；主数组占用宜控制在内存限制的约 75% 以内，其余空间留给程序、其他数组、容器与分配器、递归栈和运行库。下表“建议”均为四舍五入后的保守数量级，不代表评测环境的实际可用上限。

限制	总字节	`char`（1B）	`int`（4B）	`long long/double`（8B）	`__int128`（16B）
128 MiB	134,217,728	理论 $1.34\times10^8$ ；建议 $1.0\times10^8$	理论 $3.36\times10^7$ ；建议 $2.5\times10^7$	理论 $1.68\times10^7$ ；建议 $1.25\times10^7$	建议 $6.2\times10^6$
256 MiB	268,435,456	理论 $2.68\times10^8$ ；建议 $2.0\times10^8$	理论 $6.71\times10^7$ ；建议 $5.0\times10^7$	理论 $3.36\times10^7$ ；建议 $2.5\times10^7$	建议 $1.25\times10^7$
512 MiB	536,870,912	理论 $5.37\times10^8$ ；建议 $4.0\times10^8$	理论 $1.34\times10^8$ ；建议 $1.0\times10^8$	理论 $6.71\times10^7$ ；建议 $5.0\times10^7$	建议 $2.5\times10^7$
1 GiB	1,073,741,824	理论 $1.07\times10^9$ ；建议 $8.0\times10^8$	理论 $2.68\times10^8$ ；建议 $2.0\times10^8$	理论 $1.34\times10^8$ ；建议 $1.0\times10^8$	建议 $5.0\times10^7$

$O(n)$ 只描述增长率，不表示内存一定小：线段树若有两组 long long tree[4*n]，主数组就是约 $64n$ 字节；ST 表是 $\operatorname{sizeof}(T)\cdot n(\lfloor\log\_2 n\rfloor+1)$ 字节。
二维方阵要先算 $n^2\operatorname{sizeof}(T)$ 。按 75% 建议值，int 方阵在 128/256/512 MiB/1 GiB 下的 $n$ 约不超过 5000/7000/10000/14000；long long 约不超过 3500/5000/7000/10000。
vector<vector<T>> 还有每行对象和多次分配开销；map/set/unordered_map 每元素远大于键值本身。图要按有向弧数算：无向 $m$ 条边通常存 $2m$ 条弧。
递归栈既可能计入总内存，又常受独立栈上限约束；全局 /BSS、堆和栈都不能假设“免费”。估算时应把主数组、状态数组、邻接表、容器开销和递归栈逐项相加。

11 时间复杂度估算基准

本节只按增长函数换算循环体执行次数；上一节用于查询具体算法的时间和空间复杂度。下表以 $2.5\times10^8$ 和 $9\times10^8$ 次作为两条算术刻度，便于比较数量级，但它们不是跨机器、跨语言或跨算法的“一秒稳定线”和“绝对上限”。实际可行规模必须结合时限、评测机和同类代码实测；随机访存、难预测分支、容器操作、哈希、递归、整数除法、宽整数和多组数据通常会降低吞吐，程度依实现与数据而异。

增长级别	$2.5\times10^8$ 次刻度	$9\times10^8$ 次刻度	说明
$n!$	$n\le11$	$n\le12$	$11!\approx4.0\times10^7$ ， $12!\approx4.8\times10^8$ ；若每排列还做 $O(n)$ 检查，需把乘积重算。
$2^n$	$n\le27$	$n\le29$	$2^{27}\approx1.34\times10^8$ ， $2^{29}\approx5.37\times10^8$ ；只适用于每状态常数工作。
$n\cdot2^n$	$n\le23$	$n\le25$	$23\cdot2^{23}\approx1.93\times10^8$ ， $25\cdot2^{25}\approx8.39\times10^8$ ；空间限制往往先于时间限制。
$n^2\cdot2^n$	$n\le19$	$n\le20$	$19^2\cdot2^{19}\approx1.89\times10^8$ ， $20^2\cdot2^{20}\approx4.19\times10^8$ ， $n=21$ 已超过 $9\times10^8$ 次。
$3^n$	$n\le17$	$n\le18$	$3^{17}\approx1.29\times10^8$ ， $3^{18}\approx3.87\times10^8$ 。
$n^5$	$n\le47$	$n\le61$	$47^5\approx2.29\times10^8$ ， $61^5\approx8.45\times10^8$ 。
$n^4$	$n\le125$	$n\le173$	$125^4\approx2.44\times10^8$ ， $173^4\approx8.96\times10^8$ 。
$n^3$	$n\le629$	$n\le965$	$629^3\approx2.49\times10^8$ ， $965^3\approx8.99\times10^8$ ；Floyd/DP 往往访存较重。
$n^2$	$n\approx1.5\times10^4$	$n\approx3.0\times10^4$	$15000^2=2.25\times10^8$ ； $20000^2=4\times10^8$ ，只表示落在两条刻度之间； $30000^2=9\times10^8$ 。存全表另算空间。
$n\sqrt{n}$	$n\approx3.9\times10^5$	$n\approx9.3\times10^5$	两者分别约为 $2.44\times10^8$ 和 $8.97\times10^8$ 次；分块/莫队的常数与访存通常会显著压低实际可行规模。
$n\log\_2 n$	$n\approx1.0\times10^7$	$n\approx3.5\times10^7$	仅按比较或简单更新计数；排序搬移及BIT、线段树的随机访存应另行折算。
$n$	$n\le2.5\times10^8$	$n\le9\times10^8$	实际通常先受输入量和内存限制；这行只用于理论运算次数换算。
$K\cdot\text{状态}$	乘积 $\le2.5\times10^8$	乘积 $\le9\times10^8$	按实际可达状态数、每状态转移数及测试组数求和；只有维度独立且状态稠密时才直接相乘。

使用要求：先计算状态数、转移次数、每次转移工作量及测试组数的乘积，再与表中两条算术刻度比较。该表只能比较理论数量级，不能仅凭落在某条刻度内就断言“可做”；接近刻度的方案应使用目标编译选项和最坏数据实测。时间估算后仍需单独核算空间，例如存储 $n^2$ 条边或完整二维数组时，空间可能先超限。

12 * C++ 未定义行为与实现风险

种类	风险	错误示例	后果	修正方式
UB	有符号溢出	`int x=2000000000; x+=x;`	程序行为未定义；优化器可假设溢出不会发生	先提升到能容纳结果的类型，或在运算前按正负号分类检查边界
乘后才转宽	`long long x=a*b;`（`a`、`b` 均为 `int`）	乘法先在 `int` 中完成，可能在赋值前溢出	若最终结果保证在 `long long` 范围内，写 `long long x=1LLab;`；否则乘前检查或改用更宽类型
非法移位量	`1ULL<<k`， $k<0$ 或 $k\ge64$	移位量越界	移位前检查； $k=64$ 特判
有符号左移	负值左移，或非负值左移后不满足C++14 的可表示条件	程序行为未定义	位掩码使用无符号类型；先检查移位量和结果范围
数组/容器越界	`int a[10]; a[10]=0;`	覆盖内存或段错误	显式检查；调试时用 `at()`
非法整数除法或取模	除数为0；或 `INT_MIN/-1`、`INT_MIN%-1`	商不可表示或除数为0时，程序行为未定义	运算前同时检查除数与最小值除以 $-1$ 的边界
读未初始化值	`int x; if(x){...}`	读取自动存储期的未初始化 `int` 会导致未定义行为	定义时初始化；不可达 DP 用明确的哨兵值
悬空引用/指针	返回局部变量地址；`vector` 重分配后继续使用原有元素引用	解引用悬空对象会导致未定义行为	不返回局部对象地址；取得引用前预留容量，并在可能重分配的操作后重新取得引用
失效迭代器	`v.erase(it); ++it;`	`erase` 后继续使用已失效的 `it` 会导致未定义行为	写 `it=v.erase(it);`，使用 `erase` 返回的下一位置
非严格弱序	比较器返回 `a<=b`	`sort` 行为未定义	相等时必须两向均为 `false`
同一标量上的未排序读写	`arr[i]=i++;`（C++14）	对 `i` 的修改与另一次读取彼此未排序，程序行为未定义	拆成多条语句，显式保存旧下标并规定更新顺序
非虚析构删除	`Base* p=new Derived; delete p;`，且 `Base` 析构非虚	经基类指针删除派生对象时程序行为未定义	需要多态删除时令基类析构函数为 `virtual`，或避免经基类指针拥有并删除派生对象
实现定义	负数右移	`int y=(-3)>>1;`	结果依赖实现	不以该操作代替除法；先明确编译器语义
资源	递归爆栈	链上 DFS 深度达到 $10^5$ 以上	常见SIGSEGV	显式栈或确认并调整栈限制
无限递归	线段树区间不缩小	栈耗尽/超时	保证叶子终止且子区间严格缩小
编译	版本不兼容	C++14 使用 `std::gcd`	CE	自行实现gcd；不得使用 C++17 特性
提交	文件重定向错误	`freopen` 文件名、扩展名、模式或输入输出流不符	无法读入或写出答案	按题面和比赛公告逐项核对文件名、`"r"`/`"w"` 及 `stdin`/`stdout`
重定向未生效	`freopen` 仍被注释，或使用本机绝对路径	本地测试通过但评测无法读写	提交前在独立目录按正式文件名复测
编译	入口或预处理错误	`main`、`include` 拼写错误，括号缺失或源码重复粘贴	CE	使用正式编译命令重新编译最终文件，不以编辑器语法高亮代替编译
提交	文件格式错误	将 `.c`、`.pas` 或其他文件作为C++ 源文件提交	编译失败或语言识别错误	核对题号、源文件名、扩展名和提交语言
输出	调试或固定答案残留	额外输出日志、样例特判、随机答案或固定字符串	WA	只保留题目规定的输出，并在样例外数据上复测
环境	非标准环境依赖	使用 `windows.h`、`system()` 或本机专用命令	CE、RE 或行为不一致	仅使用竞赛允许的标准库、编译选项和系统接口
源码	无关大段内容	源码中保留大样例、超大静态答案表或重复代码	文件超限、CE 或审查困难	删除与算法无关的内容，并核对最终源码大小
数值	浮点近似值直接判等	对计算所得浮点数写 `if(a==b)`	舍入误差可能导致边界误判；精确可表示值的比较不在此限	按绝对/相对误差模型比较，或在可行时改用整数与有理数
复杂度	哈希退化	`unordered_map` 出现严重冲突	单次最坏 $O(n)$	需要复杂度保证时使用排序、`map` 或数组
概率	哈希碰撞	单哈希相等即判原串相等	小概率WA	双哈希/强校验/确定性结构
类型	`vector<bool>`	`vector<bool> v(1); auto x=v[0];`	`x` 是代理对象	需普通引用语义时用 `vector<char>`
无符号下标下溢或混比	`for(size_t i=v.size()-1;i>=0;--i)`	`i>=0` 恒真；空容器还会在初始化时下溢	倒序写 `for(size_t i=v.size();i-->0;)`，或检查范围后统一使用足够宽的有符号下标
复杂度	SPFA 退化	特殊构造反复入队	最坏 $O(VE)$	非负权优先Dijkstra
逻辑	位运算优先级	`if(x&1==0)`	实为 `x&(1==0)`	写 `if((x&1)==0)`
模减法为负	`(a-b)%MOD`（ $a<b$ ）	输出负数	规范化到 $[0,\mathrm{MOD})$
线段树数组偏小	`vector<ll> tr(2*n)`	非满二叉规模时越界	递归版保守开 `4*n`
多测不清空	全局数组/并查集复用	WA/RE	按本次实际范围重置
混用整行输入	`cin>>n; getline(cin,s);`	`getline` 可能先读到上一行末尾的换行	若确实要丢弃当前行剩余内容，先用 `cin.ignore(numeric_limits<streamsize>::max(), '\n');`，再调用 `getline`

分类说明：UB 表示标准不对程序行为作任何要求；实现定义行为必须由实现记录其选择；未指定行为只限定若干允许结果，但实现不必记录具体选择。表中“同一标量上的未排序读写”在C++14 中属于UB，而不是普通的未指定行为。CE、资源耗尽、精度错误、复杂度错误和逻辑错误不属于UB。表中的提交与文件检查项是对常见竞赛失误的归纳。

13 * 对拍与差分测试

对拍由参考程序、待测程序、数据生成器和比较器组成。参考程序应优先追求容易证明正确，而不是追求与待测程序相同的优化。生成规模上限必须按参考算法的复杂度和实测时限确定： $O(n^3)$ 、 $O(2^n)$ 与 $O(n!)$ 的可承受规模不能统一成同一个 $n$ 。

brute.cpp：采用枚举、回溯或其他结构简单、易于独立验证的算法，避免与 sol.cpp 共用容易同时出错的核心逻辑。
sol.cpp：与最终提交版本保持一致。
gen.cpp：只生成合法的小规模数据。约定 argv[1] 为本轮随机种子，用它初始化 mt19937；同一 seed 必须生成完全相同的数据。随机数据之外，还应单独枚举最小值、边界值与典型退化结构。
比较器：必须与正式评测的语义一致。下面脚本使用逐字节比较，只适合要求精确输出的题目；若评测按空白分隔的 token、浮点误差或SPJ 判定，应换成对应的比较器。

编译：Linux / WSL 下可写 g++ -std=c++14 -O2 -o brute brute.cpp，并同样编译 sol.cpp、gen.cpp；Windows 下通常生成 brute.exe、sol.exe、gen.exe。编译参数最终以比赛环境为准。

Linux / WSL（bash + GNU coreutils）

以下脚本要求GNU timeout。macOS 默认没有该命令；不要在未安装兼容工具时直接使用本脚本。

#!/usr/bin/env bash
set -u

command -v timeout >/dev/null 2>&1 || {
  echo "GNU timeout is required" >&2
  exit 2
}

save_failure() {
  stage=$1
  code=$2
  seed=$3
  printf '%s\n' "$seed" > hack.seed
  cp -f in.txt hack.in
  cp -f ans.txt hack.ans
  cp -f out.txt hack.out
  cp -f gen.err hack.gen.err
  cp -f brute.err hack.brute.err
  cp -f sol.err hack.sol.err
  echo "$stage failed on seed $seed (exit code $code)" >&2
  exit 1
}

for ((seed=1; seed<=1000; ++seed)); do
  : > in.txt
  : > ans.txt
  : > out.txt
  : > gen.err
  : > brute.err
  : > sol.err

  timeout -k 1s 5s ./gen "$seed" > in.txt 2> gen.err
  code=$?
  ((code == 0)) || save_failure "generator" "$code" "$seed"

  timeout -k 1s 5s ./brute < in.txt > ans.txt 2> brute.err
  code=$?
  ((code == 0)) || save_failure "reference program" "$code" "$seed"

  timeout -k 1s 5s ./sol < in.txt > out.txt 2> sol.err
  code=$?
  ((code == 0)) || save_failure "tested program" "$code" "$seed"

  if ! cmp -s ans.txt out.txt; then
    save_failure "output comparison" 1 "$seed"
  fi
done

echo "All 1000 tests passed"

任何非零退出状态都按失败处理，因此生成失败、RE、TLE 和双方同为空输出均不会误报为通过。GNU timeout 通常以124表示超时；-k 1s 会在发送TERM 后程序仍未退出时继续发送KILL。

Windows（PowerShell 5.1+）

$ErrorActionPreference = 'Stop'
$timeoutMs = 5000
$workDir = (Get-Location).Path

function Get-WorkPath([string]$name) {
    return [IO.Path]::GetFullPath((Join-Path $workDir $name))
}

function Reset-LogFiles {
    foreach ($name in 'in.txt','ans.txt','out.txt','gen.err','brute.err','sol.err') {
        [IO.File]::WriteAllBytes((Get-WorkPath $name), [byte[]]@())
    }
}

function Invoke-LimitedProcess {
    param(
        [string]$FilePath,
        [string]$ArgumentString,
        [string]$InputFile,
        [string]$OutputFile,
        [string]$ErrorFile,
        [int]$TimeoutMs
    )

    $start = New-Object System.Diagnostics.ProcessStartInfo
    $start.FileName = Get-WorkPath $FilePath
    $start.Arguments = $ArgumentString
    $start.WorkingDirectory = $workDir
    $start.UseShellExecute = $false
    $start.CreateNoWindow = $true
    $start.RedirectStandardOutput = $true
    $start.RedirectStandardError = $true
    $start.RedirectStandardInput = [bool]$InputFile

    $process = New-Object System.Diagnostics.Process
    $process.StartInfo = $start
    $outStream = [IO.File]::Create((Get-WorkPath $OutputFile))
    $errStream = [IO.File]::Create((Get-WorkPath $ErrorFile))
    $outTask = $null
    $errTask = $null
    $inputTask = $null
    $timedOut = $false

    try {
        if (-not $process.Start()) {
            throw "Failed to start $FilePath"
        }

        # 先异步排空输出管道，避免子进程因管道写满而死锁。
        $outTask = $process.StandardOutput.BaseStream.CopyToAsync($outStream)
        $errTask = $process.StandardError.BaseStream.CopyToAsync($errStream)
        $timer = [Diagnostics.Stopwatch]::StartNew()

        if ($InputFile) {
            $inputBytes = [IO.File]::ReadAllBytes((Get-WorkPath $InputFile))
            $inputTask = $process.StandardInput.BaseStream.WriteAsync(
                $inputBytes, 0, $inputBytes.Length
            )
            while (-not $inputTask.IsCompleted -and
                   -not $process.HasExited -and
                   $timer.ElapsedMilliseconds -lt $TimeoutMs) {
                [Threading.Thread]::Sleep(5)
            }

            if ($inputTask.IsCompleted) {
                try { $inputTask.Wait() } catch {
                    if (-not $process.HasExited) { throw }
                }
                $process.StandardInput.Close()
            } elseif (-not $process.HasExited) {
                $timedOut = $true
            }
        }

        $remaining = [Math]::Max(
            0, $TimeoutMs - [int]$timer.ElapsedMilliseconds
        )
        if (-not $timedOut -and -not $process.HasExited -and
            -not $process.WaitForExit($remaining)) {
            $timedOut = $true
        }

        if ($timedOut) {
            try { $process.Kill() } catch {}
        }
        $process.WaitForExit()

        if ($outTask) { $outTask.Wait() }
        if ($errTask) { $errTask.Wait() }

        if ($timedOut) { return 124 }
        return $process.ExitCode
    } finally {
        if ($start.RedirectStandardInput) {
            try { $process.StandardInput.Close() } catch {}
        }
        if ($outTask) { try { $outTask.Wait() } catch {} }
        if ($errTask) { try { $errTask.Wait() } catch {} }
        $outStream.Dispose()
        $errStream.Dispose()
        $process.Dispose()
    }
}

function Save-Failure([string]$stage, [int]$code, [int]$seed) {
    [IO.File]::WriteAllText(
        (Get-WorkPath 'hack.seed'),
        "$seed$([Environment]::NewLine)",
        [Text.Encoding]::ASCII
    )
    foreach ($pair in @(
        @('in.txt','hack.in'), @('ans.txt','hack.ans'),
        @('out.txt','hack.out'), @('gen.err','hack.gen.err'),
        @('brute.err','hack.brute.err'), @('sol.err','hack.sol.err')
    )) {
        Copy-Item -LiteralPath (Get-WorkPath $pair[0]) `
                  -Destination (Get-WorkPath $pair[1]) -Force
    }
    Write-Host "$stage failed on seed $seed (exit code $code)" -ForegroundColor Red
    exit 1
}

for ($seed = 1; $seed -le 1000; ++$seed) {
    Reset-LogFiles

    try {
        $code = Invoke-LimitedProcess '.\gen.exe' "$seed" '' `
            'in.txt' 'gen.err' $timeoutMs
    } catch {
        Save-Failure 'generator start' -1 $seed
    }
    if ($code -ne 0) { Save-Failure 'generator' $code $seed }

    try {
        $code = Invoke-LimitedProcess '.\brute.exe' '' 'in.txt' `
            'ans.txt' 'brute.err' $timeoutMs
    } catch {
        Save-Failure 'reference program start' -1 $seed
    }
    if ($code -ne 0) { Save-Failure 'reference program' $code $seed }

    try {
        $code = Invoke-LimitedProcess '.\sol.exe' '' 'in.txt' `
            'out.txt' 'sol.err' $timeoutMs
    } catch {
        Save-Failure 'tested program start' -1 $seed
    }
    if ($code -ne 0) { Save-Failure 'tested program' $code $seed }

    $answer = [IO.File]::ReadAllBytes((Get-WorkPath 'ans.txt'))
    $output = [IO.File]::ReadAllBytes((Get-WorkPath 'out.txt'))
    $same = [Collections.StructuralComparisons]::StructuralEqualityComparer.Equals(
        $answer, $output
    )
    if (-not $same) { Save-Failure 'output comparison' 1 $seed }
}

Write-Host 'All 1000 tests passed'

Invoke-LimitedProcess 返回124表示脚本判定超时；其他非零退出码表示程序运行失败。若程序会再创建子进程，应改用可终止整个进程树的沙箱或作业对象，不能只依赖 Stop-Process。

边界数据应包括最小规模，以及参考程序可承受的小规模域内最大规模；还应覆盖全等、全0、全1、全正、全负、链或菊花等退化树、零权边、环、相等关键字、无解输入及数值边界。只生成随机数据不能替代这些定向用例。

掌握要求：能够在限定时间内完成可靠的对拍框架；把本轮seed 传给生成器并在失败时记录；区分生成器失败、参考程序失败、待测程序RE/TLE 与比较失败；保存输入、双方输出和标准错误；检查比较器是否符合正式评测语义。

14 * NP、NP 完全与 NP-hard 识别

本节只讨论已经明确输入编码的判定问题或优化问题。NP 是判定问题类；NP 完全（NPC）问题既属于NP，又是NP-hard。NP-hard 问题不一定属于NP，也不一定是判定问题。不能因为一个问题写成“求最优值”就称其为NP-hard；只有已经证明至少与某个NP-hard 问题一样困难时，才能使用这一分类。对经典NPC 判定问题，其对应的优化版通常称为NP-hard，而不称为NPC。

一般问题	分类口径	处理原则
SAT、3-SAT、团、独立集、点覆盖、三染色、哈密顿路/回路	表述为“是否存在满足给定阈值或约束的解”时，经典一般版本为NPC	小 $n$ 可枚举、状压或搜索；可解的特殊结构必须逐题说明。不能笼统认为树、DAG 或二分图会让整行所有问题都降为P；例如2-SAT、Horn-SAT 是SAT 的可解限制，而一般二分图上的哈密顿问题仍可能保持NP 完全。
子集和、划分、0/1 背包	明确目标值或收益阈值后的经典判定版为弱NP 完全	$O(nS)$ 、 $O(nW)$ 等算法对数值大小是多项式，但对二进制输入长度只是伪多项式；只有目标和或容量足够小时才可直接使用。
旅行商、最长简单路、最小染色、最大团、最小集合覆盖、Steiner 树	经典优化版为NP-hard；相应阈值判定版通常为NPC	精确算法取决于问题参数：旅行商可用Held--Karp DP，集合覆盖常按全集大小做子集DP，Steiner 树常按终端数参数化。不能把同一个 $O(n^2 2^n)$ 上界套到整行所有问题。
精确覆盖、支配集、反馈点集、3-Partition、整数线性规划可行性	经典判定版为NPC；其中3-Partition 是强NP 完全问题；二进制编码的一般整数线性规划优化版为NP-hard	先确认元素数、参数 $k$ 、数值编码和图结构。强NP 完全意味着不能指望仅靠数值范围的普通伪多项式DP 解决一般情形。
2-SAT、二分图最大匹配、最大流/最小割、MST、经典最短路、欧拉路、DAG 最长路	这些明确列出的经典版本在P	分类只对准确的问题版本成立；改变约束、目标或图类别后必须重新判断，不能只按名称套用结论。

识别要求：先写清输入编码、一般版本还是受限版本、判定目标还是优化目标，以及题目额外约束；再决定使用指数算法、伪多项式DP、参数化算法或有证明的特殊结构算法。

15 能力缺口与复习重点

复习时应重点确认以下能力：
1. 复杂度反推：根据 $n\le10^5$ 、 $m\le2\times10^5$ 、 $K\le50$ 等多参数，计算 $O(K(n+m))$ 与 $O(n^2)$ 的实际操作量。
2. 树与图建模：将删边后的分量问题转化为重链跳跃与换根；将函数调用依赖转化为 DAG 拓扑序和反向贡献累积。
3. DP 状态设计：使用差值状态、0/1 状态维及不可达值，严格区分“恰好”与“至多”。
4. 部分分规划：根据测试点的规模、固定参数和特殊结构确定可覆盖的分值并集。
5. 数学推导：完成方差到差分不变量的转化，并区分不同模数下的组合数算法及容斥边界。
6. 对拍定位：保存失败数据，并区分生成器、参考程序、待测程序和比较器错误。
线段树、树状数组、LCA、Tarjan、树上差分、状态压缩 DP 和树形 DP 常作为综合题的组成部分，不一定以独立模板形式出现。
SCC、笛卡尔树、平衡树和 DP 常用优化是本文的重点；概率基本概念与平面图对偶作为拓展内容保留。
每项时间复杂度均应配套空间估算。一般图组合优化问题还应写清判定版或优化版、输入编码、小参数及特殊结构，再据此选择精确算法、参数化算法或可证明的多项式算法。

创作声明与许可

除另有说明的第三方材料外，本文原稿由 scmmm 创作，当前版本由 gakki 提供校验与补充。本文以 Creative Commons 署名—非商业性使用 4.0 国际版（CC BY-NC 4.0）发布。转载、分享或修改时，请保留创作者的署名、本许可声明及许可证链接，并标明是否作过修改。第三方材料不因本声明自动改用该许可，其来源与许可按相应标注执行。

目前还没有评论...

CSP-S自查表