GESP C++ 七级已经明显进入“算法综合能力”阶段。
按照 GESP 七级考纲，七级重点包括：
数学库常用函数：三角、对数、指数； 复杂动态规划：二维 DP、区间 DP、LIS、LCS、滚动数组优化； 图的定义与遍历：有向图、无向图、点的度、邻接表、邻接矩阵； 图论基本算法：DFS、BFS、泛洪算法； 哈希表的概念与应用。
从真题来看，七级编程题比六级更强调：
图建模； 连通性分析； BFS / DFS 在图和网格中的应用； 哈希或状态压缩； 树形 DP； 背包与二维动态规划； LIS、区间/划分 DP； 根据数据范围选择 、、 或优化做法。
如果说六级是“树、搜索、简单 DP”的入门，那么七级就是“图论 + 复杂 DP + 状态建模”的正式训练阶段。
一、图论建模与最短路思想
七级最重要的变化，是题目开始大量出现“抽象成图”的模型。
1. BFS 最短路
P10110 [GESP202312 七级] 商品交易 P14921 [GESP202512 七级] 城市规划
商品交易 表面上是商品交换问题，但每种商品可以看作一个点，每个商人的交换关系可以看作一条有向边。由于每次交易都收取固定手续费，且商品价值变化只与起点和终点有关，所以核心可以转化为从起始商品到目标商品的最短交换次数，再结合价值差计算答案。
重点：
商品抽象为点； 商人提供的交换关系抽象为有向边； BFS 求最少经过边数； 如果无法到达，输出 No solution；理解“路径长度”和“价值差”的分离。
城市规划 给出一张连通无向图，定义城市 的建设难度为它到所有城市最短距离的最大值，要求找建设难度最小且编号最小的城市。数据范围 ，可以从每个点做一次 BFS，求出每个点到其它点的最短距离，再取最大值作为该点难度。
重点：
无权图最短路使用 BFS； 每个点作为起点做一次 BFS； 一个城市的答案是到其它所有点距离的最大值； 最后取最小最大距离； 多个城市相同取编号最小。
这两题适合放在“BFS 最短路建模”专题中。
2. 连通块与并查集
P14077 [GESP202509 七级] 连通图
题目给出一张可能有重边和自环的无向图，要求最少加入多少条边使整张图连通。核心结论是：
如果图有 个连通块，那么最少需要加入： 条边。
重点：
连通块数量统计； 自环对连通性没有帮助； 重边不会改变连通块数量； 可以用 DFS / BFS，也可以用并查集； 最终答案是连通块数减一。
这题是七级图论中较基础的一道，适合作为并查集或连通块统计入门题。
3. 图的中心与全源 BFS
P14921 [GESP202512 七级] 城市规划
这题也可以作为图论综合题。
它本质是在无权连通图中找“图中心”：选择一个点，使它到所有点的最短距离最大值最小。
重点：
无权图中点到点距离用 BFS； 对每个点计算离它最远的点距离； 选择最大距离最小的点； 数据范围允许 ； 注意编号最小优先。
这类题能很好训练从题面定义中提炼图论模型的能力。
二、DFS、泛洪与形状识别
七级的 DFS 不再只是“走迷宫”，还会结合连通块形状、树结构、网格图等模型。
1. 网格连通块与形状哈希
P10379 [GESP202403 七级] 俄罗斯方块
题目给出一个有颜色的网格，相同颜色且四连通的格子组成一个俄罗斯方块。两个方块如果只通过平移就能重合，则认为是同一种形状，颜色不同也不影响形状种类。
重点：
用 DFS / BFS 找出每个同色连通块； 记录连通块中所有格子的坐标； 将坐标平移到相对原点； 排序后作为形状表示； 用 set/map/ 字符串哈希统计不同形状。
这题是非常典型的“泛洪算法 + 形状归一化”。
2. 树上连通结构
P10723 [GESP202406 七级] 黑白翻转 P11249 [GESP202409 七级] 小杨寻宝 P11378 [GESP202412 七级] 燃烧
黑白翻转 要求把最少的白点变黑，使得所有黑点在树上仍然连成一棵树。它的本质是：把所有原本的黑点连接起来所需经过的白点数量。也就是树上的最小连通子树问题。
重点：
树中连接若干关键点的最小连通结构； DFS 统计每棵子树中黑点数量； 判断一个点是否在所有黑点的连接路径上； 白色且必须保留的点需要翻转。
小杨寻宝 中，每条边最多经过一次，想取得所有宝物。树上如果所有宝物点都在一条简单路径上，就可以选择路径一端作为起点、另一端作为终点，一路经过所有宝物；如果宝物形成分叉结构，则不可能。
重点：
树上关键点是否位于一条简单路径； 可以从一个宝物出发找最远宝物，再判断所有宝物是否在这条路径上； 也可以用 DFS 判断关键子树分叉数； 本质是“关键点诱导的最小子树是否是一条链”。
燃烧 给出树上每个点权值，火只能从高权值点扩散到相邻的低权值点，要求选择一个起点使燃烧点数最多。
教学重点：
边的可扩散方向由点权大小决定； 从某个点能烧到哪些点，是一个有向可达问题； 朴素从每个点 DFS 会超时； 需要树形 DP 或换根思想； 统计每个点作为起点时可到达的节点数量。
这一组题非常适合组成“树上 DFS 与树形 DP”专题。
三、哈希、状态压缩与奇偶性
七级对哈希的考查不一定是直接写哈希表，也可能是把状态编码后统计。
1. 奇偶状态压缩
P10724 [GESP202406 七级] 区间乘积 P11965 [GESP202503 七级] 等价消除
区间乘积 要求统计多少个区间的乘积是完全平方数。
一个数是不是完全平方数，关键在于每个质因子的指数是否都是偶数。因此可以把每个数的“质因子奇偶性”编码成一个状态。区间乘积为完全平方数，当且仅当前缀状态相同。
重点：
质因数分解； 只关心每个质因子指数的奇偶； 用异或维护前缀状态； 相同前缀状态之间形成合法区间； 用 map统计状态出现次数。
等价消除 中，每次可以删去两个相同字符。一个字符串能被完全消除，当且仅当每种字符出现次数都是偶数。因此子串是否可消除，也可以用字符出现次数奇偶状态判断。
重点：
每个字母出现奇偶性用二进制位表示； 扫描字符串维护前缀异或状态； 两个相同状态之间的子串所有字符出现次数均为偶数； 用 map<int,int>统计前缀状态。
这两题本质非常接近，都是“前缀状态 + 哈希统计”。
2. 图形状哈希
P10379 [GESP202403 七级] 俄罗斯方块
这题也可以放到哈希专题。
将一个连通块的形状转成标准形式后，可以用字符串、数组、set 或字典树存储。核心不是哈希函数本身，而是“如何保证相同形状得到相同表示”。
重点：
找出连通块； 坐标归一化； 排序； 序列化； 判重。
四、动态规划与背包模型
七级 DP 的特点是：状态设计比六级更复杂，但通常还不会到省选级别。
1. 背包问题
P11377 [GESP202412 七级] 武器购买 P13018 [GESP202506 七级] 调味平衡
武器购买 给出每件武器的强度和花费，要求总强度至少为 ，总花费不超过 ，并求最小花费。它是典型的 0/1 背包变形。
重点：
每件物品只能选或不选； 用花费作为背包容量； dp[j]表示花费为 时可达到的最大强度；倒序枚举花费； 最后找第一个强度不小于 的花费。
调味平衡 给出若干食材，每个食材有酸度和甜度。要求选出若干食材，使酸度和甜度相等，并最大化酸度与甜度之和。
可以把每个食材转成：
差值：； 价值：。
目标是差值总和为 ，价值最大。
重点：
差值可能为负，要用偏移量； dp[diff]表示当前差值下的最大总和；0/1 背包思想； 正负差值状态转移要避免重复使用物品； 最终答案是差值为 的最大价值。
这两题是七级背包类 DP 的代表题。
2. 路径 DP 与资源限制
P11248 [GESP202409 七级] 矩阵移动
题目给出一个只包含 0、1、? 的矩阵，只能向右或向下走。经过 1 得分，最多可以把 个 ? 改成 1，要求最大得分。
重点：
路径只能向右或向下； 状态中需要记录已经修改了多少个 ?；dp[i][j][k]表示到达格子 、使用 次修改的最大得分；可以用滚动数组压缩； 本质是“网格路径 DP + 背包维度”。
这题适合放在二维 DP 专题中。
3. 序列 DP 与分组 DP
P10111 [GESP202312 七级] 纸牌游戏 P14922 [GESP202512 七级] 学习小组
纸牌游戏 中，自己每轮可以保持上一轮牌或换牌，换了 次牌会扣对应代价。状态可以设计为：
dp[card][cnt]
表示当前最后一轮出某张牌、已经换牌 次时的最大得分。
重点：
当前位置的选择依赖上一轮； 需要记录当前出的牌； 需要记录已经换牌次数； 每轮根据胜负规则计算得分； 最后枚举所有状态取最大值。
学习小组 给出每个同学积极度 ，以及人数为 的小组基础积极度 。一个小组贡献为：
要求划分所有学生，使贡献总和最大。数据范围 ，可以先按积极度排序，再做区间/划分 DP。题意中明确了组内贡献由人数和最大最小积极度差决定。
重点：
先排序，使一组的最大最小差可以由区间端点表示； 设计划分 DP； 枚举最后一组的大小； 用 加上区间最大最小差作为该组贡献； 注意复杂度控制在 或 范围内。
这两题适合作为七级“序列 DP / 分组 DP”专题。
4. LIS 模型
P14078 [GESP202509 七级] 金币收集
题目中金币出现在数轴坐标 和时刻 ，角色只能不动或向右走。要按时间和位置可达关系选择最多金币。
核心转化是：
要收集某枚金币，必须满足 ，并且对于两枚金币按位置排序后，还要满足时间差能够覆盖位置差。
一种常见处理方式是按 排序，再对 做最长不下降子序列模型。
重点：
可达条件转化； 排序消除一个维度； 维护另一个维度的单调性； 用 LIS / LNDS 思想优化； 注意不可达金币要跳过。
这题是七级中非常典型的“现实运动模型转 LIS”。
5. 整数拆分与数学 DP
P15802 [GESP202603 七级] 拆分
题目要求把正整数 拆成若干个正整数之和，使乘积最大，并输出最大乘积对 取模的结果。数据范围 。
这题可以从 DP 入手：
dp[i] 表示拆分 的最大乘积。
但大数据下需要发现经典结论：
尽量拆成 ； 余数为 时，把一个 改成 ； 余数为 时，最后乘 。
重点：
小数据可以用 DP 找规律； 大数据使用数学规律； 快速幂取模； 模数是 ，不是常见的 ； 注意 的特殊情况。
这题适合作为七级“DP 到数学优化”的题。
五、图的度数、线图与组合计数
1. 线图计数
P13017 [GESP202506 七级] 线图
题目给定简单无向图 ，构造它的线图 。原图中每条边在线图中对应一个点；若原图中两条边共享端点，则线图中对应点之间连边。要求线图中的边数。
关键观察：
对于原图中一个度数为 的点，所有与它相连的 条边两两共享这个点，因此在线图中会产生：
条边。
由于原图是简单图，一对原图边最多共享一个端点，所以不会重复计算。
重点：
理解线图定义； 只需要统计原图每个点的度数； 累加组合数 ； 答案可能较大，要用 long long。
这题是七级图论概念题中非常好的计数题。
六、带优惠的路径问题
1. 物流网络
P15803 [GESP202603 七级] 物流网络
题目给出无向图，每条边有运输费用 和景观评分 。从 到 的一条路径中，可以免除景观评分最高的那条边的运输费用，要求最小费用；若无法到达输出 -1。数据范围 ，边权和评分可达 。
这题比普通最短路多了一个限制：优惠边由路径上最大景观评分决定。
重点：
路径费用不是简单边权和； 需要处理“路径上最大 的边”； 可以枚举被免除的边或枚举最大景观阈值； 也可以构造状态最短路； 注意不可达情况输出 -1。
这题适合作为七级图论提高题，训练学生处理“路径代价带附加规则”的模型。
按难度梯度整理
第一梯度：七级基础题
适合刚进入七级的同学。
这一阶段的目标是：
熟悉七级的基本图建模、状态压缩和背包转移。
第二梯度：七级核心题
适合系统训练七级主力模型。
这一阶段覆盖了七级最常见的图论、动态规划和状态设计。
第三梯度：七级提高题
适合冲刺高分和训练综合建模。
这一阶段题目已经不只是套模板，而是要求从定义中抽象模型，再选择合适算法。
按知识点专题整理
1. 图论专题
七级图论的重点不是复杂算法，而是“能不能把题目抽象成图”。
2. DFS / 泛洪 / 树专题
这一类题特别适合训练 DFS 的“信息回传”和“子树统计”。
3. 哈希与状态压缩专题
这一类题的共同点是：把复杂对象转化成一个可比较、可统计的状态。
4. 动态规划专题
七级 DP 的核心不是记公式，而是根据题目找到“状态中必须记录什么”。
七级备考建议
七级训练建议按下面顺序进行：
先练图的基本建模：商品交易、连通图、线图、城市规划； 再练 DFS 和树：俄罗斯方块、黑白翻转、小杨寻宝、燃烧； 接着练状态压缩：等价消除、区间乘积； 然后练 DP：武器购买、矩阵移动、纸牌游戏、调味平衡； 最后练综合题：金币收集、学习小组、拆分、物流网络。
七级最容易出错的地方主要是：
无法判断题目该建成图、树、序列还是状态； BFS 和 DFS 使用场景混淆； 树上 DFS 不会从子树回传信息； DP 状态设计少了一维； 背包转移顺序写错； 前缀状态没有初始化； map统计时忘记先加入空前缀；路径题没有处理不可达情况； 答案范围较大但没有使用 long long。
七级的核心能力可以概括为一句话：
能把题面抽象成图、状态或 DP，并根据数据范围选择正确复杂度。
