GESP六级202603场复盘：四道编程题解题思路与避坑指南

刚查到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; vectorPerson p(n); for (int i 0; i n; i) { cin p[i].a p[i].t; } sort(p.begin(), p.end()); priority_queuell, vectorll, greaterll 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. 第二题迷宫寻宝状态压缩BFS4.1 为什么朴素的BFS会挂题目大意n乘m的网格迷宫有障碍物起点是S终点是E地图上有k个宝箱。小杨要从起点出发收集完所有宝箱之后走到终点每次可以上下左右移动一格问最短步数。k小于等于10n和m最大到50。拿到这题第一反应肯定是BFS求最短路。但注意“收集完所有宝箱”这个附加条件它把问题彻底改变了。普通BFS的vis数组只记录坐标它假设“同一个格子第二次走到步数一定不比第一次少”。可是这个题里你走到同一个格子时身上带的宝箱集合可能不同——带着宝箱A的你和没带宝箱A的你虽然是同一个坐标但后续能走的路完全不一样。举个极端例子宝箱A在起点附近宝箱B在终点附近。你第一次经过某个格子时没捡到A第二次再经过时捡到了A此时步数更多但你必须走第二次。如果vis数组只记录坐标第二次就被拦下来了答案直接算不出来。4.2 状态设计与转移正确做法是把“当前坐标已收集宝箱集合”看成一个完整状态。k最大10宝箱集合用二进制mask表示1的个数不超过102的10次方就是1024。所以状态总数是n乘m乘1024最多50乘50乘1024大约256万个状态BFS完全跑得动。起点状态是(sx, sy, 0)终点状态是(ex, ey, (1k)-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; vectorstring grid(n); int sx, sy, ex, ey; vectorpairint,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}; queueState 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]0dis[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的精度会带来边界误差。这题必须全程用整数。堆里存什么最方便的是存pairlong long, pairint,int外面是距离里面是(层号,城市编号)。也可以把层号编码成一个整数比如u*2layer但那样状态转移时容易写乱。我考场上就是因为先用了编码方式写错了几次后来改成pair嵌套才理顺。5.3 样例推演和边界检查#include bits/stdc.h using namespace std; typedef long long ll; typedef pairll, pairint,int plii; const ll INF 4e18; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorpairint,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}); } vectorvectorll dis(2, vectorll(n 1, INF)); priority_queueplii, vectorplii, greaterplii 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权102-3权101-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. 第四题互不相同的数字数位DP6.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这三个模板在六级考场上的出现频率极高能默写就等于白送分。最后一次实话实说这四道题里只有第四题是真正需要天赋和大量刷题积累的前三题只要准备充分、细心拿分并不难。但“不拿分”和“拿分”之间的距离往往就是一次数据类型溢出、一次状态少开一维、一次前导零的疏忽。希望这篇复盘能帮你把这些坑提前填上等你在考场上遇到它们的时候可以直接绕过去。