GESP C++ 六级真题分类及详细讲解

GESP C++ 六级的核心特点是：动态规划开始成为主线，树与图的遍历正式出现，栈、归并排序等数据结构与算法开始综合考查。

从真题风格看，六级通常不再是单纯语法题，而是要求你能把题意转化成算法模型。常见题型可以分为以下几大类：

一、六级核心知识点总览

二、真题分类详解

1. 线性 DP 类

题型特征

这类题通常给你一个序列、台阶、道路或若干天的状态，要求计算：

• • 有多少种方案；
• • 最小代价；
• • 最大收益；
• • 是否可以到达某个状态。

核心是找到：

dp[i] 表示前 i 个位置 / 到达第 i 个状态的最优值或方案数

常见模型 1：爬楼梯 / 下楼梯

典型题意

一次可以走 1 阶或 2 阶，问到第 n 阶有多少种走法。

状态设计

dp[i] = 到达第 i 阶的方案数

状态转移

到第 i 阶可以从：

• • i - 1 阶走 1 步；
• • i - 2 阶走 2 步。

所以：

dp[i] = dp[i - 1] + dp[i - 2]

初始化

dp[1] = 1;dp[2] = 2;

代码框架

#include<bits/stdc++.h>using namespace std;intmain(){int n;    cin >> n;vector<longlong> dp(n + 1);if (n >= 1) dp[1] = 1;if (n >= 2) dp[2] = 2;for (int i = 3; i <= n; i++) {        dp[i] = dp[i - 1] + dp[i - 2];    }    cout << dp[n] << endl;    return0;}

常见模型 2：最小代价路径

典型题意

有一排台阶，每个台阶有一个花费，走到第 i 个台阶需要支付代价，求到终点的最小花费。

状态设计

dp[i] = 到达第 i 个位置的最小花费

状态转移

如果可以从 i - 1 或 i - 2 来：

dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

易错点

1. 1. dp[0] 是否代表起点；
2. 2. 终点是否需要支付代价；
3. 3. 数组下标从 0 还是 1 开始。

2. 01 背包 DP 类

这是 GESP 六级的重点之一。

题型特征

有 n 个物品，每个物品只能选一次。

每个物品有：

• • 体积 / 重量 w[i]
• • 价值 v[i]

背包容量为 m，求最大价值。

状态设计

dp[j] = 容量为 j 时能取得的最大价值

状态转移

对于第 i 个物品：

dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

为什么容量要倒序？

因为每个物品只能用一次。

如果正序枚举：

for (int j = w[i]; j <= m; j++)

那么当前物品可能会被重复使用，变成完全背包。

01 背包必须倒序：

for (int j = m; j >= w[i]; j--)

标准代码

#include<bits/stdc++.h>usingnamespace std;intmain(){int n, m;    cin >> n >> m;vector<int> w(n + 1), v(n + 1);vector<int> dp(m + 1, 0);for (int i = 1; i <= n; i++) {        cin >> w[i] >> v[i];    }for (int i = 1; i <= n; i++) {for (int j = m; j >= w[i]; j--) {            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);        }    }    cout << dp[m] << endl;return0;}

六级真题常见变形

3. 完全背包 DP 类

题型特征

有 n 种物品，每种物品可以选无限次。

例如：

• • 用若干种面值凑钱；
• • 买饮料，每种饮料可以买多瓶；
• • 若干种操作可以重复使用。

状态设计

dp[j] = 容量为 j 时的最优值

状态转移

dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

与 01 背包的关键区别

完全背包容量正序枚举：

for (int j = w[i]; j <= m; j++)

因为物品可以重复选。

标准代码

#include<bits/stdc++.h>usingnamespace std;intmain(){int n, m;    cin >> n >> m;vector<int> w(n + 1), v(n + 1);vector<int> dp(m + 1, 0);for (int i = 1; i <= n; i++) {        cin >> w[i] >> v[i];    }for (int i = 1; i <= n; i++) {for (int j = w[i]; j <= m; j++) {            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);        }    }    cout << dp[m] << endl;return0;}

