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