剛查到202603那場GESP六級成績的時候我盯著屏幕愣了好一會兒。不是為了分數(shù)而是因為考試時第三題那個“優(yōu)惠券最短路”差點沒寫完第四題數(shù)位DP又栽在前導零上考完復盤覺得自己像個漏勺哪兒都在漏水。這篇文章不打算寫成標準答案式題解我想把整場考試從進場到收卷的真實過程、四道編程題的完整解題思路、以及那些考場上踩中的坑都攤開講一遍給后面準備六級的朋友一個參照。先說清楚一件事GESP六級編程題到底考什么。它不像一級二級那樣考語法填空也不像三級四級那樣考單一算法模板。六級基本是算法綜合場貪心、搜索、圖論、動態(tài)規(guī)劃都會出現(xiàn)而且每道題都藏著一個“看起來簡單、做起來要命”的拐點。202603這場給我的整體感覺是前三題是保分題但保分題里也埋著雷第四題則是真正的分水嶺。下面我按考場上的實際順序把這四道題從頭到尾拆開。1. 202603六級這場的整體印象1.1 為什么說這場“難忘”說實話GESP六級我準備了小半年洛谷上CSP-J難度的題刷了快兩百道模擬卷也做了好幾套。但真正坐到機房里面對202603這四道題的時候還是被狠狠上了一課。第一題看起來是個人都會的排序題第二題是個迷宮BFS第三題是最短路加了一個“優(yōu)惠券”第四題是數(shù)位統(tǒng)計——都是常見面孔但每道題的細節(jié)都比表面復雜。我最深的感受是六級真正的難點不在“知道算法”而在“知道什么時候用哪個算法”。比如第一題如果你一上來就按服務時間sort大概率只能過樣例后面的大數(shù)據(jù)點全掛。第二題如果你老老實實寫二維BFS收集完所有寶箱這個條件就會讓你直接卡死。第三題的分層圖倒是不難認但堆優(yōu)化的轉(zhuǎn)移寫不熟就會超時。第四題反而是最老實的數(shù)位DP可惜我栽在了前導零的處理上。這就是為什么我說難忘不是難到做不出來而是每一道題都在你熟悉的領域里挖了一個小坑等著你踩。1.2 編程題結(jié)構與六級難度定位202603六級的編程題部分一共四道題整體風格可以用一句話概括CSP-J普及組T3/T4的難度加上GESP特有的“小楊式”生活化包裝。第一題小楊的食堂排隊第二題小楊的迷宮尋寶第三題小楊的城市網(wǎng)絡第四題小楊的數(shù)字游戲——題目里的主人公永遠是那個小楊但內(nèi)核都是標準算法題。從分值和通過率角度來看按往年經(jīng)驗第一題是送分題只要不犯低級錯誤基本穩(wěn)拿第二題是搜索題會狀態(tài)壓縮BFS就能過第三題是圖論題考察分層圖最短路屬于六級考綱里的高頻難點第四題是數(shù)位DP屬于拉開差距的壓軸題很多人寫到這題已經(jīng)沒時間了。我的建議是目標通過的同學前三題必須拿下第四題至少寫出暴力枚舉版本拿部分分目標高分的同學四道題都要沖。下面我把每道題從題意到代碼完整過一遍。2. 考場實錄時間分配和心態(tài)管理2.1 進場后的前20分鐘我干了什么上機考試有個非常容易犯的錯誤登錄進去就開始悶頭敲代碼。我這次故意改變策略先進去把四道題全部通讀一遍邊讀邊在草稿紙上記錄每道題的數(shù)據(jù)范圍和關鍵詞。第一題的n到10萬一看就是貪心加堆第二題的k小于等于10這是狀態(tài)壓縮的強烈信號第三題的m到20萬最短路沒跑第四題L和R能到10的18次方枚舉必然不可能數(shù)位DP或者組合數(shù)學二選一。整個讀題加標記過程大概花了15分鐘這15分鐘的價值遠遠大于一上來就寫第一題的那15分鐘。讀完題之后我心里基本有數(shù)了前兩題穩(wěn)第三題需要集中精力寫第四題先做一個暴力版本兜底。這個判斷幫我節(jié)省了大量時間因為我知道什么時候該果斷放棄局部優(yōu)化。2.2 四道題的時間預算與放棄策略我的時間分配大致是這樣第一題20分鐘寫完加調(diào)試第二題40分鐘第三題40到50分鐘剩下時間全砸在第四題上。這個預算建立在“第三題一次寫對”的前提下但事實上我第三題調(diào)了快一個小時因為優(yōu)先隊列里存的狀態(tài)類型寫錯了導致dis數(shù)組更新異常。這里分享一個考場上最實用的心態(tài)不要跟一道題死磕超過40分鐘。如果你在某道題上連續(xù)調(diào)試三次還找不到錯誤最優(yōu)策略是先把這道題的暴力版本寫上保證拿到部分分然后跳去做下一題。六級每道題的數(shù)據(jù)分布里通常有小數(shù)據(jù)點暴力能拿二十分三十分比零分強得多。我在第三題卡住的時候就是這么干的先把不優(yōu)化的Dijkstra寫出來過了前幾個小點再去補分層圖的細節(jié)。最終那道題我用優(yōu)化版本拿到了全分但如果不是提前準備了暴力版本兜底可能連部分分都丟光。3. 第一題小楊的食堂排隊貪心堆模擬3.1 題意轉(zhuǎn)化別被“排隊”兩個字騙了題目大意食堂有一個打飯窗口n個人來打飯第i個人在a_i時刻到達打飯需要t_i時間。窗口空閑的時候會從所有已經(jīng)到達但還沒打飯的人里選擇一個打飯時間最短的人先服務。問所有人都打完飯總共需要多長時間。很多人的第一反應是這不就是按t從小到大排序嗎錯了。注意“到達時間a_i”這個條件不是所有人一開始就站在窗口前。如果你直接按t排序可能出現(xiàn)某個人的到達時間非常晚但因為他t小被排在前面導致窗口空轉(zhuǎn)等待。所以這題的正確模型是按時間軸模擬窗口每空閑一次就從“已到達未服務”的集合里挑t最小的。這個模型本質(zhì)上是一個帶到達時間約束的短作業(yè)優(yōu)先調(diào)度也是貪心算法里非常經(jīng)典的一類。它和生活里排隊不一樣的點在于人可以晚到但窗口不會等一個還沒到的人它只會在當前已經(jīng)到場的人里挑活最輕的。3.2 貪心為什么成立這個貪心的正確性可以這樣理解當窗口空閑時所有已經(jīng)到達的人都在等待無論選擇其中哪一個對后面還沒到的人來說等待的起點都是一樣的——“窗口什么時候再次空閑”。為了讓下一個到達者少等我們應該盡快把當前這批人清空所以選打飯時間最短的人是最優(yōu)的。這是一個標準的“局部最優(yōu)能推出全局最優(yōu)”的交換論證如果把兩個顧客a、b交換服務順序t_a小于t_b卻讓先來的a后服務那么交換之后總的完成時間只會提前或不變不會變差。實現(xiàn)上因為要動態(tài)維護“已到達未服務的人里t最小的那個”我們用一個最小堆。先把所有人按a排序維護一個當前時間cur。循環(huán)把a_i小于等于cur的人全部入堆如果堆為空說明窗口在等人直接把cur跳到下一個人的到達時間然后繼續(xù)入堆。從堆頂彈出一個人cur加上他的t同時累加完成時間。這樣一遍掃描就能算完。3.3 參考實現(xiàn)與易錯點#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; }這題主要的坑有三個數(shù)據(jù)類型n到10萬a和t都可能到10的9次方cur累加起來會超過int范圍必須用long long。我身邊就有同學因為忘了這條大數(shù)據(jù)點全WA。cur的跳躍邏輯當堆為空并且當前時間還沒到下一個人的到達時間時窗口空轉(zhuǎn)這期間cur要直接跳過去。如果不跳而是一秒一秒加小數(shù)據(jù)能過大數(shù)據(jù)直接超時。排序關鍵字先按a排序沒錯但如果a相同誰先入堆都行因為堆會再按t選一次。千萬別畫蛇添足把排序里加上t的比較雖然不影響正確性但容易讓人產(chǎn)生“這題是不是要按某種規(guī)則排”的誤解。4. 第二題迷宮尋寶狀態(tài)壓縮BFS4.1 為什么樸素的BFS會掛題目大意n乘m的網(wǎng)格迷宮有障礙物起點是S終點是E地圖上有k個寶箱。小楊要從起點出發(fā)收集完所有寶箱之后走到終點每次可以上下左右移動一格問最短步數(shù)。k小于等于10n和m最大到50。拿到這題第一反應肯定是BFS求最短路。但注意“收集完所有寶箱”這個附加條件它把問題徹底改變了。普通BFS的vis數(shù)組只記錄坐標它假設“同一個格子第二次走到步數(shù)一定不比第一次少”?？墒沁@個題里你走到同一個格子時身上帶的寶箱集合可能不同——帶著寶箱A的你和沒帶寶箱A的你雖然是同一個坐標但后續(xù)能走的路完全不一樣。舉個極端例子寶箱A在起點附近寶箱B在終點附近。你第一次經(jīng)過某個格子時沒撿到A第二次再經(jīng)過時撿到了A此時步數(shù)更多但你必須走第二次。如果vis數(shù)組只記錄坐標第二次就被攔下來了答案直接算不出來。4.2 狀態(tài)設計與轉(zhuǎn)移正確做法是把“當前坐標已收集寶箱集合”看成一個完整狀態(tài)。k最大10寶箱集合用二進制mask表示1的個數(shù)不超過102的10次方就是1024。所以狀態(tài)總數(shù)是n乘m乘1024最多50乘50乘1024大約256萬個狀態(tài)BFS完全跑得動。起點狀態(tài)是(sx, sy, 0)終點狀態(tài)是(ex, ey, (1k)-1)。轉(zhuǎn)移的時候每走一步如果新格子上有寶箱i就把mask的第i位變成1。vis數(shù)組開三維vis[x][y][mask]含義是“在x,y且寶箱集合為mask的狀態(tài)是否訪問過”。同一個格子可以反復進入只要mask不同就可以重新入隊。這題還有個小陷阱寶箱編號從0開始還是從1開始。題目如果給的是1到k記得入隊前減一。我在考場上就是這里寫錯了導致mask一直對不上調(diào)試了好久才發(fā)現(xiàn)是索引越界問題。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就行因為狀態(tài)量撐死256萬內(nèi)存完全夠。但四題里如果有比這更大的搜索題比如狀態(tài)上千萬手寫數(shù)組模擬隊列會更穩(wěn)妥因為STL的queue在頻繁push和pop時有額外開銷而且調(diào)試環(huán)形數(shù)組比調(diào)試queue難看多了。這題的坑一個是vis數(shù)組別開小了一個是終點檢查別放在循環(huán)外因為有可能起點就是終點且k等于0——雖然這題大概率不會這么出但養(yǎng)成把出口判斷寫在出隊時的習慣總沒錯。5. 第三題小楊的城市網(wǎng)絡分層圖最短路5.1 一個優(yōu)惠券為什么值得開一層新圖題目大意n個城市m條雙向道路每條路走一次需要一定時間。小楊從城市1出發(fā)去城市n路途中最多可以使用一次“優(yōu)惠券”可以讓某條道路的通行時間減半向下取整。問最少時間。如果題目沒有優(yōu)惠券就是一個裸的Dijkstra沒什么好說的。但是加了一張優(yōu)惠券之后狀態(tài)就不能只是“我在哪個城市”了還得記錄“我用過券沒有”。這就是分層圖的經(jīng)典思路把原圖復制成兩層第一層表示還沒用券第二層表示已經(jīng)用過了。同一層內(nèi)部城市之間的邊權保持原樣跨層之間從第一層的u到第二層的v有一條邊權為原來一半的邊表示“我在u到v這條路上使用了優(yōu)惠券”。第二層內(nèi)部不能再用券所以第二層只有普通邊。這個模型最妙的地方在于它把“用沒用券”這個記憶變成了圖上的層次跑一遍Dijkstra就能同時得到用券和不用券兩種情況的最短路。實際實現(xiàn)不需要真的把邊存兩遍可以在松弛的時候用if判斷。5.2 轉(zhuǎn)移方程與堆優(yōu)化細節(jié)用dis[0][u]表示到城市u且沒用券的最短時間dis[1][u]表示到城市u且已經(jīng)用過券的最短時間。初始dis[0][1]0dis[1][1]0。每次從堆里彈出當前最小狀態(tài)做兩類松弛不用券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)這里有一個容易忽略的細節(jié)w除以2要向下取整而原題如果是整數(shù)邊權w/2在C整數(shù)除法里會自動向下取整所以直接用w/2沒問題。但如果你習慣用double存距離這題就會出大問題因為原題要求輸出整數(shù)double的精度會帶來邊界誤差。這題必須全程用整數(shù)。堆里存什么最方便的是存pairlong long, pairint,int外面是距離里面是(層號,城市編號)。也可以把層號編碼成一個整數(shù)比如u*2layer但那樣狀態(tài)轉(zhuǎn)移時容易寫亂。我考場上就是因為先用了編碼方式寫錯了幾次后來改成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比較器寫錯了編譯報錯我心態(tài)差點崩了。后來冷靜下來發(fā)現(xiàn)是我把pair嵌套的類型寫得不一致。考場上遇到這種問題第一件事不是反復讀代碼而是把類型對齊檢查一遍。6. 第四題互不相同的數(shù)字數(shù)位DP6.1 范圍到10^18說明不能枚舉題目大意給定正整數(shù)L和R問區(qū)間[L,R]里有多少個整數(shù)滿足它的各位數(shù)字互不相同。例如123滿足122不滿足10滿足11不滿足。L和R可以大到10的18次方。如果直接枚舉L到R復雜度爆炸。10的18次方是什么概念就是一百億億一秒跑一億次也要跑三十一年。看到這種范圍必須想到數(shù)位DP。數(shù)位DP本質(zhì)上是一個帶記憶化的深度優(yōu)先搜索它把“小于等于某個上限的所有數(shù)”按位拆開從高位到低位逐位枚舉同時用記憶化數(shù)組緩存中間結(jié)果。它最大的優(yōu)勢是復雜度只跟位數(shù)有關位數(shù)再多也就19位所以即使是10的18次方的大范圍在數(shù)位DP眼里和100沒什么區(qū)別。6.2 記憶化搜索的狀態(tài)與轉(zhuǎn)移我習慣用遞歸寫法因為不容易出錯。狀態(tài)設計如下pos當前處理到第幾位從最高位往最低位走。mask一個10位的二進制狀態(tài)第i位為1表示數(shù)字i已經(jīng)出現(xiàn)過了。limit當前是否頂著枚舉上限。比如上限是12345當前位已經(jīng)填了12那下一位最多只能填3如果當前位填的是1小于上限的2那后面隨便填。started是否已經(jīng)開始了一個非零的數(shù)。這個維度專門用來處理前導零。轉(zhuǎn)移的時候枚舉當前位填的數(shù)字d從0到9。如果d等于0且started為假說明還是前導零階段不把0計入mask繼續(xù)往后搜。如果d不等于0或者started為真就要檢查mask的第d位是否為1如果已經(jīng)是1說明出現(xiàn)了重復數(shù)字直接跳過否則把第d位置1繼續(xù)遞歸。記憶化的時候要注意只有l(wèi)imit為假的狀態(tài)才能緩存。因為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) { // 前導零不產(chǎn)生任何數(shù)字mask不變 ans dfs(pos - 1, mask, limit d up, false); } else { if (mask (1 d)) continue; // 已出現(xiàn)過這個數(shù)字 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為假說明這個數(shù)從頭到尾全是前導零其實就是0。題目只統(tǒng)計正整數(shù)而且L從1開始所以這種情況應該返回0而不是1。如果寫錯了會把0也算進答案小數(shù)據(jù)對不上大數(shù)據(jù)差1非常難發(fā)現(xiàn)。第二前導零不能進mask。數(shù)字0在最高位作為前導零出現(xiàn)時不代表數(shù)字0真的出現(xiàn)了。比如數(shù)10它各位數(shù)字是1和0是合法的。如果前導零也算進mask那么處理到個位的0時會發(fā)現(xiàn)mask第0位已經(jīng)是1直接跳過導致10被錯誤判定為不合法。這個坑我在考場上花了十分鐘才看出來所以現(xiàn)在寫出來提醒大家千萬別踩。這道題還有一個常見的優(yōu)化變種如果題目還要求“各位數(shù)字之和能被3整除”之類的附加條件只需在狀態(tài)里再加一個sum維度即可架構完全一樣。我自己練習時經(jīng)常把幾個數(shù)位DP變體都寫一遍確保狀態(tài)設計靈活度足夠。7. 考后復盤7.1 這次最容易丟分的三個地方考完之后我對著四道題做了完整復盤總結(jié)了三個最容易丟分的環(huán)節(jié)也都是大家普遍容易出問題的點。第一個是數(shù)據(jù)類型。四道題里每一道都藏著超過int范圍的累加第一題的cur第三題的dis第四題的答案甚至第二題的step理論上也可能超過10萬級別的int。很多同學在Dev-C里跑樣例沒問題一交上去大數(shù)據(jù)點WA到崩潰大概率就是int不夠用。第二個是狀態(tài)維度的遺漏。第二題的vis數(shù)組少開mask那一維、第三題忘記區(qū)分用沒用過券都屬于這一類。這類錯誤的特點是小數(shù)據(jù)能過大數(shù)據(jù)超時或者答案偏大。因為少了狀態(tài)維度實際搜索或最短路被錯誤剪枝算出來的答案不是真實最優(yōu)解。第三個是數(shù)位DP的前導零處理。這個我不多說了上面已經(jīng)講得很清楚。它屬于一眼看不出來、一調(diào)試就崩潰的問題因為答案總是差那么一點而且差的那一點還不是固定值。7.2 七級方向與備考建議考完六級下一個目標自然是七級。以我的經(jīng)驗看六級到七級之間的跨度比想象中大因為七級開始就會涉及更復雜的動態(tài)規(guī)劃模型、樹鏈剖分、網(wǎng)絡流基礎等內(nèi)容。如果你六級考得還行建議趁熱打鐵把洛谷上的提高組專題刷起來如果六級壓線過甚至沒過那得回頭把基礎算法再過一遍尤其是圖論和DP這兩個大頭。我個人的備考建議有三個第一每周至少寫兩套完整的模擬卷而且必須限時。GESP六級機考的時間其實挺緊張很多人不是不會做是來不及做模擬訓練能顯著提升時間感。第二每道錯題都要寫復盤筆記記錄“為什么錯”而不是只記“答案是什么”。我這次第三題的pair類型錯誤如果當初記錄過類似問題考場上就不會浪費二十分鐘。第三把常見算法的模板代碼背熟到能默寫。分層圖、狀態(tài)壓縮BFS、數(shù)位DP這三個模板在六級考場上的出現(xiàn)頻率極高能默寫就等于白送分。最后一次實話實說這四道題里只有第四題是真正需要天賦和大量刷題積累的前三題只要準備充分、細心拿分并不難。但“不拿分”和“拿分”之間的距離往往就是一次數(shù)據(jù)類型溢出、一次狀態(tài)少開一維、一次前導零的疏忽。希望這篇復盤能幫你把這些坑提前填上等你在考場上遇到它們的時候可以直接繞過去。