GESP C++ 七级真题全拆解
20道洛谷题，一网打尽图论、DP、哈希

不是泛泛讲考纲——而是把每道真题的"为什么这么做"给你讲透

GESP C++ 七级已经明显进入"算法综合能力"阶段。如果说六级是"树、搜索、简单 DP"的入门，那么七级就是"图论 + 复杂 DP + 状态建模"的正式训练。

P10110 [GESP202312 七级] 商品交易

题目本质：每种商品是一个点，商人的交换关系是有向边。每次交易收固定手续费，核心转化为从起始商品到目标商品的最短交换次数，再结合价值差计算答案。

教学重点：商品抽象为点；交换关系抽象为有向边；BFS 求最少经过边数；无法到达输出 No solution；理解"路径长度"和"价值差"的分离。

P14921 [GESP202512 七级] 城市规划

题目本质：连通无向图中，一个城市的"建设难度" = 它到所有城市最短距离的最大值。要求找建设难度最小且编号最小的城市。O(n²) 可过，每个点做一次 BFS。

教学重点：无权图最短路用 BFS；每个点作为起点做一次 BFS；求到所有点距离的最大值；取最小最大距离处；多个城市相同取编号最小。

这两题适合放在"BFS 最短路建模"专题中。孩子要先学会"看出来这是图"，而不是等着题目告诉他。

P14077 [GESP202509 七级] 连通图

题目本质：给出一张可能有重边和自环的无向图，问最少加入多少条边使整张图连通。核心结论：k 个连通块 → 需要 k-1 条边。

教学重点：连通块数量统计；自环对连通性没有帮助；重边不会改变连通块数量；DFS/BFS 或并查集均可；最终答案 = 连通块数 - 1。

这题是七级图论中最基础的一道，适合作为并查集或连通块统计的入门题。

P10379 [GESP202403 七级] 俄罗斯方块

题目本质：有颜色的网格中，相同颜色且四连通的格子组成一个"俄罗斯方块"。两个方块只通过平移就能重合，视为同一种形状。颜色不同不影响形状种类。

教学重点：DFS/BFS 找出同色连通块；记录所有格子的坐标；平移到相对原点；排序后作为形状表示；用 set/map/字符串哈希统计不同形状。

这道题是"泛洪算法 + 形状归一化"的典型。很多孩子第一次做的时候，卡在"怎么保证相同形状得到相同表示"上——答案很简单：找连通块 → 平移到原点 → 排序 → 序列化。

P10723 [GESP202406 七级] 黑白翻转

题目本质：把最少的白点变黑，使得所有黑点在树上仍然连成一棵树。本质是把所有黑点连接起来所需经过的白点数量——也就是树上的最小连通子树问题。

教学重点：树中连接若干关键点的最小连通结构；DFS 统计每棵子树中黑点数量；判断一个点是否在所有黑点的连接路径上；白色且必须保留的点需要翻转。

P11249 [GESP202409 七级] 小杨寻宝

题目本质：每条边最多经过一次，想取得所有宝物。如果宝物点都在一条简单路径上，可以选一端作起点、另一端作终点，一路经过所有宝物；如果宝物形成分叉，则不可能。

教学重点：树上关键点是否位于一条简单路径上；从某个宝物出发找最远宝物，判断其余宝物是否在此路径上；本质是"关键点诱导的最小子树是否是一条链"。

P11378 [GESP202412 七级] 燃烧

题目本质：树上每个点有权值，火只能从高权值点扩散到相邻低权值点，选一个起点使燃烧点数最多。是一个有向可达问题。

教学重点：边的可扩散方向由点权大小决定；朴素从每个点 DFS 会超时；需要树形 DP 或换根思想；统计每个点作为起点时可到达的节点数量。

P10724 [GESP202406 七级] 区间乘积

题目本质：统计多少个区间的乘积是完全平方数。一个数是完全平方数 ⇔ 每个质因子的指数都是偶数。把每个数的"质因子奇偶性"编码成状态，区间乘积为完全平方数 ⇔ 前缀状态相同。

教学重点：质因数分解；只关心指数奇偶；用异或维护前缀状态；相同状态之间形成合法区间；map 统计状态出现次数。

P11965 [GESP202503 七级] 等价消除

题目本质：每次删两个相同字符。字符串可完全消除 ⇔ 每种字符出现次数都是偶数。子串是否可消除，用字符出现次数奇偶状态判断。

