COURSE · 课程路径

GESP 8级

CURRICULUM

课程大纲 · 能力地图

按「大类 → 难度 → 前后顺序」组织，共 385 个能力标签。其中 58 个为相对「GESP 7级」新增，其余为前置级别已覆盖；同一大类内循序渐进，绿色为已备教案、可直接进入学习；灰色为编写中。

新增标记表示该知识点是「GESP 7级」基础上本级别新加入的，需重点学习。

仅展示相对「GESP 7级」新增的内容 (58)关闭可查看完整大纲（含前置级别已覆盖的知识点）

字符串算法

7 个标签 · 7 已就绪

序号	知识点	能力目标
725	字符串哈希新增36-A1-1	掌握滚动哈希（Rabin-Karp）：把字符串映射为大整数，用前缀哈希 O(1) 比较任意子串是否相等，并能高效处理子串匹配、回文、最长公共子串等问题。
726	KMP 与 next 数组新增36-A1-2	掌握 KMP：用 next（最长真前缀=真后缀）数组在 O(n+m) 内匹配模式串，并用于统计出现次数、周期判定等。
727	Trie 字典树新增36-A1-3	掌握 Trie（前缀树）：用树结构共享字符串前缀，支持插入、查询、前缀计数，是 AC 自动机与异或 Trie 的基础。
728	AC 自动机新增36-A1-4	掌握 AC 自动机：在 Trie 上建 fail 指针（类 KMP 的 next），实现多模式串的单遍匹配，用于敏感词过滤、多串出现统计。
729	后缀数组 SA新增36-A1-5	掌握后缀数组：将所有后缀按字典序排序得到 sa[] 与 rank[]，配合 height[]（相邻后缀 LCP）解决子串统计、最长公共子串、重复子串等问题。
730	后缀自动机 SAM新增36-A1-6	掌握后缀自动机：用 O(n) 状态的有向图表示字符串所有子串，每个状态对应一组 endpos 相同的子串；用于子串计数、出现次数、本质不同子串数。
731	Manacher 与字符串综合新增36-A1-7	掌握 Manacher 算法：O(n) 求最长回文子串/子回文数；并综合应用哈希、KMP、SA 解决回文、周期、公共子串等字符串问题。

线段树与树状数组进阶

7 个标签 · 7 已就绪

序号	知识点	能力目标
688	线段树基础（建树/单点改/区间和）新增39-A1-1	掌握线段树：用完全二叉树维护区间和，支持单点加与区间求和，建树/修改/查询均 O(log n)。
689	区间加 + lazy 懒标记新增39-A1-2	掌握带 lazy 标记的线段树：区间加时若完全覆盖则打标记并返回，查询/下传时再把标记下放给子节点，做到区间修改 O(log n)。
690	区间最值（RMQ）新增39-A1-3	掌握用线段树维护区间最值（max/min）：结构与区间和类似，合并时取最值，支持单点/区间修改与区间最值查询。
691	扫描线（矩形面积并）新增39-A1-4	掌握扫描线 + 线段树求矩形面积并：把矩形拆成左右竖边，按 x 排序，用线段树维护当前“被覆盖长度”随扫描推进的变化。
692	权值线段树 / 动态开点新增39-A1-5	掌握权值线段树：以“值域”为下标建线段树，统计数出现的频数、求第 k 小；当值域过大时用动态开点避免建满整棵树。
693	线段树合并新增39-A1-6	掌握线段树合并：把两棵动态开点线段树按位置逐节点合并（同位置值相加），常用于树上每个节点维护一棵值域线段树并自底向上合并子树信息。
694	线段树综合新增39-A1-7	综合运用线段树：区间加、区间最值/和、懒标记、历史版本等，能根据题目灵活选择节点维护的信息与合并/下传方式。

平衡树与可持久化

5 个标签 · 5 已就绪

序号	知识点	能力目标
695	Treap（旋转平衡）新增32-A1-1	掌握 Treap：给每个节点一个随机优先级，按“堆序（优先级）保持平衡、BST 序维护查找”通过旋转保持平衡，支持插入/删除/排名等。
696	无旋 Treap（fhq Treap）新增32-A1-2	掌握无旋 Treap：用 split（按值/排名切分）与 merge（按优先级合并）完成所有操作，无需旋转，代码简洁且天然支持可持久化。
697	可持久化线段树新增32-A1-3	掌握可持久化线段树：每次修改只复制受影响的节点路径（而非整棵树），从而得到每个历史版本的线段树，支持“回到旧版本”查询。
698	主席树（区间第 k 小）新增32-A1-4	掌握主席树：对静态数组每个前缀建一棵权值线段树（可持久化），查询区间 [l,r] 第 k 小时用 roots[r]−roots[l−1] 两版本相减定位，O(log V)。
699	可持久化 Trie新增32-A1-5	掌握可持久化 Trie（可持久化 01 字典树）：每个前缀插入一个数得到一棵可回退的 Trie，查询区间 [l,r] 内与 x 异或最大值时，用版本 r 与 l−1 的计数差沿“取反位”贪心。

