GESP C++ 八级已经进入 GESP 体系中的最高等级，题目不再只是“会用某个模板”，而是更强调：
能否从题意中抽象出数学模型； 能否用组合计数快速计算方案数； 能否使用倍增处理大步移动或快速跳转； 能否掌握最短路、最小生成树等基础图论算法； 能否分析复杂度并做必要优化。
按照 GESP 八级考纲，八级重点包括计数原理、排列组合、杨辉三角、倍增法、代数与平面几何、最小生成树、单源最短路、Floyd，以及较复杂算法的时间空间复杂度分析和算法优化。
从真题来看，八级题目主要集中在：
组合数学与排列计数； 树上倍增、LCA、树上路径； Dijkstra、Floyd、最小生成树； 图论建模与连通性； 贪心、双指针、栈模拟； 子图枚举、区间最短路； 大数据范围下的复杂度优化。
一、组合数学与计数问题
八级最明显的特点之一，就是组合计数题变多。
这类题通常不难理解题意，但如果直接暴力枚举，会很快超时。学生需要熟悉阶乘、逆元、组合数、排列数，以及“先选对象，再排顺序”的计数思路。
1. 多重集合分配
P10112 [GESP202312 八级] 奖品分配
题目给出 名同学和 种奖品，第 种奖品有 个。每位同学恰好分到一个奖品，且奖品总数为 或 ，要求分配方案数。
如果奖品总数刚好是 ，那么就是多重集合排列：
如果奖品总数是 ，说明会剩下一个奖品。可以枚举剩下的是哪一种奖品，然后把该种奖品数量减一，再计算方案数。
重点：
阶乘和逆元(要了解)预处理； 多重集合排列公式； 总数为 时枚举剩余奖品； 取模计算； 多组数据下要注意复杂度。
这题是八级组合数学的入门题。
2. 组合选择与配对计数
P11250 [GESP202409 八级] 手套配对
题目有 对手套，每对分左右两只。从中取出 只，要求恰好包含 对完整手套，求方案数。(洛谷)
思路可以分三步：
先从 对中选出 对完整手套； 剩余还需要取 只单只手套； 这些单只手套必须来自剩下的 对，并且每对最多取一只，每对有左手或右手两种选择。
因此核心公式是：
重点：
“完整一对”和“单只手套”分开处理； 选择完整对数； 选择贡献单只手套的若干对； 每一对单只手套有 种选择； 需要处理不合法情况，例如 或 。
这是非常标准的组合计数题。
3. 相邻限制与排列计数
P11380 [GESP202412 八级] 排队
题目给出 位同学和 对相邻关系，关系 表示 必须排在 前面且二者相邻，要求总排队方案数。数据范围达到 。
这题本质是把若干相邻关系压缩成“链”。
如果某个同学后面必须接多个人，或者前面必须接多个人，就不合法。
如果关系形成环，也不合法。
否则每条链可以看成一个整体，与单独的人一起排列。
假设压缩后共有 个整体，则答案为：
重点：
每个点最多有一个后继； 每个点最多有一个前驱； 检查是否出现环； 把链压缩成整体； 最后对整体数量做阶乘。
这题适合训练“限制关系转图，再转计数”的能力。
4. DFS 遍历序计数
P13020 [GESP202506 八级] 遍历计数
题目给出一棵树，DFS 的起点可以任意选择，每个点访问相邻点的顺序也可以任意，要求不同 DFS 遍历序的数量。答案对 取模。
这题看起来像搜索，实际上是树上计数。
确定根后，每个点的若干子树可以按照任意顺序访问，贡献一个阶乘。
如果起点不同，得到的遍历序也可能不同，需要综合统计。
重点：
树上 DFS 的访问序由相邻点顺序决定； 每个点的分支顺序有阶乘贡献； 起点可以任意选择； 答案可能极大，需要取模； 取模是 ，不是常见的 。
这题是八级中比较典型的“树结构 + 计数”题。
二、树上问题与倍增思想
八级考纲明确包含倍增法。真题中虽然不一定都直接写“倍增”，但大量题目需要处理树上路径、祖先、快速移动和大步跳转。
1. 多人共同领导
P10113 [GESP202312 八级] 大量的工作沟通
公司结构是一棵以 为根的有根树。每次询问给出若干员工，要求找到能够管理所有参与员工且编号最大的员工。
这就是求多个点的最近公共祖先。
重点：
公司上下级关系抽象成有根树； 能管理所有人的编号最大员工，就是这些点的 LCA； 可以用倍增预处理祖先； 多个点的 LCA 可以两两合并； 注意根节点编号为 。
这题是八级 LCA 入门题。
2. 树上最远异色点对
P10725 [GESP202406 八级] 最远点对
题目给出一棵树，每个点为黑色或白色，要求相距最远的一对不同颜色点的距离。(洛谷)
常见思路：
从某个颜色点出发找最远的异色点； 或分别维护黑点、白点的树上直径信息； 也可以通过两次 DFS / 树形 DP 合并答案。
重点：
树上距离； 树的直径思想； 不同颜色限制； 子树信息合并； ，不能枚举所有点对。
这题适合放在“树上距离与直径”专题。
3. 最长交替颜色路径
P11251 [GESP202409 八级] 美丽路径
树上每个点是黑色或白色，一条路径美丽当且仅当相邻节点颜色均不同，要求最长美丽路径长度。(洛谷)
如果把所有连接同色节点的边删除，剩下的每个连通块中任意路径都满足相邻颜色不同。
所以问题可以转化为：
在删去同色边后的森林中，求最大连通块的直径节点数。
重点：
同色边不能出现在美丽路径中； 保留异色边形成森林； 在每个连通块中求直径； 或用树形 DP 求最长链； 路径长度按节点数量计算，不是边数。
这题是树上路径 DP 的经典变形。
4. 黑点数量限制下的最长路径
P11379 [GESP202412 八级] 树上移动
题目要求在树上选择一条简单路径，使路径上经过的黑色节点不超过 ，并最大化经过节点数。数据范围 。
由于数据范围不大，可以从每个点出发 DFS，统计路径上黑点数量和长度。
也可以把它作为“树上双指针 / 树上路径枚举”的训练题。
重点：
路径不能重复节点； 约束是黑点数量； 允许较高复杂度； 可以枚举起点进行 DFS； 注意路径长度按节点数计算。
5. 树上快速移动
P13019 [GESP202506 八级] 树上旅行
题目给出一棵有根树，移动有两类：向父亲移动若干步，或向编号最小的儿子移动若干步。移动次数可能很大，询问总规模较大。
向父亲走多步，是典型的倍增跳祖先。
向编号最小的儿子不断走，相当于沿着每个点的“最小儿子链”向下移动，也可以预处理倍增跳转。
重点：
父亲方向用倍增； 最小儿子方向也可以看成函数图上的倍增； 每段移动次数可能很大，不能一步步走； 需要处理到根或叶子后不再移动； 总 ，每段 可通过。
这是八级倍增专题非常好的题。
三、最短路与图论算法
八级考纲明确要求最短路与最小生成树。真题中图论题的难度明显高于七级，很多题会结合附加条件或多次询问。
1. 单源最短路
P11966 [GESP202503 八级] 上学
给定一张带权无向图，学校在点 ，有 个同学询问从家到学校的最短时间。边权均为正。
因为所有询问终点相同，直接从学校 做一次 Dijkstra，就能得到所有点到学校的最短距离。
重点：
带权图不能用 BFS； 多个询问同一个目标点，可以反向思考； 无向图中从学校出发等价于所有点到学校； Dijkstra + 优先队列； 距离要用 long long。
这是八级单源最短路基础题。
2. 巨大完全图上的最短距离
P14079 [GESP202509 八级] 最短距离
题目构造了一个含 个结点的带权无向图，若两个结点编号互质则边权为 ，不互质则边权为 ，多次询问两点之间最短距离。题目给出的询问规模为 ，点编号可达 。
显然不能建图。
这类题的关键是利用数学性质压缩路径长度。
重点：
图极大，不能建边； 判断两数是否互质； 直接边权由 决定； 可能通过中间点获得更短距离； 需要用数论性质分析最短路径只需考虑少数情况。
这题是“数学图论建模”的代表题。
3. 猫和老鼠
P14923 [GESP202512 八级] 猫和老鼠
庄园是一张带权连通无向图。猫从猫窝出发，老鼠从某点逃往老鼠洞。若老鼠能规划一条路径，使路径上每个点猫到达时间都严格大于老鼠到达时间，则这个点是安全的，要求安全点奶酪价值和。
核心思路：
先从猫窝做 Dijkstra，求猫到每个点的最短时间； 再从老鼠洞反向做 Dijkstra 或类似最短路扩展； 只有满足“老鼠到达时间 < 猫到达时间”的点才可能安全； 安全路径必须整条路径都满足严格不等式。
重点：
两次最短路； 严格小于条件； 从终点反向扩展更自然； 点权求和； 边权和答案都要用 long long。
这题非常适合训练“最短路 + 安全区域判定”。
4. 子图最短路
P15805 [GESP202603 八级] 子图最短路
给定带权无向图，对所有编号区间 构造诱导子图，要求统计所有子图中所有点对最短路之和，对 取模。数据范围 ，可能有重边。
这题数据范围不大，但枚举层次很多。
可以从 Floyd 的角度思考：
子图由连续编号区间决定； 对每个区间都重新 Floyd 会很慢； 需要利用 做复杂度优化； 重边要保留最小边权； 不连通点对贡献 。
重点：
Floyd 求全源最短路； 区间诱导子图； 多重循环复杂度估算； 对 取模； 注意重边和不连通。
这是八级图论综合压轴题之一。
四、最小生成树及其变形
1. 删除边后的 MST
P14080 [GESP202509 八级] 最小生成树
给定一张带权连通无向图。对于每条边，询问删除这条边后图的最小生成树权值和；若不存在 MST 输出 -1。
如果每次删一条边重新跑 Kruskal，复杂度太高。
需要先求原图 MST，然后分类讨论：
如果删除的是非 MST 边，原 MST 不受影响； 如果删除的是 MST 边，需要找能替代它的最小非树边； 若没有替代边，则图不连通，答案为 -1。
重点：
Kruskal 求 MST； 判断边是否在 MST 中； 非树边替代树边； 树上路径最大边 / 替代边维护； 可结合 LCA、倍增或并查集优化。
这题是八级最小生成树专题的核心题。
五、栈、区间询问与模拟优化
1. 接竹竿
P10264 [GESP202403 八级] 接竹竿
给出卡牌序列，多次询问区间 按规则玩“接竹竿”后剩余几张牌。若新牌点数在队列中已出现，就把两张相同牌之间所有牌取出。
这题如果每次询问直接模拟，最坏复杂度过高。
由于点数最大只有 ，可以利用状态压缩或预处理区间转移。
重点：
单次过程可以用栈模拟； 点数种类很少； 区间询问需要预处理； 可以把当前队列状态压缩成一个状态； 询问转化为状态转移。
这题是“模拟规则 + 多次询问优化”的代表题。
2. 宝石项链
P14924 [GESP202512 八级] 宝石项链
项链是环形的，有 种宝石。需要把项链划分成若干连续段，每段都包含全部 种宝石，求最多能划分多少段。
线性版本可以贪心：从左到右扫描，当前段集齐所有颜色后立刻切开。
环形版本则要考虑起点。
重点：
每段必须包含全部颜色； 线性情况下“越早切越优”； 环形需要枚举或优化起点； 可以使用双指针维护颜色种类； 需要避免重复绕圈过度。
这题适合放在“环形序列 + 贪心/双指针”专题。
六、几何与数学建模
1. 公倍数问题
P10263 [GESP202403 八级] 公倍数问题
题目定义一个看不到的 矩阵，其中 是 和 的公倍数。对每个 ，问矩阵中最多有多少个位置可以是 ，最后输出加权和。
一个位置 可以填 ，当且仅当 是 和 的公倍数，也就是：
因此答案与 的约数数量有关：
行编号 要是 的约数且 ； 列编号 要是 的约数且 ； 该 的可填位置数就是两者乘积。
重点：
公倍数条件反向转化为约数条件； 枚举倍数 / 约数预处理； ，适合类似筛法统计； 注意答案可能很大； 使用 long long。
这题是数论与矩阵计数结合的好题。
2. 空间跳跃
P10726 [GESP202406 八级] 空间跳跃
二维空间中有若干水平挡板，人物可以在挡板上左右移动，也可以从端点掉落到下方第一个挡板。求从第 个挡板左端点到第 个挡板的最短时间，可能无法到达。
可以把每个挡板看成图中的状态，左右端点掉落形成有向边，挡板上移动形成代价边。
重点：
几何关系建图； 从端点向下找到第一个挡板； 边权包括水平移动距离和竖直掉落高度； 建图后跑最短路； ，可以较直接地枚举下方挡板。
这题是“几何场景转图论最短路”的代表题。
七、树上割裂与路径覆盖
1. 割裂
P11967 [GESP202503 八级] 割裂
给定一棵树、若干好点对和一个坏点对。删除某个点后，要求所有好点对仍连通，而坏点对不连通，求可删除节点数。
删除树上一个点会把树分成若干部分。
要让坏点对不连通，删除点必须在坏点对路径上。
要让所有好点对仍连通，删除点不能位于任何好点对路径上，也不能删掉好点对端点。
所以问题转化为：
统计坏点对路径上的点，排除所有好点对路径覆盖到的点。
重点：
树上路径； LCA； 差分标记路径覆盖； 坏路径与好路径的集合差； 数据范围 ，必须线性或近线性处理。
这题是八级树上路径差分的典型题。
八、消息引用与跳转优化
1. 消息查找
P15804 [GESP202603 八级] 消息查找
消息编号从小到大。当前位置为 时，可以移动到 ，如果消息 引用了 ，也可以跳到 。询问从 到 的最少操作次数，且保证有引用的消息最多 条。
如果只用 ，答案是 。
引用边提供了“向前跳跃”的捷径。
由于引用消息很少，可以把关键点抽出来建图或预处理。
重点：
普通边是连续向前移动； 引用边是额外跳跃； 引用边数量少，是突破口； 多次询问不能逐步模拟； 可建立关键点图或预处理最短跳转。
这题是八级中非常好的“稀疏特殊边 + 查询优化”题。
按难度梯度整理
第一梯度：八级基础题
适合刚进入八级学习。
这一阶段目标是：
熟悉八级中的组合计数、树上路径和基础图论模型。
第二梯度：八级核心题
适合系统训练八级主力算法。
这一阶段基本覆盖八级的关键训练内容：倍增、树上路径、组合计数和查询优化。
第三梯度：八级提高题
适合冲刺高分和训练综合建模。
这些题已经明显要求不仅会模板，还要能判断“哪些信息可以预处理、哪些状态可以压缩、哪些暴力可以被数学或图论性质替代”。
按知识点专题整理
1. 组合数学专题
组合数学题的重点不是背公式，而是把方案拆成若干个互不干扰的选择步骤。
2. 树上算法专题
八级树题经常不是单纯 DFS，而是要结合 LCA、差分、倍增或计数。
3. 图论专题
图论题的重点是：先判断图是显式图还是隐式图，再决定能不能建图。
4. 查询优化专题
多次询问题一般不能每次从头模拟，要寻找可复用的信息。
八级备考建议
八级训练建议按下面顺序进行：
先练组合计数：奖品分配、手套配对、排队； 再练树上算法：大量的工作沟通、美丽路径、最远点对、割裂； 接着练倍增和查询优化：树上旅行、消息查找、接竹竿； 然后练图论：上学、空间跳跃、最小生成树、猫和老鼠； 最后练综合题：最短距离、子图最短路、遍历计数。
八级最容易出错的地方主要是：
组合数预处理范围不够； 忘记处理不合法计数情况； LCA 倍增数组初始化错误； 路径差分的端点和 LCA 处理错误； Dijkstra 中距离没有用 long long；MST 删除边时没有区分树边和非树边； 图中存在重边但没有取最小边权； 取模数看错，尤其是 和 ； 看到大数据范围仍然直接暴力模拟。
八级的核心能力可以概括为一句话：
能把题面转化为数学结构或图结构，并用预处理、倍增、组合公式或图论算法把复杂度压下来。