教学重点：每个字母奇偶性用二进制位表示；扫描维护前缀异或状态；两个相同状态之间的子串所有字符出现次数均为偶数；用 map 统计前缀状态。

P11377 [GESP202412 七级] 武器购买

题目本质：每件武器有强度和花费，总强度至少为 S，总花费不超过 B，求最小花费。0/1 背包变形——用花费作背包容量，dp[j] = 花费 j 时可达到的最大强度，倒序枚举。

教学重点：花费作为背包容量；dp[j] 表示最大强度；倒序枚举花费避免重复使用；最后找第一个强度不小于 S 的花费。

P13018 [GESP202506 七级] 调味平衡

题目本质：每个食材有酸度 a 和甜度 b。选若干食材使酸度和等于甜度和，最大化酸度+甜度之和。核心转化：差值 d=a-b，价值 v=a+b，目标 = 差值总和为 0 时价值最大。

教学重点：差值可能为负 → 用偏移量；dp[diff] 表示当前差值下的最大总和；正负差值状态转移避免重复使用物品；最终答案 = 差值为 0 的最大价值。

P11248 [GESP202409 七级] 矩阵移动

题目本质：矩阵只包含 0、1、?，只能向右或向下走。经过 1 得分，最多把 k 个 ? 改成 1，要求最大得分。状态中需记录已修改了多少个 ?。

教学重点：路径限制（只能向右向下）；dp[i][j][k] 三维状态；可用滚动数组压缩空间；本质是"网格路径 DP + 背包维度"。

P10111 [GESP202312 七级] 纸牌游戏

题目本质：每轮可以保持上一轮牌或换牌，换 k 次扣对应代价。状态设计：dp[card][cnt] = 当前最后一轮出某张牌、已换牌 cnt 次时的最大得分。

教学重点：当前位置的选择依赖上一轮；需记录当前出的牌和换牌次数；每轮根据胜负规则计算得分；最后枚举所有状态取最大值。

P14922 [GESP202512 七级] 学习小组

题目本质：每个同学有积极度 a[i]，人数为 k 的小组基础积极度 v[k]。小组贡献 = v[k] + max(a) - min(a)。划分所有学生使贡献总和最大。

教学重点：先排序，使一组的最大最小差由区间端点表示；设计划分 DP；枚举最后一组的大小；注意复杂度控制在 O(n²) 或 O(n²×k) 范围内。

P14078 [GESP202509 七级] 金币收集

题目本质：金币在数轴坐标 x[i] 和时刻 t[i] 出现，角色只能不动或向右走。按时间和位置可达关系选择最多金币。转化：按 x 排序后，对 t-x 做最长不下降子序列模型。

教学重点：可达条件转化 t[j] ≥ t[i] + |x[j]-x[i]|；排序消除一个维度；维护另一维度的单调性；LIS/LNDS 思想优化；不可达金币要跳过。

P15802 [GESP202603 七级] 拆分

题目本质：把正整数 n 拆成若干个正整数之和，使乘积最大，结果对 1000000007 取模。经典结论：尽量拆成 3；余 1 时把一个 3+1 改成 2+2；余 2 时最后乘 2。

教学重点：小数据用 DP 找规律；大数据用数学规律 + 快速幂取模；注意 n ≤ 2 的特殊情况；模数是 1000000007。

P13017 [GESP202506 七级] 线图

题目本质：给定简单无向图 G，构造线图 L(G)：原图每条边 → 线图中一个点；原图中两条边共享端点 → 线图中对应点之间连边。求线图中边数。

教学重点：理解线图定义；只需统计原图每个点的度数 d；累加组合数 C(d,2)；由于原图是简单图，一对原图边最多共享一个端点，不会重复计算；答案较大要用 long long。

这题是七级图论概念题中非常好的计数题。不需要高阶算法，但需要你真正理解线图的定义并能转化为组合数计算。

P10378 [GESP202403 七级] 交流问题

题目本质：给出若干学生和他们的交流关系，要求判断是否可以将学生分成两组，使得每组内部没有交流关系——即判断图是否为二分图。

教学重点：二分图判定；染色法 DFS/BFS；冲突检测（相邻点同色则不是二分图）；颜色标记（0/1 或 1/2）；注意图可能不连通，需要对每个连通分量分别染色。

二分图判定是图论中的"基本功"。这题的关键坑在于图可能不连通——很多孩子只从 1 号点开始染色，结果漏掉了其它连通分量。

P11964 [GESP202503 七级] 图上移动