判断 01 背包还是完全背包

4. 简单树形 DP 类

六级会开始出现树结构，不一定很复杂，但要求能理解：

• • 树的 DFS；
• • 父子关系；
• • 子树信息合并。

题型特征

题目给一棵树，要求在树上求：

• • 最大收益；
• • 最小代价；
• • 子树大小；
• • 树上路径信息；
• • 是否选择某些节点。

基础模型：求子树大小

状态设计

siz[u] = 以 u 为根的子树节点数量

转移

siz[u] = 1 + 所有儿子的 siz[v]

代码

voiddfs(int u, int fa){    siz[u] = 1;for (int v : g[u]) {if (v == fa) continue;dfs(v, u);        siz[u] += siz[v];    }}

树形 DP 模型：选或不选

典型题意

一棵树上每个节点有价值，相邻节点不能同时选择，求最大价值。

状态设计

dp[u][0] = 不选 u 时，以 u 为根的子树最大价值dp[u][1] = 选 u 时，以 u 为根的子树最大价值

状态转移

如果选了 u，那么它的儿子不能选：

dp[u][1] += dp[v][0];

如果不选 u，儿子可选可不选：

dp[u][0] += max(dp[v][0], dp[v][1]);

代码框架

voiddfs(int u, int fa){    dp[u][1] = val[u];    dp[u][0] = 0;for (int v : g[u]) {if (v == fa) continue;dfs(v, u);        dp[u][1] += dp[v][0];        dp[u][0] += max(dp[v][0], dp[v][1]);    }}

六级树形 DP 易错点

1. 1. 忘记记录父节点，导致 DFS 死循环；
2. 2. 没有初始化 dp[u][1] = val[u]；
3. 3. 把无根树当成有根树时，需要从某个点开始 DFS；
4. 4. 子节点状态合并顺序写错。

5. DFS / BFS 遍历类

5.1 DFS 深度优先搜索

题型特征

DFS 常用于：

• • 遍历树；
• • 遍历图；
• • 求连通块；
• • 网格搜索；
• • 判断是否可达。

网格 DFS 模型

典型题意

给一个 n × m 的地图，. 表示空地，# 表示障碍，求从起点能到达多少格子。

DFS 代码

#include<bits/stdc++.h>usingnamespace std;int n, m;char a[105][105];bool vis[105][105];int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};int cnt = 0;voiddfs(int x, int y){    vis[x][y] = true;    cnt++;for (int k = 0; k < 4; k++) {int nx = x + dx[k];int ny = y + dy[k];if (nx < 1 || nx > n || ny < 1 || ny > m) continue;if (vis[nx][ny]) continue;if (a[nx][ny] == '#') continue;dfs(nx, ny);    }}intmain(){    cin >> n >> m;int sx, sy;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {            cin >> a[i][j];if (a[i][j] == 'S') {                sx = i;                sy = j;            }        }    }dfs(sx, sy);    cout << cnt << endl;return0;}

DFS 适合解决什么？

5.2 BFS 广度优先搜索

题型特征

BFS 常用于无权图最短路。

例如：

• • 迷宫最短步数；
• • 棋盘最少移动次数；
• • 从一个状态变成另一个状态的最少操作数。

BFS 标准模型

queue<pair<int, int>> q;q.push({sx, sy});vis[sx][sy] = true;dist[sx][sy] = 0;while (!q.empty()) {auto [x, y] = q.front();    q.pop();for (int k = 0; k < 4; k++) {int nx = x + dx[k];int ny = y + dy[k];if (越界) continue;if (不能走) continue;if (vis[nx][ny]) continue;        vis[nx][ny] = true;        dist[nx][ny] = dist[x][y] + 1;        q.push({nx, ny});    }}

BFS 与 DFS 的区别

