1. 項目概述一次對算法競賽真題的深度復盤最近整理硬盤翻到了幾年前參加藍橋杯全國軟件和信息技術專業(yè)人才大賽國賽時的一些代碼和筆記。標題里的“2020藍橋國賽 c B(部分)”指的就是那一年C大學B組的部分真題。雖然比賽過去已久但重新審視這些題目依然能感受到當時賽場的緊張和解題時的思維碰撞。對于正在備賽的選手或是希望提升自己算法與編程能力的開發(fā)者來說歷屆真題無疑是最寶貴的“礦藏”。它們不僅檢驗知識掌握程度更能訓練在有限時間和壓力下分析問題、設計算法、編寫穩(wěn)健代碼的綜合能力。今天我就以一名“過來人”的身份和大家一起拆解2020年這場比賽中幾道具有代表性的C B組題目。我不會僅僅給出答案那樣意義不大。我會重點分享解題時的完整思考路徑題目到底在考察什么有哪些可能的“坑”從暴力枚舉到優(yōu)化解法的躍遷關鍵點在哪里以及在競賽環(huán)境下如何平衡代碼的正確性、效率和可調試性。無論你是正在備賽的學生還是對算法感興趣的同行希望這篇深度復盤能給你帶來一些實實在在的啟發(fā)和收獲。2. 解題環(huán)境與核心思路解析2.1 競賽環(huán)境與工具鏈復盤當年的藍橋杯比賽環(huán)境是標準的Windows PC預裝了Dev-C、Code::Blocks等IDE。對于C選手一個穩(wěn)定、熟悉的開發(fā)環(huán)境至關重要。我個人的習慣是使用Code::Blocks并將其編譯器設置為支持C11標準。這一點很重要因為像auto關鍵字、基于范圍的for循環(huán)、to_string()等C11特性能在不犧牲可讀性的前提下極大提升編碼速度。在比賽開始前務必花幾分鐘確認編譯選項關閉一些過于嚴格的警告避免干擾并測試一個簡單的輸入輸出程序確保環(huán)境一切正常。注意藍橋杯的評測系統(tǒng)通常使用GCC編譯器且對C標準的支持可能滯后于最新版本。穩(wěn)妥起見應避免使用比賽環(huán)境可能不支持的C14/17/20特性。以C11為核心輔以部分廣泛支持的C14特性如泛型lambda是相對安全的選擇。2.2 通用解題方法論五步拆題法面對一道競賽題切忌直接上手寫代碼。我總結了一個“五步拆題法”在高壓的競賽環(huán)境中能幫助保持清晰的思路精確理解題意至少讀題兩遍。第一遍通讀了解故事背景第二遍精讀用筆劃出所有輸入輸出格式、數(shù)據范圍、約束條件和特殊說明。一個常見的失分點就是誤解題意。抽象與建模剝離題目描述中的“故事外殼”將其轉化為一個清晰的數(shù)學模型或計算機問題。是圖論動態(tài)規(guī)劃搜索還是數(shù)學計算復雜度估算與算法選型根據題目給出的數(shù)據范圍N, M的最大值快速估算暴力解法如果存在的時間復雜度。例如N10可能允許階乘級復雜度N20可能允許指數(shù)級N1e5通常要求O(NlogN)或O(N)。這直接決定了你應該嘗試哪種算法。設計算法與邊界構思在草稿紙上畫出算法流程圖或寫出偽代碼。同時主動構思各種邊界情況和極端輸入如最小輸入、最大輸入、負數(shù)、零、重復元素等思考你的算法是否能正確處理。編碼與測試將設計好的算法轉化為代碼。先實現(xiàn)核心邏輯再補充輸入輸出。完成后立即用題目給的樣例、自己構思的邊界案例進行測試。這套方法的核心是“先想清楚再動手”能有效避免寫到一半發(fā)現(xiàn)思路錯誤而推倒重來的時間浪費。3. 代表性真題深度剖析與實現(xiàn)3.1 真題一平面分割動態(tài)規(guī)劃/數(shù)學組合問題題目回憶有n條直線和m個圓在平面上詢問這些圖形最多能把平面分割成多少個區(qū)域。直線和圓可以任意相交但任意兩個圓之間、以及直線和圓之間都最多只有兩個交點且沒有三線共點等情況。核心思路拆解 這是一道經典的“平面分割”問題考察的是遞推和組合數(shù)學思想。關鍵在于找到新增一個圖形時區(qū)域數(shù)量的增量規(guī)律。僅考慮直線眾所周知n條互不平行且無三線共點的直線最多能將平面分割成(n*(n1)/2) 1個區(qū)域。可以從遞推角度理解第k條直線最多能與前k-1條直線交出k-1個新交點這k-1個交點把這條直線分成k段每一段都會將其穿過的原有區(qū)域一分為二從而新增k個區(qū)域。因此區(qū)域總數(shù)f_line(n) f_line(n-1) n初始f_line(0)1解得f_line(n)1n*(n1)/2。引入圓問題變得復雜。我們需要考慮新增一個圓時它與已有直線和圓相交能產生多少新的交點這些交點又如何把圓分割成若干段弧每段弧穿過一個原有區(qū)域并將其分割。聯(lián)合遞推設dp[i][j]表示i條直線和j個圓最多能將平面分割的區(qū)域數(shù)。我們可以從dp[i-1][j]加一條直線和dp[i][j-1]加一個圓兩個方向遞推。加一條直線這條新增的直線最多會與已有的i-1條直線各交于一點共i-1點與已有的j個圓各交于兩點共2j點。所以最多產生(i-1 2j)個新交點。這些交點把這條直線分成了(i-12j 1) i2j段。每一段穿過一個舊區(qū)域并使其一分為二因此區(qū)域增量就是i2j。故有dp[i][j] dp[i-1][j] (i 2*j)。加一個圓這個新增的圓最多會與已有的i條直線各交于兩點共2i點與已有的j-1個圓各交于兩點共2(j-1)點。所以最多產生2i 2(j-1) 2i2j-2個新交點。這些交點把圓分成了(2i2j-2)段弧。每一段弧穿過一個舊區(qū)域并使其一分為二因此區(qū)域增量就是2i2j-2。故有dp[i][j] dp[i][j-1] (2*i 2*j - 2)。初始化dp[0][0] 1一個圖形都沒有整個平面就是一個區(qū)域。dp[i][0]就是僅直線的公式dp[0][j]可以類似推導僅圓分割平面公式為j*j - j 2。C實現(xiàn)與關鍵代碼#include iostream #include vector using namespace std; long long maxDivision(int n, int m) { // 使用vectorvectorlong long防止大數(shù)溢出 vectorvectorlong long dp(n 1, vectorlong long(m 1, 0)); dp[0][0] 1; // 初始化只有直線的情況 for (int i 1; i n; i) { dp[i][0] dp[i-1][0] i; } // 初始化只有圓的情況 for (int j 1; j m; j) { dp[0][j] dp[0][j-1] 2*j; // 或者直接用公式 j*j - j 2 } // 動態(tài)規(guī)劃遞推 for (int i 1; i n; i) { for (int j 1; j m; j) { // 兩種轉移方式取最大值符合“最多”分割的要求 long long fromLine dp[i-1][j] (i 2*j); long long fromCircle dp[i][j-1] (2*i 2*j - 2); dp[i][j] max(fromLine, fromCircle); } } return dp[n][m]; } int main() { int n, m; // 假設輸入為直線數(shù)n和圓數(shù)m // cin n m; // 示例n5, m3 n 5; m 3; cout maxDivision(n, m) endl; return 0; }避坑指南整數(shù)溢出當n和m較大時比如幾十區(qū)域數(shù)可能超過int范圍。務必使用long long類型。遞推方向理解一定要理解“新增圖形產生的交點分割該圖形進而增加區(qū)域”這一物理過程。死記公式在題目變形時容易出錯。“最多”的含義題目要求“最多”分割這意味著我們在放置直線和圓時必須讓它們盡可能多地相交。我們的遞推公式基于“最多交點數(shù)”的假設因此是合理的。3.2 真題二字符串編碼模擬與貪心題目回憶給定一個純數(shù)字字符串例如“123456”。編碼規(guī)則為將字符串分割成若干個子串每個子串可以解碼為一個字母A-Z對應1-26。問有多少種不同的分割編碼方式。例如“12”可以解碼為“AB”(1,2) 或者 “L”(12)。核心思路拆解 這是一個經典的解碼方法數(shù)問題與“爬樓梯”問題異曲同工通常使用動態(tài)規(guī)劃解決。狀態(tài)定義設dp[i]表示字符串前i個字符s[0...i-1]的解碼方法總數(shù)。狀態(tài)轉移考慮最后一個字符s[i-1]如果它單獨構成一個編碼‘1’到‘9’那么它可以從dp[i-1]的狀態(tài)轉移過來即dp[i] dp[i-1]。考慮最后兩個字符s[i-2]和s[i-1]如果它們能構成一個有效的兩位數(shù)編碼‘10’到‘26’那么可以從dp[i-2]的狀態(tài)轉移過來即dp[i] dp[i-2]。初始化dp[0] 1表示空字符串有一種解碼方式通常這樣初始化便于計算。dp[1]則需要看第一個字符是否為‘0’如果是‘0’則無法解碼為0否則為1。特殊字符‘0’的處理這是本題最大的坑點。‘0’不能單獨解碼它必須和前面的‘1’或‘2’結合成“10”或“20”才能被解碼。因此在轉移時需要特別判斷如果s[i-1] ‘0’那么它不能從dp[i-1]轉移不能單獨成碼。如果s[i-2] ‘1’ 或 ‘2’且s[i-1] ‘0’那么只能從dp[i-2]轉移必須合成“10”或“20”。如果s[i-2] ‘1’ 或 ‘2’且s[i-1]在‘1’到‘6’之間對于‘2’或‘1’到‘9’之間對于‘1’則可以從dp[i-1]和dp[i-2]兩個方向轉移。如果s[i-2]是其他數(shù)字且s[i-1]‘0’那么整個字符串無法解碼直接返回0。C實現(xiàn)與關鍵代碼#include iostream #include string #include vector using namespace std; int numDecodings(string s) { int n s.length(); if (n 0 || s[0] 0) return 0; // 空串或首字符為0無效 vectorint dp(n 1, 0); dp[0] 1; // 空串基礎情況 dp[1] 1; // 第一個字符非‘0’已判斷 for (int i 2; i n; i) { int oneDigit s[i-1] - 0; int twoDigits (s[i-2] - 0) * 10 (s[i-1] - 0); // 檢查一位數(shù)解碼 if (oneDigit 1 oneDigit 9) { dp[i] dp[i-1]; } // 檢查兩位數(shù)解碼 if (twoDigits 10 twoDigits 26) { dp[i] dp[i-2]; } // 如果dp[i]在兩次判斷后仍為0說明當前字符無法被解碼直接返回0 // 例如出現(xiàn)‘30’, ‘40’等 if (dp[i] 0) { return 0; } } return dp[n]; } int main() { string s 226; // 示例對應 “BZ”(2,26), “VF”(22,6), “BBF”(2,2,6) cout numDecodings(s) endl; // 輸出應為 3 return 0; }避坑指南‘0’是萬惡之源必須把所有涉及‘0’的情況考慮周全。上面的代碼通過判斷一位數(shù)和兩位數(shù)的有效性隱式處理了‘0’的問題一位數(shù)為0無效兩位數(shù)為10或20有效。另一種更清晰的寫法是顯式判斷s[i-1]‘0’的情況。大數(shù)取模題目有時會要求結果對某個大數(shù)如1e97取模務必在每次加法后取模防止中間結果溢出。空間優(yōu)化dp數(shù)組可以優(yōu)化為只使用三個變量因為dp[i]只依賴于dp[i-1]和dp[i-2]。但在競賽中除非內存特別緊張為了代碼清晰可調試使用數(shù)組通常更穩(wěn)妥。3.3 真題三最優(yōu)旅行圖論中的最短路徑變種題目回憶給定一個國家的城市網絡圖以及每個城市的“隔離政策”信息到達某個城市后必須停留滿一定的天數(shù)才能離開。求從起點城市到終點城市總耗時旅行時間停留時間最短的路徑。核心思路拆解 這是一個帶權圖上的最短路徑問題但邊的權重不是固定的。邊的旅行時間是固定的但到達一個節(jié)點后需要額外增加該節(jié)點規(guī)定的停留時間然后才能通過下一條邊離開。這打破了傳統(tǒng)Dijkstra算法“當前最短路徑一旦確定則不再更新”的前提因為即使你更早到達一個城市如果你需要等待更久你的總離開時間即可以作為后續(xù)節(jié)點起算的時間可能反而更晚。問題轉化我們不能簡單地將“城市”作為圖的節(jié)點。因為狀態(tài)不僅取決于你在哪個城市還取決于你“到達”這個城市的時間點這影響了你的等待結束時間。一種思路是使用Dijkstra算法但修改松弛relax條件。狀態(tài)定義與松弛設dist[v]表示最早能夠從城市v出發(fā)的時間注意不是到達v的時間。初始時dist[start] 0可以從起點立即出發(fā)。對于一條從u到v的邊旅行時間為w城市v的強制停留時間為stay[v]。如果我們已知能從u出發(fā)的最早時間是dist[u]那么到達v的時間是dist[u] w。但是到達v后我們必須等到時間arrive_time dist[u] w才能開始計算停留嗎題目通常理解為到達后立即開始執(zhí)行停留政策。所以最早能從v離開的時間是arrive_time stay[v]。因此我們嘗試用arrive_time stay[v]去更新dist[v]。如果這個值比當前記錄的dist[v]小說明我們找到了一條更早能從v出發(fā)的路徑就更新它。算法執(zhí)行使用優(yōu)先隊列最小堆優(yōu)化的Dijkstra算法。隊列中存儲(departure_time, city)。每次取出當前departure_time最小的城市u然后用上述規(guī)則去松弛它的所有鄰居v。最終答案我們要求的是到達終點城市的總耗時。注意dist[dest]記錄的是最早能從終點城市出發(fā)的時間。但終點是目的地我們不需要再從它出發(fā)。所以最終答案應該是到達終點的時間即dist[dest] - stay[dest]不更準確地說我們到達終點后雖然也要遵守停留政策但題目可能只關心“到達”并完成停留的那一刻。通常我們可以將終點的停留時間stay[dest]設為0或者最終答案就是dist[dest]如果dist[v]定義為最早能在v完成停留的時間。C實現(xiàn)與關鍵代碼概念模型#include iostream #include vector #include queue #include climits using namespace std; typedef pairlong long, int pii; // (最早離開時間, 城市編號) long long minTravelTime(int n, int start, int dest, vectorvectorpairint, int graph, // graph[u] { (v, travel_time), ...} vectorint stay_time) { vectorlong long earliest_departure(n, LLONG_MAX); earliest_departure[start] 0 stay_time[start]; // 假設起點也需要停留看題意通常起點停留可設為0或忽略。 priority_queuepii, vectorpii, greaterpii pq; pq.push({earliest_departure[start], start}); while (!pq.empty()) { auto [current_time, u] pq.top(); pq.pop(); if (current_time earliest_departure[u]) continue; // 舊的、非最優(yōu)的記錄跳過 for (auto [v, travel] : graph[u]) { long long arrive_at_v current_time travel; // 到達v的時間 long long depart_from_v arrive_at_v stay_time[v]; // 能從v離開的最早時間 if (depart_from_v earliest_departure[v]) { earliest_departure[v] depart_from_v; pq.push({depart_from_v, v}); } } } // 最終答案到達目的地dest的總時間。 // 如果earliest_departure[v]記錄的是“完成停留可離開”的時間那么到達dest的時間就是它減去停留時間。 // 更合理的定義讓earliest_departure[v]表示“到達v并完成停留”的時刻。那么初始化start就是stay_time[start]。 // 這樣最終答案就是 earliest_departure[dest]。 return earliest_departure[dest]; }避坑指南狀態(tài)定義的清晰性這是本題最核心也最容易混淆的地方。務必在編碼前用注釋明確寫出dist[]數(shù)組的確切含義是到達時間完成停留時間可出發(fā)時間。這直接影響初始化和最終答案的計算。起點和終點的停留根據題意起點城市可能不需要停留stay[start]0終點城市的停留可能不計入總時間stay[dest]0。必須仔細審題。數(shù)據范圍與類型旅行時間和停留時間累加后可能很大需要使用long long。圖的無向/有向明確道路是單向還是雙向。4. 競賽實戰(zhàn)技巧與避坑總結4.1 時間管理策略一場比賽4小時通常有10道左右題目。合理的時間分配至關重要。我的策略是前30分鐘快速通覽。把所有題目都看一遍用紅、黃、綠做簡單標記。綠色是思路清晰、有把握很快AC的簡單題黃色是需要思考、但估計能解的中等題紅色是暫時沒思路或識別出的難題。第1小時解決所有綠色題目。快速、準確地拿到基礎分建立信心。每道題務必通過樣例和自測邊界。中間2小時主攻黃色題目。這是得分的關鍵。一道題如果卡了超過30分鐘還沒有清晰進展做好標記暫時跳過去嘗試另一道黃色或綠色題目。保持節(jié)奏避免在一道題上耗盡時間。最后1小時攻堅與檢查。嘗試紅色難題的暴力解法如果數(shù)據范圍允許以獲取部分分。最后至少留出20分鐘進行全局檢查文件輸入輸出名是否正確所有結果是否都在要求范圍內是否有未提交的代碼4.2 常見“坑點”速查與應對整數(shù)溢出見到累加、乘積特別是涉及階乘、組合數(shù)、路徑計數(shù)時第一時間想到long long。如果結果需要取模在每次運算后取模。數(shù)組越界聲明數(shù)組時大小是否10以留有余地循環(huán)變量是從0開始還是1開始DFS/BFS中訪問節(jié)點前是否檢查了邊界多組輸入未處理題目說“包含多組測試數(shù)據”你的代碼是否用while(cin n n)之類的循環(huán)正確處理了浮點數(shù)精度盡量避免直接比較浮點數(shù)相等(a b)。使用fabs(a-b) 1e-9這樣的方式。如果可能盡量使用整數(shù)運算例如比較分數(shù)a/b和c/d時轉化為比較a*d和c*b。遞歸深度過大DFS時如果圖或樹很深超過1e5遞歸可能導致棧溢出。可以顯式設置棧大小競賽環(huán)境不一定允許或改用迭代棧模擬的DFS。輸出格式錯誤最后一行是否需要換行數(shù)字之間用空格還是逗號分隔特別是“Case #1: ”這種帶前綴的輸出容易漏掉。4.3 調試與對拍技巧在競賽環(huán)境中沒有強大的IDE調試器printf/cerr 調試法是王道。關鍵變量輸出在算法關鍵步驟后輸出中間變量的值。提交前記得注釋掉或刪除這些調試輸出。小數(shù)據測試自己構造一些小的、手算能知道答案的測試數(shù)據驗證代碼邏輯。對拍暴力法驗證對于一道題如果你寫了一個高效但復雜的算法正解同時可以很容易地寫一個保證正確但超時的暴力算法用于小數(shù)據范圍。寫一個腳本隨機生成大量小規(guī)模數(shù)據分別用兩個程序跑比較輸出。這是發(fā)現(xiàn)邏輯錯誤最有效的方法之一。在本地可以用簡單的批處理或Python腳本實現(xiàn)。4.4 代碼風格與可讀性清晰的代碼在調試時能節(jié)省大量時間。命名變量名、函數(shù)名要有意義。i, j, k用于循環(huán)n, m用于規(guī)模dp,vis,dist用于算法數(shù)組。注釋在復雜算法或易錯點旁寫下簡短注釋說明這段代碼在做什么為什么這么做。函數(shù)化將獨立的邏輯塊封裝成函數(shù)如readInput(),solve(),dfs()。這使主函數(shù)更清晰也便于單獨測試。預處理對于多組數(shù)據輸入如果有一些可以預先計算好的表如素數(shù)表、組合數(shù)表、階乘表可以在程序開始前一次性算好避免每組數(shù)據重復計算。回顧2020年的這些題目它們考察的不僅僅是數(shù)據結構和算法的知識更是將實際問題抽象、建模并穩(wěn)健實現(xiàn)的能力。比賽的意義遠不止于名次更在于這段高強度、聚焦式的訓練過程它能極大地鍛煉一個人的邏輯思維、編碼能力和心理素質。對于解題本身我最大的體會是“慢就是快”花足夠的時間去理解題意、設計算法、構思邊界往往比匆忙開始寫代碼、然后陷入無盡的調試要高效得多。希望這篇針對性的復盤能幫助你更從容地面對未來的算法挑戰(zhàn)。