网络流

9 个标签 · 9 已就绪

序号	知识点	能力目标
700	最大流 / Dinic新增33-A1-1	掌握最大流与 Dinic 算法：用残量网络 + 分层图（BFS 定层次）+ 阻塞流（DFS 多路增广），复杂度 O(V²E)，实际极快。
701	最小割新增33-A1-2	掌握最小割：由最大流最小割定理，源汇间的最小割容量恰等于最大流值；并能通过残量网络从 s 可达性求出割集（左/右部）。
702	最大权闭合子图新增33-A1-3	掌握最大权闭合子图：给定点权（可负）与依赖（选 u 必选 v），用最小割建模：答案为“正权和 − 最小割”，转化为最大流求解。
703	费用流（SPFA 增广）新增33-A1-4	掌握最小费用最大流（MCMF）：在最大流基础上，每次用最短路（SPFA，边权=单位费用）找费用最小的增广路，反复增广直到无法增广。
704	费用流（Dijkstra 优化）新增33-A1-5	掌握带势能（Johnson）的费用流：用势能 h 将边权改造为非负，从而用 Dijkstra 替代 SPFA，避免负权退化，复杂度更稳。
705	二分图最大匹配（匈牙利）新增33-A1-6	掌握二分图最大匹配与匈牙利算法：不断尝试为左部点找增广路（未匹配→匹配→…→未匹配右部点），轮换匹配使匹配数+1，直到无法增广。
706	二分图最优匹配（KM）新增33-A1-7	掌握 KM 算法：在带权二分图上求“完美匹配且边权和最大”，用顶标 lx/ly 与相等子图，通过调节顶标不断扩展相等子图直到完备匹配。
707	最小路径覆盖新增33-A1-8	掌握 DAG 最小路径覆盖：把每个点拆成入点/出点，原边 i→j 连出点i→入点j，最大匹配数即“能被合并的路径端点对数”，答案 = 点数 − 最大匹配。
708	网络流建模综合新增33-A1-9	综合运用最大流建模：通过“拆点限流、源汇连边、边权化容量”把现实问题（如每牛需一种食物+一种饮料）转化为最大流，再求最大满足数。

强连通分量与 2-SAT

5 个标签 · 5 已就绪

序号	知识点	能力目标
709	Tarjan 求强连通分量新增34-A1-1	掌握 Tarjan 算法求有向图的强连通分量（SCC）：用 dfn/low 与栈，当 low[u]==dfn[u] 时栈中 u 及其后元素构成一个 SCC。
710	Kosaraju 算法新增34-A1-2	掌握 Kosaraju 算法：正向 DFS 记录完成序，再在反图（边全反向）上按完成序逆序 DFS，每次 DFS 访问到的一个连通块就是一个 SCC。
711	缩点 + 拓扑排序新增34-A1-3	掌握缩点：把每个 SCC 缩成一个点得到 DAG；之后可在 DAG 上拓扑排序，把有环图问题转化为 DAG 上的 DP/依赖问题。
712	2-SAT新增34-A1-4	掌握 2-SAT：每个布尔变量 x 用两个点 x、¬x 表示；子句 (a∨b) 转两条蕴含边 ¬a→b、¬b→a。建图求 SCC，若 x 与 ¬x 同 SCC 则无解，否则可构造解。
713	差分约束系统新增34-A1-5	掌握差分约束：把形如 x_j−x_i≤c 的约束转成边 i→j（权 c），问题化为求最长路（或判正环）；若出现正环则无可行解。

高级动态规划

11 个标签 · 11 已就绪

