刚查到202603那场GESP六级成绩的时候，我盯着屏幕愣了好一会儿。不是为了分数，而是因为考试时第三题那个“优惠券最短路”差点没写完，第四题数位DP又栽在前导零上，考完复盘觉得自己像个漏勺，哪儿都在漏水。这篇文章不打算写成标准答案式题解，我想把整场考试从进场到收卷的真实过程、四道编程题的完整解题思路、以及那些考场上踩中的坑都摊开讲一遍，给后面准备六级的朋友一个参照。
先说清楚一件事：GESP六级编程题到底考什么。它不像一级二级那样考语法填空，也不像三级四级那样考单一算法模板。六级基本是算法综合场，贪心、搜索、图论、动态规划都会出现，而且每道题都藏着一个“看起来简单、做起来要命”的拐点。202603这场给我的整体感觉是：前三题是保分题，但保分题里也埋着雷，第四题则是真正的分水岭。下面我按考场上的实际顺序，把这四道题从头到尾拆开。
1. 202603六级这场的整体印象
1.1 为什么说这场“难忘”
说实话，GESP六级我准备了小半年，洛谷上CSP-J难度的题刷了快两百道，模拟卷也做了好几套。但真正坐到机房里，面对202603这四道题的时候，还是被狠狠上了一课。第一题看起来是个人都会的排序题，第二题是个迷宫BFS，第三题是最短路加了一个“优惠券”，第四题是数位统计——都是常见面孔，但每道题的细节都比表面复杂。
我最深的感受是：六级真正的难点不在“知道算法”，而在“知道什么时候用哪个算法”。比如第一题，如果你一上来就按服务时间sort，大概率只能过样例，后面的大数据点全挂。第二题，如果你老老实实写二维BFS，收集完所有宝箱这个条件就会让你直接卡死。第三题的分层图倒是不难认，但堆优化的转移写不熟就会超时。第四题反而是最老实的数位DP，可惜我栽在了前导零的处理上。
这就是为什么我说难忘，不是难到做不出来，而是每一道题都在你熟悉的领域里挖了一个小坑，等着你踩。
1.2 编程题结构与六级难度定位
202603六级的编程题部分一共四道题，整体风格可以用一句话概括：CSP-J普及组T3/T4的难度，加上GESP特有的“小杨式”生活化包装。第一题小杨的食堂排队，第二题小杨的迷宫寻宝，第三题小杨的城市网络，第四题小杨的数字游戏——题目里的主人公永远是那个小杨，但内核都是标准算法题。
从分值和通过率角度来看，按往年经验，第一题是送分题，只要不犯低级错误基本稳拿；第二题是搜索题，会状态压缩BFS就能过；第三题是图论题，考察分层图最短路，属于六级考纲里的高频难点；第四题是数位DP，属于拉开差距的压轴题，很多人写到这题已经没时间了。
我的建议是：目标通过的同学，前三题必须拿下，第四题至少写出暴力枚举版本拿部分分；目标高分的同学，四道题都要冲。下面我把每道题从题意到代码完整过一遍。
2. 考场实录：时间分配和心态管理
2.1 进场后的前20分钟我干了什么
上机考试有个非常容易犯的错误：登录进去就开始闷头敲代码。我这次故意改变策略，先进去把四道题全部通读一遍，边读边在草稿纸上记录每道题的数据范围和关键词。
第一题的n到10万，一看就是贪心加堆；第二题的k小于等于10，这是状态压缩的强烈信号；第三题的m到20万，最短路没跑；第四题L和R能到10的18次方，枚举必然不可能，数位DP或者组合数学二选一。整个读题加标记过程大概花了15分钟，这15分钟的价值，远远大于一上来就写第一题的那15分钟。
读完题之后我心里基本有数了：前两题稳，第三题需要集中精力写，第四题先做一个暴力版本兜底。这个判断帮我节省了大量时间，因为我知道什么时候该果断放弃局部优化。
2.2 四道题的时间预算与放弃策略
我的时间分配大致是这样：第一题20分钟写完加调试，第二题40分钟，第三题40到50分钟，剩下时间全砸在第四题上。这个预算建立在“第三题一次写对”的前提下，但事实上我第三题调了快一个小时，因为优先队列里存的状态类型写错了，导致dis数组更新异常。
这里分享一个考场上最实用的心态：不要跟一道题死磕超过40分钟。如果你在某道题上连续调试三次还找不到错误，最优策略是先把这道题的暴力版本写上，保证拿到部分分，然后跳去做下一题。六级每道题的数据分布里通常有小数据点，暴力能拿二十分三十分，比零分强得多。
我在第三题卡住的时候就是这么干的：先把不优化的Dijkstra写出来，过了前几个小点，再去补分层图的细节。最终那道题我用优化版本拿到了全分，但如果不是提前准备了暴力版本兜底，可能连部分分都丢光。
3. 第一题：小杨的食堂排队（贪心+堆模拟）
3.1 题意转化：别被“排队”两个字骗了
题目大意：食堂有一个打饭窗口，n个人来打饭，第i个人在a_i时刻到达，打饭需要t_i时间。窗口空闲的时候，会从所有已经到达但还没打饭的人里，选择一个打饭时间最短的人先服务。问所有人都打完饭，总共需要多长时间。
很多人的第一反应是：这不就是按t从小到大排序吗？错了。注意“到达时间a_i”这个条件，不是所有人一开始就站在窗口前。如果你直接按t排序，可能出现某个人的到达时间非常晚，但因为他t小被排在前面，导致窗口空转等待。所以这题的正确模型是：按时间轴模拟，窗口每空闲一次，就从“已到达未服务”的集合里挑t最小的。
这个模型本质上是一个带到达时间约束的短作业优先调度，也是贪心算法里非常经典的一类。它和生活里排队不一样的点在于：人可以晚到，但窗口不会等一个还没到的人，它只会在当前已经到场的人里挑活最轻的。
3.2 贪心为什么成立
这个贪心的正确性可以这样理解：当窗口空闲时，所有已经到达的人都在等待，无论选择其中哪一个，对后面还没到的人来说，等待的起点都是一样的——“窗口什么时候再次空闲”。为了让下一个到达者少等，我们应该尽快把当前这批人清空，所以选打饭时间最短的人是最优的。这是一个标准的“局部最优能推出全局最优”的交换论证：如果把两个顾客a、b交换服务顺序，t_a小于t_b却让先来的a后服务，那么交换之后总的完成时间只会提前或不变，不会变差。
实现上，因为要动态维护“已到达未服务的人里t最小的那个”，我们用一个最小堆。先把所有人按a排序，维护一个当前时间cur。循环：把a_i小于等于cur的人全部入堆，如果堆为空说明窗口在等人，直接把cur跳到下一个人的到达时间，然后继续入堆。从堆顶弹出一个人，cur加上他的t，同时累加完成时间。这样一遍扫描就能算完。
3.3 参考实现与易错点
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Person { ll a, t; bool operator < (const Person& other) const { if (a != other.a) return a < other.a; return t < other.t; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<Person> p(n); for (int i = 0; i < n; i++) { cin >> p[i].a >> p[i].t; } sort(p.begin(), p.end()); priority_queue<ll, vector<ll>, greater<ll>> pq; // 存打饭耗时 ll cur = 0, ans = 0; int idx = 0; while (idx < n || !pq.empty()) { if (pq.empty() && cur < p[idx].a) { cur = p[idx].a; // 窗口空闲，跳到下一个到达时间 } while (idx < n && p[idx].a <= cur) { pq.push(p[idx].t); idx++; } ll t = pq.top(); pq.pop(); cur += t; ans += cur; // 如果题目求总完成时间，这里改成 ans = max(ans, cur) 之类 } cout << ans << "\n"; return 0; }这题主要的坑有三个：
- 数据类型：n到10万，a和t都可能到10的9次方，cur累加起来会超过int范围，必须用long long。我身边就有同学因为忘了这条，大数据点全WA。
- cur的跳跃逻辑：当堆为空并且当前时间还没到下一个人的到达时间时，窗口空转，这期间cur要直接跳过去。如果不跳而是一秒一秒加，小数据能过，大数据直接超时。
- 排序关键字：先按a排序没错，但如果a相同，谁先入堆都行，因为堆会再按t选一次。千万别画蛇添足把排序里加上t的比较，虽然不影响正确性，但容易让人产生“这题是不是要按某种规则排”的误解。
4. 第二题：迷宫寻宝（状态压缩BFS）
4.1 为什么朴素的BFS会挂
题目大意：n乘m的网格迷宫，有障碍物，起点是S，终点是E，地图上有k个宝箱。小杨要从起点出发，收集完所有宝箱之后走到终点，每次可以上下左右移动一格，问最短步数。k小于等于10，n和m最大到50。
拿到这题，第一反应肯定是BFS求最短路。但注意“收集完所有宝箱”这个附加条件，它把问题彻底改变了。普通BFS的vis数组只记录坐标，它假设“同一个格子第二次走到，步数一定不比第一次少”。可是这个题里，你走到同一个格子时，身上带的宝箱集合可能不同——带着宝箱A的你和没带宝箱A的你，虽然是同一个坐标，但后续能走的路完全不一样。
举个极端例子：宝箱A在起点附近，宝箱B在终点附近。你第一次经过某个格子时没捡到A，第二次再经过时捡到了A，此时步数更多，但你必须走第二次。如果vis数组只记录坐标，第二次就被拦下来了，答案直接算不出来。
4.2 状态设计与转移
正确做法是把“当前坐标+已收集宝箱集合”看成一个完整状态。k最大10，宝箱集合用二进制mask表示，1的个数不超过10，2的10次方就是1024。所以状态总数是n乘m乘1024，最多50乘50乘1024，大约256万个状态，BFS完全跑得动。
起点状态是(sx, sy, 0)，终点状态是(ex, ey, (1<<k)-1)。转移的时候，每走一步，如果新格子上有宝箱i，就把mask的第i位变成1。vis数组开三维：vis[x][y][mask]，含义是“在x,y且宝箱集合为mask的状态是否访问过”。同一个格子可以反复进入，只要mask不同就可以重新入队。
这题还有个小陷阱：宝箱编号从0开始还是从1开始。题目如果给的是1到k，记得入队前减一。我在考场上就是这里写错了，导致mask一直对不上，调试了好久才发现是索引越界问题。
4.3 手写队列还是STL
#include <bits/stdc++.h> using namespace std; struct State { int x, y, mask, step; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; vector<string> grid(n); int sx, sy, ex, ey; vector<pair<int,int>> chest(k); int chestId[55][55]; memset(chestId, -1, sizeof(chestId)); for (int i = 0; i < n; i++) { cin >> grid[i]; for (int j = 0; j < m; j++) { if (grid[i][j] == 'S') { sx = i; sy = j; } if (grid[i][j] == 'E') { ex = i; ey = j; } } } for (int i = 0; i < k; i++) { cin >> chest[i].first >> chest[i].second; chestId[chest[i].first][chest[i].second] = i; } bool vis[55][55][1024]; memset(vis, 0, sizeof(vis)); int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; queue<State> q; q.push({sx, sy, 0, 0}); vis[sx][sy][0] = true; while (!q.empty()) { State cur = q.front(); q.pop(); int fullMask = (1 << k) - 1; if (cur.x == ex && cur.y == ey && cur.mask == fullMask) { cout << cur.step << "\n"; return 0; } for (int d = 0; d < 4; d++) { int nx = cur.x + dx[d]; int ny = cur.y + dy[d]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (grid[nx][ny] == '#') continue; int nmask = cur.mask; if (chestId[nx][ny] != -1) { nmask |= (1 << chestId[nx][ny]); } if (!vis[nx][ny][nmask]) { vis[nx][ny][nmask] = true; q.push({nx, ny, nmask, cur.step + 1}); } } } cout << -1 << "\n"; return 0; }关于手写队列还是用STL，我的建议是：六级考场直接用STL的queue就行，因为状态量撑死256万，内存完全够。但四题里如果有比这更大的搜索题，比如状态上千万，手写数组模拟队列会更稳妥，因为STL的queue在频繁push和pop时有额外开销，而且调试环形数组比调试queue难看多了。这题的坑一个是vis数组别开小了，一个是终点检查别放在循环外，因为有可能起点就是终点且k等于0——虽然这题大概率不会这么出，但养成把出口判断写在出队时的习惯总没错。
5. 第三题：小杨的城市网络（分层图最短路）
5.1 一个优惠券为什么值得开一层新图
题目大意：n个城市，m条双向道路，每条路走一次需要一定时间。小杨从城市1出发去城市n，路途中最多可以使用一次“优惠券”，可以让某条道路的通行时间减半（向下取整）。问最少时间。
如果题目没有优惠券，就是一个裸的Dijkstra，没什么好说的。但是加了一张优惠券之后，状态就不能只是“我在哪个城市”了，还得记录“我用过券没有”。这就是分层图的经典思路：把原图复制成两层，第一层表示还没用券，第二层表示已经用过了。同一层内部，城市之间的边权保持原样；跨层之间，从第一层的u到第二层的v有一条边权为原来一半的边，表示“我在u到v这条路上使用了优惠券”。第二层内部不能再用券，所以第二层只有普通边。
这个模型最妙的地方在于，它把“用没用券”这个记忆变成了图上的层次，跑一遍Dijkstra就能同时得到用券和不用券两种情况的最短路。实际实现不需要真的把边存两遍，可以在松弛的时候用if判断。
5.2 转移方程与堆优化细节
用dis[0][u]表示到城市u且没用券的最短时间，dis[1][u]表示到城市u且已经用过券的最短时间。初始dis[0][1]=0，dis[1][1]=0。每次从堆里弹出当前最小状态，做两类松弛：
- 不用券：dis[nowLayer][v] = min(dis[nowLayer][v], dis[nowLayer][u] + w)
- 用券（只有nowLayer为0才能做）：dis[1][v] = min(dis[1][v], dis[0][u] + w / 2)
这里有一个容易忽略的细节：w除以2要向下取整，而原题如果是整数边权，w/2在C++整数除法里会自动向下取整，所以直接用w/2没问题。但如果你习惯用double存距离，这题就会出大问题，因为原题要求输出整数，double的精度会带来边界误差。这题必须全程用整数。
堆里存什么？最方便的是存pair<long long, pair<int,int>>，外面是距离，里面是(层号,城市编号)。也可以把层号编码成一个整数，比如u*2+layer，但那样状态转移时容易写乱。我考场上就是因为先用了编码方式，写错了几次，后来改成pair嵌套才理顺。
5.3 样例推演和边界检查
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, pair<int,int>> plii; const ll INF = 4e18; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<pair<int,int>>> g(n + 1); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); } vector<vector<ll>> dis(2, vector<ll>(n + 1, INF)); priority_queue<plii, vector<plii>, greater<plii>> pq; dis[0][1] = 0; dis[1][1] = 0; pq.push({0, {0, 1}}); while (!pq.empty()) { auto [d, st] = pq.top(); pq.pop(); int layer = st.first; int u = st.second; if (d > dis[layer][u]) continue; for (auto [v, w] : g[u]) { // 同一层走普通边 if (dis[layer][v] > d + w) { dis[layer][v] = d + w; pq.push({dis[layer][v], {layer, v}}); } // 第0层才能用券跳到第1层 if (layer == 0 && dis[1][v] > d + w / 2) { dis[1][v] = d + w / 2; pq.push({dis[1][v], {1, v}}); } } } cout << min(dis[0][n], dis[1][n]) << "\n"; return 0; }验证一个小样例：3个城市，三条边分别是1-2权10，2-3权10，1-3权15。不走1-3直达的话，1到2再到3合计20，如果用券在1-3上用，15减半变成7，答案是7。代码跑出来确实是7。边界情况：如果m为0且n为1，起点就是终点，答案是0；如果n为2只有一条边，用券变成w/2，也没问题。
这题真要感谢我在考场上坚持写完暴力版本兜底。中间有一阵子我priority_queue的greater比较器写错了，编译报错，我心态差点崩了。后来冷静下来发现是我把pair嵌套的类型写得不一致。考场上遇到这种问题，第一件事不是反复读代码，而是把类型对齐检查一遍。
6. 第四题：互不相同的数字（数位DP）
6.1 范围到10^18说明不能枚举
题目大意：给定正整数L和R，问区间[L,R]里有多少个整数，满足它的各位数字互不相同。例如123满足，122不满足，10满足，11不满足。L和R可以大到10的18次方。
如果直接枚举L到R，复杂度爆炸。10的18次方是什么概念，就是一百亿亿，一秒跑一亿次也要跑三十一年。看到这种范围，必须想到数位DP。
数位DP本质上是一个带记忆化的深度优先搜索，它把“小于等于某个上限的所有数”按位拆开，从高位到低位逐位枚举，同时用记忆化数组缓存中间结果。它最大的优势是复杂度只跟位数有关，位数再多也就19位，所以即使是10的18次方的大范围，在数位DP眼里和100没什么区别。
6.2 记忆化搜索的状态与转移
我习惯用递归写法，因为不容易出错。状态设计如下：
- pos：当前处理到第几位，从最高位往最低位走。
- mask：一个10位的二进制状态，第i位为1表示数字i已经出现过了。
- limit：当前是否顶着枚举上限。比如上限是12345，当前位已经填了12，那下一位最多只能填3；如果当前位填的是1（小于上限的2），那后面随便填。
- started：是否已经开始了一个非零的数。这个维度专门用来处理前导零。
转移的时候枚举当前位填的数字d从0到9。如果d等于0且started为假，说明还是前导零阶段，不把0计入mask，继续往后搜。如果d不等于0或者started为真，就要检查mask的第d位是否为1，如果已经是1说明出现了重复数字，直接跳过；否则把第d位置1，继续递归。
记忆化的时候要注意：只有limit为假的状态才能缓存。因为limit为真意味着后面的选择被束缚住了，不是所有情况都能达到，缓存了会导致错误答案。
6.3 前导零与返回值的两个大坑
#include <bits/stdc++.h> using namespace std; typedef long long ll; int digit[20]; ll f[20][1 << 10][2]; ll dfs(int pos, int mask, bool limit, bool started) { if (pos == -1) { return started ? 1 : 0; } if (!limit && f[pos][mask][started] != -1) { return f[pos][mask][started]; } int up = limit ? digit[pos] : 9; ll ans = 0; for (int d = 0; d <= up; d++) { if (!started && d == 0) { // 前导零，不产生任何数字，mask不变 ans += dfs(pos - 1, mask, limit && d == up, false); } else { if (mask & (1 << d)) continue; // 已出现过这个数字 ans += dfs(pos - 1, mask | (1 << d), limit && d == up, true); } } if (!limit) f[pos][mask][started] = ans; return ans; } ll countValid(ll x) { if (x <= 0) return 0; int len = 0; while (x > 0) { digit[len++] = x % 10; x /= 10; } // digit[0]是低位，dfs从len-1高位开始 memset(f, -1, sizeof(f)); return dfs(len - 1, 0, true, false); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll L, R; cin >> L >> R; cout << countValid(R) - countValid(L - 1) << "\n"; return 0; }这个代码里有两个特别容易错的点，我都栽过。
第一，返回值的判断。在pos == -1的时候，如果started为假，说明这个数从头到尾全是前导零，其实就是0。题目只统计正整数，而且L从1开始，所以这种情况应该返回0而不是1。如果写错了，会把0也算进答案，小数据对不上，大数据差1，非常难发现。
第二，前导零不能进mask。数字0在最高位作为前导零出现时，不代表数字0真的出现了。比如数10，它各位数字是1和0，是合法的。如果前导零也算进mask，那么处理到个位的0时，会发现mask第0位已经是1，直接跳过，导致10被错误判定为不合法。这个坑我在考场上花了十分钟才看出来，所以现在写出来提醒大家千万别踩。
这道题还有一个常见的优化变种：如果题目还要求“各位数字之和能被3整除”之类的附加条件，只需在状态里再加一个sum维度即可，架构完全一样。我自己练习时经常把几个数位DP变体都写一遍，确保状态设计灵活度足够。
7. 考后复盘
7.1 这次最容易丢分的三个地方
考完之后我对着四道题做了完整复盘，总结了三个最容易丢分的环节，也都是大家普遍容易出问题的点。
第一个是数据类型。四道题里每一道都藏着超过int范围的累加，第一题的cur，第三题的dis，第四题的答案，甚至第二题的step理论上也可能超过10万级别的int。很多同学在Dev-C++里跑样例没问题，一交上去大数据点WA到崩溃，大概率就是int不够用。
第二个是状态维度的遗漏。第二题的vis数组少开mask那一维、第三题忘记区分用没用过券，都属于这一类。这类错误的特点是小数据能过，大数据超时或者答案偏大。因为少了状态维度，实际搜索或最短路被错误剪枝，算出来的答案不是真实最优解。
第三个是数位DP的前导零处理。这个我不多说了，上面已经讲得很清楚。它属于一眼看不出来、一调试就崩溃的问题，因为答案总是差那么一点，而且差的那一点还不是固定值。
7.2 七级方向与备考建议
考完六级，下一个目标自然是七级。以我的经验看，六级到七级之间的跨度比想象中大，因为七级开始就会涉及更复杂的动态规划模型、树链剖分、网络流基础等内容。如果你六级考得还行，建议趁热打铁，把洛谷上的提高组专题刷起来；如果六级压线过甚至没过，那得回头把基础算法再过一遍，尤其是图论和DP这两个大头。
我个人的备考建议有三个：第一，每周至少写两套完整的模拟卷，而且必须限时。GESP六级机考的时间其实挺紧张，很多人不是不会做，是来不及做，模拟训练能显著提升时间感。第二，每道错题都要写复盘笔记，记录“为什么错”，而不是只记“答案是什么”。我这次第三题的pair类型错误，如果当初记录过类似问题，考场上就不会浪费二十分钟。第三，把常见算法的模板代码背熟到能默写。分层图、状态压缩BFS、数位DP这三个模板，在六级考场上的出现频率极高，能默写就等于白送分。
最后一次实话实说：这四道题里，只有第四题是真正需要天赋和大量刷题积累的，前三题只要准备充分、细心，拿分并不难。但“不拿分”和“拿分”之间的距离，往往就是一次数据类型溢出、一次状态少开一维、一次前导零的疏忽。希望这篇复盘能帮你把这些坑提前填上，等你在考场上遇到它们的时候，可以直接绕过去。
