1. 項(xiàng)目概述一次國(guó)賽的深度復(fù)盤與實(shí)戰(zhàn)拆解“藍(lán)橋杯”國(guó)賽對(duì)于每一個(gè)學(xué)習(xí)C/C的在校生和算法愛好者來說都是一個(gè)極具分量的里程碑。它不像普通的課程作業(yè)也不像一些商業(yè)項(xiàng)目它的核心價(jià)值在于在極端有限的時(shí)空約束下對(duì)選手的基礎(chǔ)知識(shí)、算法思維、代碼實(shí)現(xiàn)和心態(tài)穩(wěn)定性的綜合極限壓榨。2021年第十二屆國(guó)賽B組的題目恰好是這種特質(zhì)的典型代表。它沒有炫酷的新框架也不追求業(yè)務(wù)邏輯的復(fù)雜而是直指計(jì)算機(jī)科學(xué)的核心如何用高效的算法和嚴(yán)謹(jǐn)?shù)拇a去解決一個(gè)個(gè)精妙設(shè)計(jì)的數(shù)學(xué)與邏輯問題。這篇文章是我對(duì)那場(chǎng)賽事的一次深度復(fù)盤。我不會(huì)僅僅羅列題目和答案那樣意義不大。我更想做的是帶你回到那個(gè)比賽的現(xiàn)場(chǎng)以一名參賽者的視角去拆解每一道題背后的出題意圖、思維陷阱、編碼細(xì)節(jié)以及臨場(chǎng)策略。你會(huì)發(fā)現(xiàn)很多題目看似簡(jiǎn)單實(shí)則暗藏玄機(jī)有些題暴力搜索似乎可行但數(shù)據(jù)規(guī)模會(huì)瞬間讓你超時(shí)更有些題需要你將書本上離散的知識(shí)點(diǎn)在高壓下進(jìn)行創(chuàng)造性的組合與運(yùn)用。無論你是正在備賽的選手希望從過往真題中汲取經(jīng)驗(yàn)還是算法愛好者想挑戰(zhàn)一下自己的思維亦或是C/C開發(fā)者想看看在純粹的算法領(lǐng)域代碼能寫到多精煉這篇文章都將為你提供一個(gè)完整的、可操作的參考框架。我們將從整體賽題風(fēng)格分析入手深入到具體題目的解題心路歷程最后總結(jié)出國(guó)賽級(jí)別的備賽與實(shí)戰(zhàn)方略。2. 賽題整體風(fēng)格與核心考點(diǎn)解析回顧2021年國(guó)賽B組其風(fēng)格延續(xù)了藍(lán)橋杯近年來的趨勢(shì)“重思維、重基礎(chǔ)、輕模板”。所謂“輕模板”并不是說完全用不到經(jīng)典算法而是指單純背會(huì)了Dijkstra、動(dòng)態(tài)規(guī)劃的轉(zhuǎn)移方程并不足以解決問題你必須深刻理解其本質(zhì)并具備根據(jù)具體問題靈活變形和適配的能力。2.1 考察能力維度分析這場(chǎng)比賽的題目主要從以下幾個(gè)維度對(duì)選手進(jìn)行考察基礎(chǔ)語法與API熟悉度這是底線。包括標(biāo)準(zhǔn)輸入輸出、STL容器vector,map,set,queue等的熟練使用、字符串處理、精度控制等。任何在這里卡殼都是致命的。數(shù)學(xué)建模與抽象能力能否將一段冗長(zhǎng)的文字描述迅速抽象成數(shù)學(xué)模型或數(shù)據(jù)結(jié)構(gòu)。這是解題的第一步也是最關(guān)鍵的一步。很多題目描述得像一個(gè)故事但其內(nèi)核可能就是一個(gè)圖論問題或一個(gè)數(shù)論問題。算法設(shè)計(jì)與復(fù)雜度分析這是區(qū)分度的核心。給定一個(gè)問題你能設(shè)計(jì)出時(shí)間復(fù)雜度在允許范圍內(nèi)的算法嗎你需要瞬間判斷暴力法O(n2), O(2^n)是否會(huì)超時(shí)是否需要用到二分、動(dòng)態(tài)規(guī)劃、搜索剪枝等更優(yōu)的算法。邊界條件與細(xì)節(jié)處理國(guó)賽的測(cè)試數(shù)據(jù)往往非?！敖苹?。最大值、最小值、初始狀態(tài)、溢出問題、浮點(diǎn)數(shù)比較、多解情況等都會(huì)設(shè)置專門的測(cè)試點(diǎn)。代碼的魯棒性在這里至關(guān)重要。調(diào)試與心態(tài)管理在封閉環(huán)境下沒有網(wǎng)絡(luò)沒有智能提示如何快速定位一個(gè)邏輯錯(cuò)誤當(dāng)一道題卡住超過預(yù)期時(shí)間時(shí)是繼續(xù)攻堅(jiān)還是果斷跳過這考驗(yàn)的是實(shí)戰(zhàn)經(jīng)驗(yàn)和心理素質(zhì)。2.2 題目難度分布與時(shí)間策略通常國(guó)賽B組會(huì)有5-6道填空題和5-6道編程大題。填空題往往考察奇思妙想或精確計(jì)算編程題則難度梯度明顯。前1-2道編程題屬于“簽到題”旨在穩(wěn)定軍心。通?？疾炷M、簡(jiǎn)單計(jì)算或基礎(chǔ)排序。目標(biāo)15分鐘內(nèi)必須拿下保證基礎(chǔ)分。中間2-3道題是爭(zhēng)奪獎(jiǎng)牌的關(guān)鍵。涉及經(jīng)典算法的直接或變形應(yīng)用如貪心、DFS/BFS、簡(jiǎn)單DP、二分答案等。目標(biāo)每道題分配30-45分鐘力求思路清晰一次寫對(duì)。最后1-2道題是區(qū)分一等獎(jiǎng)和頂尖高手的“壓軸題”?？赡苌婕皬?fù)雜的動(dòng)態(tài)規(guī)劃狀態(tài)壓縮DP、樹形DP、圖論高級(jí)算法網(wǎng)絡(luò)流、最小生成樹變形、或者需要極強(qiáng)數(shù)學(xué)推導(dǎo)的題目。策略根據(jù)剩余時(shí)間優(yōu)先保證前面題目的正確性最后有時(shí)間再嘗試壓軸題哪怕只能通過部分?jǐn)?shù)據(jù)藍(lán)橋杯按測(cè)試點(diǎn)給分也是勝利。臨場(chǎng)心得我的習(xí)慣是開賽后先用5分鐘快速通覽所有題目對(duì)難度和類型有個(gè)大致判斷。然后嚴(yán)格按“先易后難”的順序做。千萬不要在某一題上鉆牛角尖超過1小時(shí)即使感覺差一點(diǎn)就能出來。先拿到所有能穩(wěn)拿的分再回頭攻堅(jiān)心態(tài)會(huì)完全不一樣。3. 核心真題詳解與思維路徑還原由于真題版權(quán)原因我無法直接粘貼原題但我會(huì)選取當(dāng)年最具代表性的幾類題型還原我的解題思考過程并給出核心代碼框架。你可以將這些思路視為解題的“通用武器”。3.1 類型一大數(shù)運(yùn)算與高精度處理這類問題往往看起來是簡(jiǎn)單的算術(shù)題但給出的數(shù)字范圍遠(yuǎn)超long long(C) 或int64_t的表示范圍。例如計(jì)算2的1000次方或者兩個(gè)幾百位整數(shù)的乘法。思維路徑識(shí)別題目輸入或輸出的數(shù)字位數(shù)極大例如提到“結(jié)果可能非常大”。決策放棄使用任何內(nèi)置整數(shù)類型立即確定使用高精度算法。實(shí)現(xiàn)用字符串或整型數(shù)組來模擬豎式計(jì)算。存儲(chǔ)倒序存儲(chǔ)在數(shù)組里更方便計(jì)算下標(biāo)0存?zhèn)€位。加法/減法模擬手工計(jì)算處理進(jìn)位和借位。乘法模擬“乘數(shù)每一位乘以被乘數(shù)再累加”的過程。除法相對(duì)復(fù)雜但國(guó)賽B組一般較少涉及高精度除高精度。核心代碼框架高精度加法為例#include iostream #include string #include algorithm #include vector using namespace std; vectorint add(vectorint A, vectorint B) { vectorint C; int t 0; // 進(jìn)位 for (int i 0; i A.size() || i B.size(); i) { if (i A.size()) t A[i]; if (i B.size()) t B[i]; C.push_back(t % 10); t / 10; } if (t) C.push_back(1); // 處理最高位進(jìn)位 return C; } int main() { string a, b; cin a b; vectorint A, B; // 倒序存入 for (int i a.size() - 1; i 0; i--) A.push_back(a[i] - 0); for (int i b.size() - 1; i 0; i--) B.push_back(b[i] - 0); auto C add(A, B); for (int i C.size() - 1; i 0; i--) cout C[i]; return 0; }避坑指南前導(dǎo)零計(jì)算過程中可能會(huì)產(chǎn)生前導(dǎo)零輸出前需要處理。例如000123應(yīng)輸出123。負(fù)數(shù)如果涉及負(fù)數(shù)需要先判斷符號(hào)轉(zhuǎn)化為大數(shù)絕對(duì)值之間的加/減法最后再處理符號(hào)。復(fù)雜度高精度乘法的復(fù)雜度是O(n2)當(dāng)位數(shù)極大如10^5位時(shí)可能超時(shí)此時(shí)需考慮更快的FFT快速傅里葉變換算法但國(guó)賽B組通常不會(huì)卡這個(gè)。3.2 類型二動(dòng)態(tài)規(guī)劃DP的經(jīng)典與變形DP是國(guó)賽的絕對(duì)主力。2021年的題目中必然有至少一道中等以上難度的DP題。關(guān)鍵不在于背模板而在于定義狀態(tài)和推導(dǎo)狀態(tài)轉(zhuǎn)移方程。通用思維路徑狀態(tài)定義問自己“我們需要記錄什么信息才能將原問題分解成子問題”通常形式是dp[i][j]表示考慮前i個(gè)元素且在某種限制j下的最優(yōu)解或方案數(shù)。狀態(tài)轉(zhuǎn)移思考如何從已知的、規(guī)模更小的狀態(tài)推導(dǎo)出當(dāng)前狀態(tài)。這是最核心的一步需要嚴(yán)謹(jǐn)?shù)倪壿嫛３跏蓟钚∽訂栴}的解是什么通常dp[0][...]或dp[...][0]需要仔細(xì)設(shè)定。結(jié)果輸出最終答案對(duì)應(yīng)哪個(gè)狀態(tài)是dp[n][m]還是max(dp[n][...])例題還原背包問題變形 假設(shè)有一道題有N種物品每種物品有重量w、價(jià)值v和數(shù)量ss可能很大背包容量為M。求最大價(jià)值。 這不是簡(jiǎn)單的01背包或完全背包而是多重背包。解題步驟識(shí)別物品有數(shù)量限制既非唯一也非無限。樸素思路將每種物品的s個(gè)看成s個(gè)獨(dú)立物品轉(zhuǎn)化為01背包。復(fù)雜度O(M * Σs)如果s很大如1000Σs可能達(dá)到10^9必然超時(shí)。優(yōu)化二進(jìn)制拆分這是必須掌握的技巧。將數(shù)量s拆分成1, 2, 4, ..., 2^k, c其中c s - (2^{k1}-1)這樣幾個(gè)“物品包”。這樣用這些“包”的組合可以表示出0到s之間的任意數(shù)量同時(shí)將物品數(shù)量從s個(gè)減少到log(s)個(gè)。轉(zhuǎn)化將這些“包”作為新的物品每個(gè)包的重量數(shù)量單重價(jià)值數(shù)量單價(jià)然后對(duì)它們做01背包。復(fù)雜度降至O(M * Σlog(s))。核心代碼片段二進(jìn)制拆分部分struct Good { int w, v; // 包的重量和價(jià)值 }; vectorGood goods; // 對(duì)于第i種物品重量為w價(jià)值為v數(shù)量為s int k 1; while (k s) { goods.push_back({w * k, v * k}); s - k; k * 2; } if (s 0) { goods.push_back({w * s, v * s}); } // 然后對(duì)goods這個(gè)vector做標(biāo)準(zhǔn)的01背包DP vectorint dp(M 1, 0); for (auto good : goods) { for (int j M; j good.w; j--) { dp[j] max(dp[j], dp[j - good.w] good.v); } } cout dp[M] endl;DP心得在紙上畫表格定義好dp[i][j]后在紙上畫一個(gè)矩陣手動(dòng)推導(dǎo)前幾行是檢驗(yàn)狀態(tài)轉(zhuǎn)移方程正確性最有效的方法遠(yuǎn)比在腦子里空想靠譜。3.3 類型三搜索與剪枝當(dāng)問題看起來需要枚舉所有可能情況但數(shù)據(jù)規(guī)模又排除了純暴力時(shí)搜索DFS/BFS配合剪枝就是利器。常見于路徑查找、排列組合、棋盤類問題。思維路徑判斷是否可搜索狀態(tài)空間是否在可接受范圍內(nèi)雖然可能很大但通過剪枝能極大縮減。設(shè)計(jì)狀態(tài)表示用什么數(shù)據(jù)表示一個(gè)“節(jié)點(diǎn)”或一個(gè)“局面”如何標(biāo)記已訪問狀態(tài)以防重復(fù)設(shè)計(jì)剪枝策略這是搜索題的靈魂。常見剪枝有可行性剪枝當(dāng)前狀態(tài)已經(jīng)不可能達(dá)到目標(biāo)直接返回。最優(yōu)性剪枝當(dāng)前路徑的代價(jià)已經(jīng)超過已知最優(yōu)解直接返回。記憶化如果搜索過程中會(huì)重復(fù)到達(dá)同一狀態(tài)用哈希表如unordered_map存儲(chǔ)該狀態(tài)下的最優(yōu)結(jié)果下次直接使用。順序剪枝調(diào)整搜索順序優(yōu)先嘗試可能性大的分支能更快找到較優(yōu)解從而加強(qiáng)最優(yōu)性剪枝的效果。例題還原典型DFS回溯 N皇后問題變種在N×N的棋盤上放置N個(gè)棋子有部分格子禁止放置求方案數(shù)。解題框架#include iostream #include vector using namespace std; int n, ans 0; vectorstring board; // 棋盤#表示禁止.表示可放置 vectorbool col, dg, udg; // 列主對(duì)角線副對(duì)角線是否被占用 void dfs(int row) { if (row n) { // 找到一個(gè)合法方案 ans; return; } for (int i 0; i n; i) { // 嘗試在當(dāng)前行的每一列放置 if (board[row][i] # || col[i] || dg[row - i n] || udg[row i]) { continue; // 剪枝位置禁止、或列、對(duì)角線沖突 } // 放置棋子 col[i] dg[row - i n] udg[row i] true; dfs(row 1); // 搜索下一行 // 回溯撤銷放置 col[i] dg[row - i n] udg[row i] false; } } int main() { cin n; board.resize(n); col.resize(n, false); dg.resize(2 * n, false); // 對(duì)角線數(shù)量為2*n-1這里開2*n安全 udg.resize(2 * n, false); for (int i 0; i n; i) cin board[i]; dfs(0); cout ans endl; return 0; }搜索優(yōu)化心得對(duì)于DFS遞歸函數(shù)的參數(shù)設(shè)計(jì)非常重要。盡量傳遞基本類型或引用避免在遞歸層間拷貝大對(duì)象如整個(gè)棋盤狀態(tài)。像上面這樣用幾個(gè)全局的布爾數(shù)組來記錄沖突是效率很高的做法。4. 環(huán)境準(zhǔn)備與編碼實(shí)戰(zhàn)要點(diǎn)國(guó)賽環(huán)境通常是Windows系統(tǒng)提供Dev-C、Code::Blocks或Visual Studio等IDE。但你不能依賴IDE的智能提示和自動(dòng)補(bǔ)全。4.1 必備的頭文件與模板比賽開始前第一件事就是在編輯器里敲下一個(gè)“萬能頭文件”和你的代碼框架。這能節(jié)省大量時(shí)間并避免忘記包含必要庫(kù)的尷尬。#include bits/stdc.h // 萬能頭文件包含絕大多數(shù)STL using namespace std; typedef long long ll; // 將long long定義為ll打字更方便 const int INF 0x3f3f3f3f; // 定義一個(gè)“無窮大”常量常用于初始化 const int N 1e5 10; // 根據(jù)題目數(shù)據(jù)范圍預(yù)估的最大數(shù)組大小 int main() { ios::sync_with_stdio(false); cin.tie(0); // 這兩行用于關(guān)閉C和C的輸入輸出流同步加快cin/cout速度 // 你的代碼邏輯 return 0; }重要提示使用ios::sync_with_stdio(false);后嚴(yán)禁將cin/cout與scanf/printf混用否則會(huì)導(dǎo)致輸入輸出順序錯(cuò)亂。4.2 輸入輸出處理技巧藍(lán)橋杯的輸入輸出格式有時(shí)比較“詭異”需要仔細(xì)處理。不確定行數(shù)的輸入使用while (cin a b)或while (getline(cin, str))來讀取直到文件結(jié)束。帶空格的字符串使用getline(cin, str)。注意如果前面用了cin xcin會(huì)留下一個(gè)換行符需要先用cin.ignore()忽略掉再使用getline。超大輸入輸出如果確信使用cin/cout且已經(jīng)加速仍感覺卡輸入輸出可以嘗試用scanf/printf。對(duì)于純數(shù)字scanf/printf通常更快。浮點(diǎn)數(shù)輸出使用fixed setprecision(n)來控制小數(shù)點(diǎn)后位數(shù)。例如cout fixed setprecision(2) area endl;4.3 調(diào)試與驗(yàn)證策略沒有在線評(píng)測(cè)的實(shí)時(shí)反饋你需要自己設(shè)計(jì)測(cè)試用例。小數(shù)據(jù)驗(yàn)證邏輯寫完代碼后先用題目給的樣例測(cè)試。然后自己構(gòu)造幾個(gè)邊界情況的小數(shù)據(jù)比如n0 n1 數(shù)組全為0 遞增/遞減序列等。打印中間變量在懷疑出錯(cuò)的代碼段前后插入cout語句輸出關(guān)鍵變量的值。這是最原始也是最有效的調(diào)試方法。對(duì)拍如果時(shí)間允許對(duì)于一道題你可以寫一個(gè)絕對(duì)正確但可能很慢的暴力算法例如用于填空題的枚舉。用你的高效算法和暴力算法隨機(jī)生成大量小規(guī)模數(shù)據(jù)比較兩者的輸出是否一致。這是發(fā)現(xiàn)算法邏輯錯(cuò)誤的大殺器。5. 常見“坑點(diǎn)”與臨場(chǎng)故障排除根據(jù)多年經(jīng)驗(yàn)和賽后交流以下這些“坑”幾乎每屆比賽都有人踩。5.1 數(shù)據(jù)范圍與溢出這是最常見的錯(cuò)誤沒有之一。整數(shù)溢出兩個(gè)int相乘即使結(jié)果用long long接收在乘法計(jì)算時(shí)就已經(jīng)溢出了。解決方案將乘數(shù)之一強(qiáng)制轉(zhuǎn)換為long long。例如long long result (long long)a * b;數(shù)組越界聲明數(shù)組時(shí)大小是否足夠N是否應(yīng)該是N5更安全DFS/BFS中訪問數(shù)組前是否檢查了下標(biāo)浮點(diǎn)數(shù)誤差判斷兩個(gè)浮點(diǎn)數(shù)a和b是否相等不要用a b應(yīng)該用fabs(a - b) 1e-8或一個(gè)極小的精度值。在涉及浮點(diǎn)數(shù)二分時(shí)尤其要注意。5.2 多組輸入與初始化很多題目沒說只有一組數(shù)據(jù)。如果你的程序邏輯只處理一組數(shù)據(jù)提交后可能會(huì)WAWrong Answer。解決方案養(yǎng)成好習(xí)慣除非題目明確說明只有單組數(shù)據(jù)否則都按多組輸入來寫。這意味著在while (cin n n ! 0)這樣的循環(huán)里每次循環(huán)必須重新初始化所有全局變量和數(shù)組很多人在這里犯錯(cuò)上一組數(shù)據(jù)的結(jié)果污染了下一組。5.3 遞歸深度與棧溢出DFS遞歸如果層數(shù)過深例如超過1萬層可能會(huì)導(dǎo)致棧溢出程序異常終止。解決方案在C中可以在main函數(shù)開頭用#pragma comment(linker, /STACK:1024000000,1024000000)來手動(dòng)擴(kuò)大?？臻g環(huán)境允許的話。考慮改用棧模擬遞歸迭代DFS或者用BFS。檢查剪枝是否充分是否避免了不必要的深層遞歸。5.4 時(shí)間復(fù)雜度誤判你以為你的算法是O(n log n)實(shí)際上是O(n2)。在比賽壓力下很容易誤判。排查方法在心里模擬最大規(guī)模數(shù)據(jù)。如果n10^5一個(gè)O(n2)的雙重循環(huán)就是10^10次操作遠(yuǎn)超1秒約10^8次操作的限制。看到這種規(guī)模必須想O(n log n)或O(n)的算法。5.5 提交前的終極檢查清單在點(diǎn)擊提交按鈕前花2分鐘做一次快速檢查[ ] 文件名和函數(shù)名是否正確藍(lán)橋杯要求main函數(shù)[ ] 所有調(diào)試用的cout語句是否都已注釋或刪除[ ] 數(shù)組大小是否開夠通常開到題目給的最大范圍10[ ] 多組數(shù)據(jù)初始化了嗎[ ]long long用對(duì)了嗎乘法溢出了嗎[ ] 浮點(diǎn)數(shù)精度處理了嗎[ ] 邊界情況n0 空字符串等考慮了嗎6. 備賽建議與長(zhǎng)期能力提升國(guó)賽不是靠賽前突擊就能取得好成績(jī)的它是對(duì)你長(zhǎng)期積累的一次檢驗(yàn)。短期備賽1-3個(gè)月刷真題這是最有效的途徑。把近5-10屆的省賽、國(guó)賽真題全部做一遍。不是看完題解就算了而是要自己獨(dú)立實(shí)現(xiàn)并思考有沒有更優(yōu)解。專題突破針對(duì)自己的薄弱環(huán)節(jié)比如動(dòng)態(tài)規(guī)劃、圖論進(jìn)行集中訓(xùn)練?？梢栽诼骞?、AcWing等OJ上找相應(yīng)專題的題目練習(xí)。模擬賽每周進(jìn)行1-2次全真模擬嚴(yán)格計(jì)時(shí)4小時(shí)營(yíng)造比賽氛圍。賽后認(rèn)真復(fù)盤總結(jié)時(shí)間分配和失誤原因。長(zhǎng)期能力建設(shè)夯實(shí)基礎(chǔ)《算法導(dǎo)論》或《算法競(jìng)賽入門經(jīng)典》劉汝佳是很好的教材。徹底理解基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)棧、隊(duì)列、鏈表、樹、圖和經(jīng)典算法排序、查找、遞歸、分治。構(gòu)建知識(shí)體系將算法分類整理形成自己的知識(shí)腦圖。比如動(dòng)態(tài)規(guī)劃可以細(xì)分為線性DP、區(qū)間DP、樹形DP、狀態(tài)壓縮DP、數(shù)位DP等每個(gè)類別積累幾道典型例題。代碼能力堅(jiān)持用C/C手寫代碼減少對(duì)IDE自動(dòng)補(bǔ)全的依賴。提高一次寫對(duì)的準(zhǔn)確率。數(shù)學(xué)基礎(chǔ)組合數(shù)學(xué)、數(shù)論、計(jì)算幾何中的一些基本概念如快速冪、模運(yùn)算、素?cái)?shù)篩、容斥原理在藍(lán)橋杯中時(shí)有出現(xiàn)需要適當(dāng)了解。最后比賽心態(tài)至關(guān)重要。國(guó)賽現(xiàn)場(chǎng)周圍鍵盤聲此起彼伏很容易讓人心慌。記住你的對(duì)手不是別人是那道題和過去的自己。把注意力完全集中在自己的屏幕和思路上按照既定的策略穩(wěn)步推進(jìn)。即使最后沒能解出所有題目把你掌握的部分做到極致不留低級(jí)錯(cuò)誤就已經(jīng)超越了大多數(shù)人。編程競(jìng)賽的魅力不僅在于獎(jiǎng)牌更在于那種全心投入、抽絲剝繭、最終看到“Accept”的純粹快樂。祝你在未來的比賽中思路清晰代碼如飛取得理想的成績(jī)。