1. 從賽場到復(fù)盤一次完整的國賽解題心路剛結(jié)束第十三屆藍(lán)橋杯國賽的C/C B組比賽從考場出來腦子還沉浸在那些算法邏輯和邊界條件里。這種級別的競賽題目本身固然是核心但解題過程中的思路拆解、工具運(yùn)用和心態(tài)調(diào)整其價(jià)值往往不亞于最終的答案。我把自己在賽場上的思考、實(shí)現(xiàn)以及賽后的一些反思整理出來這不僅僅是一份“題解”更像是一次完整的實(shí)戰(zhàn)復(fù)盤。無論你是即將參賽的選手還是對算法競賽感興趣的開發(fā)者希望這份結(jié)合了具體代碼、策略分析和踩坑記錄的經(jīng)驗(yàn)?zāi)芙o你帶來一些實(shí)實(shí)在在的參考。我們直接進(jìn)入正題看看這次國賽B組都考了些什么以及如何一步步拿下它們。2. 賽題整體分析與策略制定國賽的題目通常不會(huì)在奇技淫巧上做太多文章更側(cè)重于考察對基礎(chǔ)算法和數(shù)據(jù)結(jié)構(gòu)的深刻理解、縝密的邏輯思維以及將實(shí)際問題轉(zhuǎn)化為計(jì)算模型的能力。拿到題目后我習(xí)慣先用5-10分鐘快速通讀所有題目對難度和類型有個(gè)大致判斷而不是一頭扎進(jìn)第一題。2.1 題目概覽與難度評估這次B組的題目覆蓋面很廣。通常會(huì)有1-2道純簽到題考察基本語法和簡單邏輯2-3道需要用到經(jīng)典算法如DFS/BFS、動(dòng)態(tài)規(guī)劃、貪心的中等題以及1-2道對思維能力和代碼實(shí)現(xiàn)要求都較高的壓軸題?？焖贋g覽后我初步判斷前兩題屬于“必拿分”范疇主要防止粗心中間幾題是得分主力需要穩(wěn)扎穩(wěn)打最后一題則需要仔細(xì)分析爭取部分分?jǐn)?shù)。注意國賽時(shí)間寶貴切忌在簡單題上追求“最優(yōu)解”而浪費(fèi)過多時(shí)間。我們的目標(biāo)是總分最大化而不是某一道題完美。對于一眼就有清晰暴力解法的題先確保AC通過所有測試用例如果后面有時(shí)間再回來優(yōu)化。2.2 環(huán)境與工具的準(zhǔn)備要點(diǎn)工欲善其事必先利其器。比賽是在指定的OJ在線判題系統(tǒng)上進(jìn)行但前期的代碼編寫和測試離不開本地環(huán)境。編輯器/IDE選擇我使用的是VS Code搭配C/C插件。它的優(yōu)勢在于輕量、啟動(dòng)快并且代碼補(bǔ)全和跳轉(zhuǎn)功能足夠用。關(guān)鍵是要提前配置好基本的代碼片段Snippet比如快速生成freopen用于本地文件輸入輸出、生成常見算法框架如Dijkstra、快速冪等。輸入輸出重定向這是調(diào)試的利器。在main函數(shù)開頭加入以下代碼可以在本地測試時(shí)從文件讀取數(shù)據(jù)提交時(shí)只需注釋掉freopen行即可。#ifdef LOCAL freopen(“input.txt”, “r”, stdin); freopen(“output.txt”, “w”, stdout); #endif編譯時(shí)定義LOCAL宏如-DLOCAL就能自動(dòng)切換。調(diào)試與打印復(fù)雜邏輯的調(diào)試不能只靠腦子想。我通常會(huì)定義一個(gè)DEBUG宏在需要時(shí)輸出關(guān)鍵的中間變量值。#define DEBUG #ifdef DEBUG #define debug(x) cout #x “ “ x endl #else #define debug(x) #endif這樣用debug(a)就能方便地輸出變量a的值提交前關(guān)閉DEBUG宏即可。這些準(zhǔn)備工作看似瑣碎但在緊張的比賽環(huán)境中能為你節(jié)省大量時(shí)間并減少因低級錯(cuò)誤導(dǎo)致的失分。3. 核心題目詳解與實(shí)現(xiàn)思路下面我將挑選本屆比賽中幾道有代表性、能體現(xiàn)不同解題思維的題目進(jìn)行詳細(xì)拆解。為了還原真實(shí)的解題過程我會(huì)先描述題目大意非原題照搬避免版權(quán)問題然后逐步展開我的思考路徑和代碼實(shí)現(xiàn)。3.1 簽到題字符串處理與邊界陷阱題目大意給定一個(gè)字符串和一系列操作指令指令可能是翻轉(zhuǎn)某個(gè)子串也可能是查詢某個(gè)字符。最終輸出所有查詢結(jié)果。這看起來是一道簡單的模擬題。但國賽的“簡單題”往往藏著邊界條件的陷阱。思路拆解數(shù)據(jù)結(jié)構(gòu)選擇直接使用C的string類型存儲字符串是最方便的它支持下標(biāo)訪問和修改。操作模擬對于翻轉(zhuǎn)操作題目給定區(qū)間[l, r]通常下標(biāo)從1開始。我們需要將其轉(zhuǎn)換為C中從0開始的下標(biāo)然后使用std::reverse(s.begin() l, s.begin() r 1)即可高效完成。對于查詢操作直接輸出s[pos]。關(guān)鍵陷阱與實(shí)現(xiàn)下標(biāo)轉(zhuǎn)換這是最容易出錯(cuò)的地方。如果題目說“第l個(gè)到第r個(gè)字符”那么對應(yīng)到string的下標(biāo)就是l-1和r-1。我習(xí)慣在輸入l, r后立即執(zhí)行l(wèi)--; r--;讓所有后續(xù)操作都基于0-index進(jìn)行思考。輸入效率操作指令數(shù)量可能很大達(dá)到10^5級別。務(wù)必使用scanf或cin關(guān)閉同步流ios::sync_with_stdio(false);來加速輸入輸出。查詢輸出如果查詢很多不要每次查詢都cout一個(gè)字符然后換行這樣效率低?？梢韵葘⒉樵兘Y(jié)果存入一個(gè)string或vectorchar最后統(tǒng)一輸出。我的實(shí)現(xiàn)代碼片段#include iostream #include string #include algorithm using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin s; int m; cin m; while (m--) { int op, l, r, pos; cin op; if (op 1) { // 翻轉(zhuǎn)操作 cin l r; l--; r--; // 轉(zhuǎn)換為0-index reverse(s.begin() l, s.begin() r 1); } else { // 查詢操作 cin pos; pos--; // 轉(zhuǎn)換為0-index cout s[pos] ‘\n’; // 使用‘\n’而非endl } } return 0; }實(shí)操心得對于所有涉及區(qū)間下標(biāo)的題目在思維和代碼中統(tǒng)一使用一種索引方式強(qiáng)烈推薦0-index并在輸入后第一時(shí)間進(jìn)行轉(zhuǎn)換能極大降低思維負(fù)擔(dān)和出錯(cuò)概率。3.2 中等題圖論建模與BFS求最短路徑題目大意一個(gè)網(wǎng)格圖某些格子是障礙某些格子是傳送門成對出現(xiàn)可瞬間移動(dòng)。求從起點(diǎn)到終點(diǎn)的最少步數(shù)。每次移動(dòng)可以上下左右走到非障礙格子或者如果當(dāng)前格是傳送門可以花費(fèi)0步傳送到其配對格子。思路拆解問題本質(zhì)這是一個(gè)帶“0權(quán)邊”的最短路問題。普通格子間移動(dòng)邊權(quán)為1傳送門之間移動(dòng)邊權(quán)為0。求單源最短路自然想到BFS0-1 BFS或Dijkstra算法。由于邊權(quán)只有0和1使用0-1 BFS雙端隊(duì)列deque實(shí)現(xiàn)效率更高時(shí)間復(fù)雜度為O(N*M)。數(shù)據(jù)結(jié)構(gòu)建模用二維數(shù)組grid存儲地圖。用pairint, int的數(shù)組teleport記錄傳送門信息。當(dāng)輸入一對傳送門(A, B)時(shí)需要建立雙向的瞬間可達(dá)關(guān)系?？梢杂靡粋€(gè)map或二維數(shù)組來快速查詢某個(gè)坐標(biāo)是否為傳送門及其配對坐標(biāo)。算法實(shí)現(xiàn)細(xì)節(jié)0-1 BFS使用deque代替普通隊(duì)列。dist[x][y]記錄起點(diǎn)到(x,y)的最短距離初始化為無窮大。起點(diǎn)距離為0加入deque前端。當(dāng)隊(duì)列不空時(shí)從前端取出節(jié)點(diǎn)(x, y)。遍歷四個(gè)方向新坐標(biāo)(nx, ny)合法且非障礙如果dist[nx][ny] dist[x][y] 1則更新距離并將(nx, ny)推入隊(duì)列后端因?yàn)檫厵?quán)為1。關(guān)鍵步驟如果(x, y)是傳送門設(shè)其配對點(diǎn)為(tx, ty)。如果dist[tx][ty] dist[x][y]則更新距離并將(tx, ty)推入隊(duì)列前端因?yàn)檫厵?quán)為0。一個(gè)易錯(cuò)點(diǎn)傳送門是否可重復(fù)使用題目通常默認(rèn)可以。但如果傳送門使用后消失則需要用狀態(tài)標(biāo)記情況會(huì)更復(fù)雜本題未做此要求。我的實(shí)現(xiàn)代碼框架#include iostream #include vector #include deque #include cstring using namespace std; const int MAXN 1005; const int INF 0x3f3f3f3f; const int dx[4] {1, -1, 0, 0}; const int dy[4] {0, 0, 1, -1}; struct Point { int x, y; }; int n, m; char grid[MAXN][MAXN]; int dist[MAXN][MAXN]; Point teleport[MAXN][MAXN]; // teleport[x][y] 存儲配對點(diǎn)坐標(biāo)若為(-1,-1)則不是傳送門 bool isTele[MAXN][MAXN]; int bfs(Point start, Point end) { memset(dist, 0x3f, sizeof(dist)); dequePoint dq; dist[start.x][start.y] 0; dq.push_front(start); while (!dq.empty()) { Point cur dq.front(); dq.pop_front(); int x cur.x, y cur.y; // 如果到達(dá)終點(diǎn)可以提前結(jié)束BFS首次訪問即是最短 if (x end.x y end.y) { return dist[x][y]; } // 1. 處理傳送門0權(quán)邊 if (isTele[x][y]) { Point nxt teleport[x][y]; if (dist[nxt.x][nxt.y] dist[x][y]) { dist[nxt.x][nxt.y] dist[x][y]; dq.push_front(nxt); // 0權(quán)邊放前端 } } // 2. 處理普通移動(dòng)1權(quán)邊 for (int i 0; i 4; i) { int nx x dx[i], ny y dy[i]; if (nx 0 nx n ny 0 ny m grid[nx][ny] ! ‘#’) { if (dist[nx][ny] dist[x][y] 1) { dist[nx][ny] dist[x][y] 1; dq.push_back(nxt); // 1權(quán)邊放后端 } } } } return -1; // 無法到達(dá) }注意事項(xiàng)0-1 BFS中為什么0權(quán)邊放隊(duì)首1權(quán)邊放隊(duì)尾這保證了隊(duì)列前端到后端的距離值是“非遞減”的類似于優(yōu)先隊(duì)列但用deque實(shí)現(xiàn)常數(shù)更小。這是解決邊權(quán)僅為兩種值的最短路問題的經(jīng)典技巧。3.3 壓軸題動(dòng)態(tài)規(guī)劃與狀態(tài)壓縮題目大意有N個(gè)任務(wù)每個(gè)任務(wù)有開始時(shí)間、結(jié)束時(shí)間和價(jià)值。同時(shí)有M種資源每種資源在同一時(shí)間只能用于一個(gè)任務(wù)。一個(gè)任務(wù)需要占用一種特定的資源才能完成。求能獲得的最大總價(jià)值。思路拆解初步分析這是帶資源約束的區(qū)間調(diào)度問題是經(jīng)典“加權(quán)區(qū)間調(diào)度”的擴(kuò)展。如果沒有資源限制M1我們可以按結(jié)束時(shí)間排序后使用動(dòng)態(tài)規(guī)劃dp[i] max(dp[i-1], value[i] dp[p[i]])其中p[i]是在任務(wù)i開始之前結(jié)束的最后一個(gè)任務(wù)下標(biāo)。引入資源維度現(xiàn)在有M種資源相當(dāng)于有M條獨(dú)立的“時(shí)間線”。一個(gè)核心的貪心策略是對于同一種資源其上的任務(wù)選擇依然符合無資源沖突時(shí)的最優(yōu)子結(jié)構(gòu)。因此我們可以考慮狀態(tài)壓縮DP。狀態(tài)設(shè)計(jì)設(shè)dp[i][mask]表示考慮前i個(gè)任務(wù)按結(jié)束時(shí)間排序后當(dāng)前M種資源的使用狀態(tài)為mask一個(gè)M位的二進(jìn)制數(shù)第k位為1表示第k種資源正在被占用時(shí)能獲得的最大價(jià)值。但這樣狀態(tài)數(shù)是N * 2^M如果M較大比如10會(huì)超時(shí)。優(yōu)化思路注意到任務(wù)數(shù)是N可能很大但資源種類M通常較小本題可能M10。我們換一種狀態(tài)定義dp[mask]表示達(dá)到某種資源占用狀態(tài)mask時(shí)能獲得的最大價(jià)值。我們按時(shí)間順序處理事件任務(wù)開始或結(jié)束。將每個(gè)任務(wù)拆分為兩個(gè)事件開始事件價(jià)值需占用資源和結(jié)束事件-價(jià)值釋放資源。將所有事件按時(shí)間排序時(shí)間相同時(shí)處理結(jié)束事件優(yōu)先于開始事件釋放資源后才能被再利用。遍歷事件如果是結(jié)束事件dp[mask] max(dp[mask], dp[mask_with_resource_k])其中mask_with_resource_k是包含了該任務(wù)所占資源的那個(gè)狀態(tài)。這表示該任務(wù)完成狀態(tài)轉(zhuǎn)移時(shí)不增加價(jià)值只是釋放了資源。如果是開始事件假設(shè)任務(wù)需要資源r其價(jià)值為v。對于所有當(dāng)前mask中資源r未被占用的狀態(tài)嘗試開始這個(gè)任務(wù)new_mask mask | (1r)dp[new_mask] max(dp[new_mask], dp[mask] v)。最終答案所有dp[mask]中的最大值。關(guān)鍵點(diǎn)與實(shí)現(xiàn)技巧事件排序確保結(jié)束事件先于開始事件防止一個(gè)任務(wù)剛結(jié)束釋放的資源被同一個(gè)時(shí)間點(diǎn)開始的另一個(gè)任務(wù)錯(cuò)誤占用。狀態(tài)初始化dp[0] 0其他狀態(tài)為負(fù)無窮。復(fù)雜度事件數(shù)O(N)狀態(tài)數(shù)O(2^M)總復(fù)雜度O(N * 2^M)在M10時(shí)可行。實(shí)操心得對于“時(shí)間”“資源”的調(diào)度問題事件驅(qū)動(dòng)掃描線配合狀態(tài)壓縮DP是一個(gè)強(qiáng)有力的框架。難點(diǎn)在于正確設(shè)計(jì)事件類型和狀態(tài)轉(zhuǎn)移順序。在紙上畫出幾個(gè)任務(wù)的時(shí)間線模擬事件處理過程對厘清邏輯非常有幫助。4. 常見失誤點(diǎn)與賽場調(diào)試策略即使思路正確實(shí)現(xiàn)上的一點(diǎn)點(diǎn)疏忽也可能導(dǎo)致丟分。下面是我總結(jié)的幾條高頻“翻車點(diǎn)”和應(yīng)對策略。4.1 數(shù)據(jù)范圍與溢出問題這是C/C選手永恒的痛。國賽題目一定會(huì)卡數(shù)據(jù)范圍。整數(shù)溢出場景兩個(gè)int型變量a, b例如a1e9, b1e9相乘結(jié)果可能超過int范圍約2.1e9即使你打算存入long long但在計(jì)算a*b時(shí)表達(dá)式類型仍是int已經(jīng)溢出。解決在表達(dá)式前強(qiáng)制轉(zhuǎn)換。long long result (long long)a * b;。檢查清單遇到累加、累乘、計(jì)算組合數(shù)C(n,m)、距離平方等操作第一時(shí)間思考是否需要long long。數(shù)組越界場景開數(shù)組int arr[N]但訪問了arr[N]?；蛘逥FS/BFS中新坐標(biāo)未判斷是否在網(wǎng)格內(nèi)就進(jìn)行訪問。解決養(yǎng)成防御性編程習(xí)慣。定義數(shù)組時(shí)稍微開大一點(diǎn)如N5。在訪問數(shù)組前務(wù)必進(jìn)行下標(biāo)有效性檢查。無窮大的設(shè)置不要用0x7fffffff因?yàn)樗右粋€(gè)正數(shù)會(huì)溢出變成負(fù)數(shù)。推薦使用0x3f3f3f3f這個(gè)數(shù)約等于1e9且其兩倍仍在int范圍內(nèi)用memset(arr, 0x3f, sizeof(arr))可以方便地將int數(shù)組初始化為這個(gè)值。4.2 輸入輸出與格式錯(cuò)誤多組輸入題目說“包含多組測試數(shù)據(jù)”但你的代碼只讀了一組。務(wù)必使用while(cin n n ! 0)或while(scanf(“%d”, n) ! EOF)這類循環(huán)。輸出格式最后一行是否需要換行數(shù)字之間用空格還是換行分隔務(wù)必嚴(yán)格按照題目要求輸出。一個(gè)常見的技巧是第一個(gè)元素正常輸出后續(xù)元素先輸出分隔符再輸出元素如cout ans[0]; for(int i1; in; i) cout “ “ ans[i];。浮點(diǎn)數(shù)精度盡量避免直接比較浮點(diǎn)數(shù)相等a b。應(yīng)使用fabs(a-b) 1e-9這樣的方式。輸出時(shí)若要求保留小數(shù)使用printf(“%.2f\n”, value);不要用cout的setprecision容易忘掉fixed。4.3 算法選擇與復(fù)雜度誤判暴力搜索剪枝以為DFS暴力能過結(jié)果數(shù)據(jù)量大導(dǎo)致超時(shí)。在實(shí)現(xiàn)前務(wù)必估算最壞情況下的時(shí)間復(fù)雜度。例如N20子集枚舉是2^20≈1e6可接受N302^30≈1e9基本會(huì)超時(shí)。容器選擇不當(dāng)在需要頻繁按值查找如判斷一個(gè)數(shù)是否在集合中時(shí)使用vector遍歷查找是O(N)而使用unordered_set是平均O(1)。在需要有序數(shù)據(jù)時(shí)使用set。4.4 調(diào)試策略當(dāng)程序WA答案錯(cuò)誤時(shí)先讀題再讀題確保完全理解題意包括輸入輸出格式、數(shù)據(jù)范圍、特殊規(guī)定如多組數(shù)據(jù)、文件尾結(jié)束。WA的一半原因在于誤解題意。構(gòu)造小數(shù)據(jù)不要依賴OJ給的樣例。自己手寫幾個(gè)小的、邊界的數(shù)據(jù)測試。比如N0或1的情況數(shù)組全部元素相同的情況負(fù)數(shù)的情況。輸出中間變量在懷疑的邏輯段前后輸出關(guān)鍵變量的值。對比你的計(jì)算過程和手算結(jié)果是否一致。對拍對于難題如果你有一個(gè)保證正確但效率低的暴力算法例如用于小數(shù)據(jù)范圍可以寫一個(gè)隨機(jī)數(shù)據(jù)生成器讓你的優(yōu)化算法和暴力算法跑同樣的數(shù)據(jù)對比輸出。這是找出深藏BUG的終極手段。5. 從備賽到實(shí)戰(zhàn)我的個(gè)人經(jīng)驗(yàn)體會(huì)最后拋開具體的題目我想分享幾點(diǎn)關(guān)于備賽和實(shí)戰(zhàn)的體會(huì)這些可能比解出某一道題更重要。關(guān)于學(xué)習(xí)路徑算法競賽的知識體系龐大但核心是數(shù)據(jù)結(jié)構(gòu)數(shù)組、鏈表、棧、隊(duì)列、樹、圖、并查集、堆和基礎(chǔ)算法排序、二分、遞歸、分治、貪心、動(dòng)態(tài)規(guī)劃、搜索、最短路、最小生成樹。不要一開始就死磕高難度的“模板”把《算法競賽入門經(jīng)典》劉汝佳這類基礎(chǔ)書上的例題和習(xí)題扎扎實(shí)實(shí)過一遍收獲遠(yuǎn)大于漫無目的地刷題。關(guān)于刷題質(zhì)量遠(yuǎn)大于數(shù)量。每做一道題尤其是做錯(cuò)的題一定要徹底弄懂。嘗試用多種方法解同一道題思考時(shí)間與空間復(fù)雜度的權(quán)衡。建立自己的“解題本”或博客記錄經(jīng)典題目的思路、易錯(cuò)點(diǎn)和代碼模板。藍(lán)橋杯歷屆真題是非常好的素材它的題目風(fēng)格相對穩(wěn)定。關(guān)于比賽心態(tài)4個(gè)小時(shí)的比賽是腦力、體力和心態(tài)的綜合較量。開局不順很正常不要糾結(jié)于一題。按照“先易后難”的順序確保簡單題不丟分。如果一道題卡了30分鐘以上還沒有清晰思路果斷標(biāo)記后跳過去看下一題。很多時(shí)候解決后面的題目會(huì)給你帶來新的靈感。最后一定要留出至少20分鐘檢查文件名、輸入輸出、數(shù)組大小、long long、多組數(shù)據(jù)等。關(guān)于工具熟練度你平時(shí)用什么環(huán)境寫代碼比賽就用什么。不要在比賽當(dāng)天嘗試新IDE或編輯器。將常用的代碼模板快速冪、并查集、Dijkstra等提前準(zhǔn)備好放在一個(gè)單獨(dú)的文件里比賽時(shí)快速復(fù)制粘貼能節(jié)省大量時(shí)間并避免手誤。國賽只是一個(gè)節(jié)點(diǎn)無論結(jié)果如何在這個(gè)過程中對問題分析能力、編碼能力和抗壓能力的鍛煉才是真正寶貴的財(cái)富。保持熱愛持續(xù)思考下一次你會(huì)做得更好。