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