6. 栈的应用类

题型特征

六级栈题通常考：

• • 括号匹配；
• • 字符消除；
• • 最近未匹配元素；
• • 简单表达式处理。

6.1 括号匹配

典型题意

给一个括号序列，判断是否合法。

例如：

()[]{} 合法([)] 不合法(() 不合法

核心思路

遇到左括号，入栈。

遇到右括号，检查栈顶是否匹配：

• • 匹配：弹出；
• • 不匹配：非法。

最后栈为空才合法。

代码

#include<bits/stdc++.h>usingnamespace std;boolmatch(char l, char r){return (l == '(' && r == ')') ||           (l == '[' && r == ']') ||           (l == '{' && r == '}');}intmain(){    string s;    cin >> s;    stack<char> st;for (char c : s) {if (c == '(' || c == '[' || c == '{') {            st.push(c);        } else {if (st.empty()) {                cout << "No" << endl;return0;            }if (!match(st.top(), c)) {                cout << "No" << endl;return0;            }            st.pop();        }    }if (st.empty()) cout << "Yes" << endl;else cout << "No" << endl;return0;}

6.2 消除操作

典型题意

给一个字符串，相邻两个字符相同就消除，问最终剩下什么。

例如：

abbaca

处理过程：

abbaca -> aaca -> ca

核心思路

用栈模拟：

• • 如果栈空或当前字符和栈顶不同，入栈；
• • 如果当前字符和栈顶相同，弹栈，表示消除。

代码思路

string s;cin >> s;string st;for (char c : s) {if (!st.empty() && st.back() == c) {        st.pop_back();    } else {        st.push_back(c);    }}cout << st << endl;

7. 归并排序与逆序对类

题型特征

逆序对是六级经典分治题。

对于数组 a，如果 i < j 且：

a[i] > a[j]

那么 (i, j) 是一个逆序对。

要求统计逆序对数量。

为什么不能暴力？

暴力做法：

for i = 1 to nfor j = i + 1 to nif a[i] > a[j] ans++;

时间复杂度是：

O(n^2)

如果 n 很大，会超时。

归并排序统计逆序对

归并排序分为三步：

1. 1. 递归排序左半部分；
2. 2. 递归排序右半部分；
3. 3. 合并两个有序数组。

逆序对分三类：

核心逻辑

合并时，如果：

a[i] > a[j]

由于左半边已经有序，所以 a[i] ~ a[mid] 都大于 a[j]。

因此新增逆序对数量：

mid - i + 1

代码

#include<bits/stdc++.h>usingnamespace std;constint N = 1000005;longlong a[N], tmp[N];longlong ans = 0;voidmerge_sort(int l, int r){if (l >= r) return;int mid = (l + r) / 2;merge_sort(l, mid);merge_sort(mid + 1, r);int i = l, j = mid + 1, k = l;while (i <= mid && j <= r) {if (a[i] <= a[j]) {            tmp[k++] = a[i++];        } else {            tmp[k++] = a[j++];            ans += mid - i + 1;        }    }while (i <= mid) tmp[k++] = a[i++];while (j <= r) tmp[k++] = a[j++];for (int p = l; p <= r; p++) {        a[p] = tmp[p];    }}intmain(){int n;    cin >> n;for (int i = 1; i <= n; i++) {        cin >> a[i];    }merge_sort(1, n);    cout << ans << endl;return0;}

易错点

1. 1. 答案可能很大，要用 long long；
2. 2. 合并时条件建议写 a[i] <= a[j]，避免重复元素被误算；
3. 3. 临时数组 tmp 复制回原数组；
4. 4. 下标边界要统一。

三、六级真题常见综合题型

综合题型 1：DP + 前缀思想

题型特征

题目看起来像普通 DP，但每次转移要从前面多个状态中取最大值或求和。

普通写法：

dp[i] = dp[1] + dp[2] + ... + dp[i - 1]

如果直接循环，会变成 O(n^2)。

可以用前缀和优化：

sum[i] = dp[1] + dp[2] + ... + dp[i]

于是：

dp[i] = sum[i - 1]

综合题型 2：网格 BFS / DFS

题型特征

地图中有障碍、起点、终点，问：

• • 能否到达；
• • 最少步数；
• • 连通区域大小；
• • 有几个连通块。

选择方法

综合题型 3：树上 DFS + DP

题型特征

给一棵树，节点有权值或限制，需要自底向上合并子树答案。

常见步骤：

1. 1. 建图；
2. 2. 从根节点 DFS；
3. 3. 递归处理每个子节点；
4. 4. 把子节点答案合并到父节点；
5. 5. 输出根节点答案。

四、六级各类题目的解题模板总结

1. 线性 DP 解题步骤

1. 确定 dp[i] 表示什么2. 思考第 i 个状态从哪里来3. 写出状态转移方程4. 设置初始值5. 按正确顺序循环6. 输出答案

2. 背包 DP 解题步骤

1. 判断物品是否只能选一次2. 判断容量是什么3. 判断价值是什么4. 设计 dp[j]5. 写转移方程6. 确定 j 是正序还是倒序

背包方向口诀

01 背包倒着跑，完全背包正着跑。

3. DFS / BFS 解题步骤

1. 明确状态是什么，例如坐标、节点编号2. 明确可以走到哪些新状态3. 判断边界和障碍4. 用 vis 数组防止重复访问5. DFS 用递归，BFS 用队列

4. 树形 DP 解题步骤

1. 把无根树转成有根树2. 定义 dp[u] 或 dp[u][0/1]3. DFS 处理所有子节点4. 用子节点答案更新父节点5. 根节点答案就是整棵树答案

五、六级备考重点排序

如果你要准备 GESP C++ 六级，建议按下面顺序复习：

第一阶段：必须掌握

1. 1. 线性 DP
2. 2. 01 背包
3. 3. 完全背包
4. 4. DFS 遍历
5. 5. BFS 最短步数

这是六级得分的基本盘。

第二阶段：重点突破

1. 6. 栈的应用
2. 7. 树的 DFS
3. 8. 简单树形 DP
4. 9. 归并排序
5. 10. 逆序对统计

这部分决定能不能稳定拿高分。

第三阶段：综合训练

1. 11. DP + 前缀和优化
2. 12. 树上 DP 变形
3. 13. 图的连通块问题
4. 14. 网格 BFS / DFS
5. 15. 背包方案数问题

这部分用于冲刺 90 分以上。

六、常见失分点总结

七、六级复习建议

如果目标是 60 分

重点掌握：

• • 线性 DP；
• • 01 背包；
• • DFS / BFS 基础；
• • 栈模拟。

能把这些题做稳，六级基本可以通过。

如果目标是 80 分

还需要掌握：

• • 完全背包；
• • 树的 DFS；
• • 图连通块；
• • 逆序对；
• • 简单树形 DP。

如果目标是 90 分以上

需要进一步训练：

• • DP 变形题；
• • 背包方案数；
• • 树形 DP 综合；
• • BFS 状态设计；
• • 分治思想与复杂度分析。

八、推荐练习顺序

建议按照以下顺序刷题：

线性 DP↓01 背包↓完全背包↓栈模拟↓DFS / BFS↓树的遍历↓树形 DP↓归并排序 / 逆序对↓综合模拟真题

不要一开始就做树形 DP 或综合题，六级的关键是先把 DP 和搜索基础打牢。

九、一句话总结

GESP C++ 六级的本质是：

从“会写程序”过渡到“会设计基础算法”。

其中最重要的三条主线是：

动态规划：线性 DP、背包 DP搜索遍历：DFS、BFS、树和图经典算法：栈、归并排序、逆序对

如果这三条线掌握扎实，六级真题大部分都能稳定拿分。