序号	知识点	能力目标
714	斜率优化新增35-A1-1	掌握斜率优化：当 DP 转移形如 dp[i]=min(dp[j]+a(i)·b(j)+c(j)) 时，把决策点看成平面点，用单调队列维护下凸壳，将 O(n²) 降到 O(n)。
715	凸包优化（李超线段树）新增35-A1-2	掌握李超线段树：动态维护若干直线 y=kx+b，支持插入直线与查询某 x 处的最大值，用线段树在每段区间保留“当前最优直线”。
716	单调队列优化进阶新增35-A1-3	掌握单调队列优化 DP：当转移形如 dp[i]=max(dp[j]+f(j)) 且 j 落在滑动窗口 [i−L,i−1] 时，用单调队列维护窗口内最优决策，O(n)。
717	四边形不等式新增35-A1-4	掌握四边形不等式（Knuth 优化）：当区间 DP 的代价满足四边形不等式且单调时，最优分割点 s[i][j] 满足 s[i][j−1]≤s[i][j]≤s[i+1][j]，把枚举从 O(n) 降到 O(1)。
718	树形 DP（换根）新增35-A1-5	掌握换根 DP：先以某点为根做一次树形 DP，再用“二次扫描换根”把根移到每个节点，O(n) 求出每个节点作为根时的全局信息。
719	树上背包新增35-A1-6	掌握树形背包（依赖性背包）：选某节点必须选其父，每个节点有重量与价值；对每棵子树做分组背包，再合并到父节点，容量 W 下求最大价值。
720	状压 DP 进阶新增35-A1-7	掌握进阶状压 DP：用位掩码表示集合状态（如 TSP 已访问城市、棋盘占用），在“子集/位运算”上做转移，处理 NP 类组合问题。
721	插头 DP 入门新增35-A1-8	掌握插头 DP（轮廓线 DP）：在网格上逐格递推，用一条“轮廓线”上的状态（如某格是否已被骨牌占用）描述已处理部分的连通/占用情况，处理铺砖、连通性等问题。
722	数位 DP 进阶新增35-A1-9	掌握数位 DP：把“统计 [0,n] 中满足数位性质的数”拆成“按位构造”，用状态 (pos, tight, sum/其他) 记忆化，避免逐个数枚举。
723	概率 / 期望 DP 进阶新增35-A1-10	掌握概率/期望 DP：用 E=Σp·(代价+后继期望) 从后向前递推期望，或用“全概率公式”求概率；常结合高斯消元或线性递推。
724	博弈 DP（SG 进阶）新增35-A1-11	掌握 SG 函数与组合博弈：对每个状态定义 SG= mex{ SG(后继) }，多个独立子游戏的总 SG 为各子游戏 SG 的异或；SG≠0 先手必胜。

计算几何

6 个标签 · 6 已就绪

序号	知识点	能力目标
732	向量与叉积基础新增37-A1-1	掌握计算几何基础：用向量/点表示几何对象，叉积判断转向（左转/右转/共线），点积判断夹角，奠定后续凸包、相交判定的基础。
733	极角排序与凸包新增37-A1-2	掌握凸包：用 Andrew 单调链（按 x 排序，上下链各扫描一次）在 O(n log n) 求出点集最小凸多边形；理解极角排序思想。
734	旋转卡壳新增37-A1-3	掌握旋转卡壳：在凸包上用双指针（对踵点）O(n) 求最远点对（直径）、最大三角形面积等，是凸包的自然延伸。
735	线段相交与点在多边形内新增37-A1-4	掌握线段规范相交判定（跨立实验）与射线法判断点是否在多边形内，是几何建模与碰撞检测的基础。
736	扫描线求矩形面积并新增37-A1-5	掌握扫描线：把二维矩形面积并转化为“事件+区间覆盖”的一维问题，配合线段树/差分数组求总面积。
737	半平面交与几何综合新增37-A1-6	掌握半平面交：用排序+双端队列在 O(n log n) 求多个半平面的交集（凸多边形），并综合应用凸包、旋转卡壳、扫描线解决几何建模问题。

数学进阶

8 个标签 · 8 已就绪

序号	知识点	能力目标
738	逆元与费马小定理新增38-A1-1	掌握模逆元：在模质数 p 下用费马小定理 a^(p-2) ≡ a⁻¹ (mod p) 求逆元，使除法取模可行；理解扩展欧几里得求逆。
739	欧拉函数与线性筛新增38-A1-2	掌握欧拉函数 φ(n)（1..n 中与 n 互质个数）与线性筛：在 O(n) 内筛出素数并顺带求 φ、约数个数等积性函数。
740	中国剩余定理 CRT新增38-A1-3	掌握中国剩余定理：求解同余方程组 x≡a_i (mod m_i)（m_i 两两互质），用构造法合并得到模 M=Πm_i 下的唯一解。
741	矩阵快速幂新增38-A1-4	掌握矩阵快速幂：用矩阵乘法 + 快速幂在 O(k³ log n) 求线性递推的第 n 项（如斐波那契、转移矩阵），是数列与图论计数的利器。
742	高斯消元新增38-A1-5	掌握高斯消元：用初等行变换把线性方程组化为上三角，回代求解；处理唯一解、无解、无穷多解，并可用于求秩、逆矩阵。
743	组合数学：组合数与 Lucas新增38-A1-6	掌握组合数计算：用阶乘逆元 O(1) 求 C(n,k) mod p；大 n 时用 Lucas 定理把 C(n,k) 拆成各位 p 进制组合相乘。
744	莫比乌斯反演入门新增38-A1-7	掌握莫比乌斯函数 μ(n) 与反演：用 μ 把“约数/倍数求和”的二重和交换顺序，化简数论求和（如 ∑gcd(i,j)=1 计数）。
745	FFT 与数学综合新增38-A1-8	了解快速傅里叶变换（FFT）：用单位根把多项式乘法从 O(n²) 降到 O(n log n)，进而加速大整数乘法与卷积；并综合回顾数论与代数工具。