题目本质：给出一个有向图，要求在恰好 k 步内从起点到达终点的方案数。需要用 DP 思想在图上做状态转移。

教学重点：图上精确步数可达性 DP；状态设计 dp[step][node]；转移时枚举上一步的来源节点；注意步数的精确性（不能多也不能少）；可以用邻接矩阵快速幂优化。

这题是七级图论中"图上 DP"的代表题。朴素做法 O(k×m)，数据更大时可以用邻接矩阵快速幂优化到 O(n³ log k)。

P15803 [GESP202603 七级] 物流网络

题目本质：无向图中每条边有运输费用 w[i] 和景观评分 s[i]。从 S 到 T 的路径中，可免除景观评分最高那条边的运输费用，求最小费用。

教学重点：路径费用不是简单边权和；需处理"路径上最大 s 的边"；可枚举被免除的边或枚举最大景观阈值；也可构造状态最短路；不可达输出 -1。

这题适合作为七级图论提高题。孩子要学会"路径上存在特殊条件"时如何处理——不是简单的跑一遍 Dijkstra 就能解决的。

第一步：图的基本建模（P14077 连通图 → P10110 商品交易 → P13017 线图）
第二步：DFS 和树（P10379 俄罗斯方块 → P10723 黑白翻转 → P11249 小杨寻宝 → P11378 燃烧）
第三步：状态压缩（P11965 等价消除 → P10724 区间乘积）
第四步：动态规划（P11377 武器购买 → P13018 调味平衡 → P11248 矩阵移动 → P10111 纸牌游戏 → P14078 金币收集 → P14922 学习小组 → P15802 拆分）
第五步：图论综合提高（P10378 交流问题 → P11964 图上移动 → P14921 城市规划 → P15803 物流网络）

1. 无法判断题目该建成图、树、序列还是状态

现象：读完题不知道从哪下手。原因：缺少"从题面抽象模型"的训练。改正：拿到题先问自己三个问题——题目里什么是"点"？什么是"边"？我要优化的目标变量是什么？

2. BFS 和 DFS 使用场景混淆

现象：求最短路径用 DFS 导致超时或答案错误。因果：DFS 找到的第一条路径不一定最短，BFS 才能保证。记住：无权图最短路 = BFS。

3. 树上 DFS 不会从子树回传信息

现象：写了 DFS 但不知道子树的计算结果怎么用。改正：树的 DFS 精髓在于"后序遍历"——先把子树的答案算出来，然后汇总到当前节点。黑白翻转、燃烧都是这个套路。

4. DP 状态设计少了一维

现象：写出来的 DP 永远差一点，答案不对。改正：如果发现"某个约束条件没法在现有状态中体现"，那就多开一维。比如矩阵移动中的"已修改次数"。

5. 背包转移顺序写错

现象：0/1 背包正序枚举容量，结果同一个物品被用了多次。改正：0/1 背包倒序、完全背包正序，这是基本功，考试前写到肌肉记忆。

6. 前缀状态没有初始化

现象：用 map 统计前缀状态时漏了初始状态。改正：扫描之前先把空状态（通常为 0）加入 map，如 mp[0] = 1。等价消除和区间乘积都容易犯这个错。

7. 路径题没有处理不可达情况

现象：题目要求"如果无法到达输出 -1"，但代码忘了判断。改正：任何路径类题目，先在脑子里过一遍——BFS 排队列空了还没到终点怎么办？输出什么？

8. 答案范围较大但没有使用 long long

现象：逻辑全对，但最后几个测试点 WA。改正：线图那题就是典型——组合数 C(d,2) 累加时 d 大了会爆 int。养成习惯：看到"计数""求和"先想会不会超 int 范围。

七级的核心能力可以概括为一句话：
"能把题面抽象成图、状态或 DP，
并根据数据范围选择正确复杂度。"

20 道真题，精刷比泛刷重要十倍。
每道题做完问自己三个问题：
我建了什么模型？为什么选这个算法？
数据范围决定了什么复杂度？

能回答这三个问题，七级就稳了。

你家孩子在备考 GESP 几级？
评论区留下级别 + 最头疼的知识点，教练帮你分析～

我是青青老师，一名少儿编程独立老师
专注 C++ 信奥赛教学
每周更新洛谷题解、GESP 备考策略、算法干货

扫码添加好友 · 免费领取试听课和专属学习规划

朋友圈每日更新：信奥赛资讯 + 刷题打卡 + 学生成绩分享