1. 項目概述一份沉淀了實戰經驗的“藍橋杯”基礎算法模板庫如果你正在備戰藍橋杯或者任何需要快速上手基礎算法和數據結構的編程競賽、面試那你大概率經歷過這樣的時刻面對一道題思路清晰但下筆敲鍵盤時卻卡在了某個基礎操作的實現上——二分查找的邊界怎么定快速排序的遞歸出口怎么寫鄰接表存圖又該怎么初始化時間在調試這些“輪子”中一點點流逝最終可能功虧一簣。“第十二屆_國賽藍橋杯個人模板_基礎篇”這個項目正是為了解決這個痛點而生。它不是一份冷冰冰的官方文檔而是一位或一群從實戰中摸爬滾打過來的選手將自己多次參賽、刷題中那些經過反復驗證、最常用、最可靠的代碼片段系統化整理而成的私人武器庫。其核心價值在于“即拿即用”和“避坑指南”。當你理解了算法思想后可以直接調用這些模板將精力集中在問題建模和策略設計上而不是重復實現基礎功能。更重要的是這些模板里通常凝結了原作者踩過的無數“坑”比如二分查找時是mid (left right) 1還是mid left (right - left) / 2以防溢出比如深度優先搜索DFS中狀態回溯的精確位置這些都是教科書上可能一筆帶過但實戰中決定成敗的細節。這份“基礎篇”模板主要面向的正是算法競賽入門和進階階段的選手。它覆蓋了如排序、查找、圖論、樹結構、動態規劃基礎、數學計算等核心模塊。通過它你不僅能獲得代碼更能透過代碼看到一種高效的、經過競賽檢驗的編程風格和思維模式。接下來我將以一名多次參與類似競賽的“老選手”視角為你深度拆解這樣一份模板庫的設計思路、核心內容以及如何高效地將其轉化為你自己的實戰能力。2. 模板庫的整體架構與設計哲學2.1 為什么需要個人模板庫很多新手可能會問網上開源模板那么多為什么還要自己整理直接抄不就行了這里涉及到一個關鍵區別“知道”和“熟練使用”之間隔著一道名為“內化”的鴻溝。直接拷貝的模板你在緊張的比賽環境中很容易用錯因為你不理解其每個細節的設計初衷。而自己整理、在大量題目中反復使用并調整過的模板已經成為了你思維的一部分。個人模板庫的設計首要原則是“高內聚、低耦合、零黑盒”。每個模板函數應該功能單一且完整高內聚模塊之間盡量減少依賴低耦合并且你必須對模板里的每一行代碼都了如指掌零黑盒。這意味著你不能僅僅從網上復制一段“效率最高”的奇技淫巧代碼而必須選擇你真正理解、能駕馭的實現方式。例如快速排序的模板你可能選擇經典的Hoare劃分法因為它邏輯清晰也可能選擇Lomuto劃分法因為它實現簡單。無論哪種你需要清楚其最壞時間復雜度、如何避免以及如何針對競賽數據特點進行微調比如在小區間切換為插入排序。2.2 基礎篇的核心模塊劃分一份典型的“基礎篇”模板庫通常會按照算法和數據結構的類型進行模塊化組織而不是簡單地羅列代碼。這種組織方式便于快速定位和復習。基于常見的競賽大綱和實戰需求可以將其劃分為以下幾個核心模塊輸入輸出與常用宏競賽環境的輸入輸出優化是第一步。這包括關閉流同步、使用scanf/printf還是快讀快寫、定義一些常用的宏如for循環宏、無窮大常量INF。基礎數據結構數組、鏈表靜態數組模擬、棧、隊列包括循環隊列和雙端隊列、堆優先隊列。重點是它們的數組模擬實現因為比STL容器更快且更可控。排序與查找算法快速排序、歸并排序兼用于求逆序對、堆排序、二分查找整數域和浮點數域、lower_bound/upper_bound 的手動實現。圖論基礎圖的存儲鄰接矩陣、鄰接表、深度優先搜索DFS、廣度優先搜索BFS、拓撲排序、最短路徑Dijkstra, Bellman-Ford, Floyd-Warshall、最小生成樹Kruskal, Prim。樹狀數據結構并查集、二叉樹遍歷前中后序、層序、二叉搜索樹基礎、線段樹、樹狀數組Fenwick Tree。動態規劃基礎經典模型0/1背包、完全背包、最長公共子序列、最長上升子序列的模板化實現。數學工具最大公約數GCD、最小公倍數LCM、快速冪、素數篩法埃氏篩、歐拉篩、簡單組合數學。每個模塊的模板都不是孤立的。例如Kruskal算法模板必然依賴于并查集模板拓撲排序模板依賴于隊列模板和鄰接表存圖。在設計時需要考慮這些依賴關系并合理安排聲明順序或通過頭文件管理。2.3 模板代碼的風格與注釋規范模板代碼的風格直接決定了其可用性和可維護性。競賽模板追求極致的清晰和一定的效率而非企業級的泛用性。命名函數和變量名應直觀。例如binary_search_first()查找第一個滿足條件的值dijkstra(int s)。參數與返回值接口設計要簡潔。輸入參數通常是基礎數據數組、大小、起點終點返回值明確。對于需要修改多個結果的函數可以使用引用參數。注釋注釋不是解釋算法原理那是你應該掌握的而是標注易錯點和使用前提。例如在Dijkstra模板旁注釋“適用于非負權圖使用優先隊列優化復雜度 O((VE)logV)”。在二分查找模板旁注釋“區間為 [l, r]退出時 l 為第一個滿足條件的位置注意檢查越界”。防御性編程在模板中適當加入斷言assert或條件判斷幫助在調試時快速發現問題。例如在并查集的find函數中可以判斷下標是否越界。3. 核心模板解析與實現細節3.1 二分查找邊界處理的“藝術”二分查找是算法競賽中最常用也最容易出錯的算法之一。其核心難點在于循環不變量的維持和邊界條件的處理。一個健壯的二分模板應該能處理四種常見情況尋找第一個等于目標值的位置、最后一個等于目標值的位置、第一個大于等于目標值的位置、第一個大于目標值的位置。這里以在非降序數組arr中查找“第一個大于等于目標值target的位置”即 C STL 中的lower_bound為例展示一個經過千錘百煉的模板// 在 arr[l...r] 區間中尋找第一個 target 的元素下標 // 如果所有元素都 target則返回 r1 (即數組長度) int lower_bound(int arr[], int l, int r, int target) { while (l r) { // 關鍵1循環條件當區間有效時繼續 int mid l (r - l) / 2; // 關鍵2防止 (lr) 可能出現的溢出 if (arr[mid] target) { r mid - 1; // 關鍵3mid 滿足條件說明答案在 mid 或左側收縮右邊界 } else { l mid 1; // 關鍵4mid 不滿足條件說明答案在右側收縮左邊界 } } // 循環結束時l r1。 // 根據不變性arr[0...l-1] target, arr[l...n-1] target return l; }實操心得與避坑指南循環條件while (l r)這是閉區間搜索的寫法。它保證了搜索區間從[l, r]開始并能正確處理區間內只有一個元素的情況。與之相對的while (l r)是左閉右開區間[l, r)的寫法兩者在邊界更新上略有不同選定一種并貫穿始終切忌混用。中點計算mid l (r - l) / 2這是標準寫法能絕對避免(l r)在l和r都是大整數時可能發生的溢出。雖然競賽數據通常不會讓int溢出但養成這個習慣能避免未來在其它場景出錯。邊界更新r mid - 1和l mid 1這是二分查找的“靈魂”。必須確保每次循環搜索區間都被嚴格縮小。如果更新寫成r mid或l mid在某些情況下比如l 0, r 1可能導致死循環。-1和1的操作正是為了排除已經判斷過的mid位置。返回值l循環結束時l指向第一個滿足arr[i] target的位置。這個結論基于一個循環不變量在每次循環開始時[0, l-1]區間內的元素都 target[r1, n-1]區間內的元素都 target。理解并信任這個不變量比死記硬背返回值更重要。注意對于浮點數二分比如求平方根循環條件通常改為while (r - l eps)其中eps是一個極小的精度值如1e-7。邊界更新則直接是l mid或r mid因為浮點數沒有“加一減一”的概念。3.2 并查集路徑壓縮與按秩合并并查集是處理不相交集合合并與查詢問題的利器其模板看似簡單但優化細節直接影響效率。class UnionFind { private: vectorint parent; vectorint rank; // 按秩合并的秩也可以用 size 數組記錄集合大小 public: UnionFind(int n) { parent.resize(n); rank.resize(n, 0); // 初始秩為0 for (int i 0; i n; i) parent[i] i; // 初始化每個元素自成一集合 } // 查找根節點含路徑壓縮 int find(int x) { // 普通查找 while (x ! parent[x]) x parent[x]; // 路徑壓縮優化 if (parent[x] ! x) { parent[x] find(parent[x]); // 遞歸壓縮最終使樹高為1 } return parent[x]; } // 合并兩個集合 void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 已在同一集合 // 按秩合并將矮樹接到高樹下 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { // 秩相等時任意合并但秩要加一 parent[rootY] rootX; rank[rootX]; } } // 判斷是否連通 bool connected(int x, int y) { return find(x) find(y); } };核心細節解析路徑壓縮Path Compression在find函數中parent[x] find(parent[x])這行遞歸代碼是效率的關鍵。它不僅找到了根節點而且在回溯過程中將查找路徑上的所有節點都直接指向了根節點。這樣下次查詢這些節點時就是 O(1) 時間復雜度。經過多次操作后并查集的樹結構會變得非常扁平。按秩合并Union by Rankrank數組記錄的是樹高的上界。合并時總是將較矮的樹根連接到較高的樹根下。這樣可以避免樹退化成鏈狀保證操作的平均時間復雜度接近常數。當兩棵樹高度相同時合并后樹高會增加1所以需要rank[rootX]。初始化務必記得在構造函數中將每個元素的父節點設為自己。“秩”與“大小”這里用了“秩”rank也可以使用“集合大小”size。按大小合并的邏輯是將小集合合并到大集合下。兩者都能達到優化目的且時間復雜度分析類似。選擇哪一種取決于你的需求如果需要頻繁查詢集合大小那么用size數組會更方便。3.3 圖的鄰接表存儲與DFS/BFS模板圖論題目千變萬化但基礎遍歷是根本。鄰接表是最常用的存儲方式尤其適合稀疏圖。#include vector #include queue using namespace std; const int MAXN 100010; // 根據題目最大頂點數調整 vectorint graph[MAXN]; // 鄰接表graph[u] 存儲 u 的所有鄰接點 v bool visited[MAXN]; // 訪問標記數組 // 深度優先搜索 (DFS) 遞歸模板 void dfs(int u) { visited[u] true; // 這里可以對頂點 u 進行操作例如打印、計數等 // printf(Visit %d\n, u); for (int v : graph[u]) { // 遍歷 u 的所有鄰居 v if (!visited[v]) { dfs(v); // 遞歸訪問 } } // 如果需要回溯可以在這里恢復 visited[u] false; } // 廣度優先搜索 (BFS) 迭代模板 void bfs(int start) { queueint q; q.push(start); visited[start] true; while (!q.empty()) { int u q.front(); q.pop(); // 處理頂點 u for (int v : graph[u]) { if (!visited[v]) { visited[v] true; q.push(v); } } } } // 添加一條從 u 到 v 的邊無向圖 void addEdge(int u, int v) { graph[u].push_back(v); graph[v].push_back(u); // 有向圖則去掉這行 }使用要點與常見問題存儲結構選擇vectorint graph[MAXN]是靜態數組套動態數組在競賽中很常見。如果頂點數MAXN很大超過 10^5但邊數不確定這種方式既節省空間相對于鄰接矩陣訪問速度也快。另一種寫法是vectorvectorint graph(N)在運行時確定大小更靈活但稍慢。visited數組的初始化與重置在調用dfs或bfs前必須確保visited數組被正確初始化通常用memset(visited, 0, sizeof(visited))或循環賦值為false。如果圖中有多個連通分量需要對所有未訪問的節點調用遍歷函數。遞歸深度限制DFS的遞歸實現簡潔但遞歸深度受系統棧限制。對于頂點數超過約 10^5 的深圖遞歸DFS可能導致棧溢出。此時需要改為棧迭代實現的非遞歸DFS或者確保題目數據不會形成極端深的鏈。BFS與最短路徑在無權圖中BFS第一次訪問到一個節點時所經過的邊數就是從起點到該節點的最短路徑長度。這是BFS一個非常重要的性質常用于求解最短步數問題。邊的添加addEdge函數展示了無向圖的添加。對于有向圖只需單向添加。如果邊有權重需要定義結構體struct Edge {int to, weight;};然后將vectorint改為vectorEdge。4. 動態規劃基礎模板0/1背包與最長上升子序列動態規劃DP是競賽重難點但其基礎模型有很強的模板性。掌握幾個經典模型的模板能解決一大批變形題目。4.1 0/1背包問題模板問題描述有N件物品和一個容量為V的背包。第i件物品的體積是v[i]價值是w[i]。求解將哪些物品裝入背包可使這些物品的總體積不超過背包容量且總價值最大。二維DP模板易于理解// dp[i][j] 表示考慮前 i 件物品在背包容量為 j 的情況下能獲得的最大價值 vectorvectorint dp(N 1, vectorint(V 1, 0)); for (int i 1; i N; i) { // 枚舉物品 for (int j 0; j V; j) { // 枚舉容量 // 不選第 i 件物品 dp[i][j] dp[i-1][j]; // 如果容量允許嘗試選第 i 件物品 if (j v[i]) { dp[i][j] max(dp[i][j], dp[i-1][j - v[i]] w[i]); } } } int ans dp[N][V];一維滾動數組優化空間優化必須掌握// dp[j] 表示背包容量為 j 的情況下能獲得的最大價值 vectorint dp(V 1, 0); for (int i 1; i N; i) { // 枚舉物品 // 關鍵容量必須從大到小遍歷保證 dp[j - v[i]] 是上一輪i-1的結果 for (int j V; j v[i]; --j) { dp[j] max(dp[j], dp[j - v[i]] w[i]); } } int ans dp[V];核心要點狀態定義dp[i][j]是最經典的定義方式代表了DP的“階段”物品和“狀態”容量。狀態轉移核心決策是“放”還是“不放”當前物品。取兩者中價值最大者。一維優化原理觀察二維轉移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-v[i]] w[i])當前第i層狀態只依賴于第i-1層狀態。因此可以用一個一維數組滾動更新。逆序枚舉容量j是為了保證在更新dp[j]時dp[j - v[i]]還是上一輪未包含當前物品i的值。如果順序枚舉dp[j - v[i]]可能已經被本輪更新過相當于物品被重復放入這就變成了“完全背包”問題。4.2 最長上升子序列LIS模板問題描述給定一個長度為N的數組nums找到其中最長的、嚴格遞增的子序列的長度。動態規劃 O(N2) 模板vectorint dp(N, 1); // dp[i] 表示以 nums[i] 結尾的最長上升子序列長度 int ans 0; for (int i 0; i N; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } // ans 即為答案貪心二分查找 O(N logN) 優化模板vectorint d; // d 是一個單調遞增的數組d[len] 表示長度為 len 的上升子序列的末尾元素的最小值 d.push_back(nums[0]); // 初始化長度為1的子序列末尾是第一個元素 for (int i 1; i N; i) { if (nums[i] d.back()) { // 如果當前元素大于 d 的最后一個元素可以延長子序列 d.push_back(nums[i]); } else { // 否則在 d 中找到第一個 nums[i] 的位置用 nums[i] 替換它 // 這樣做的目的是讓后續的上升子序列“更有潛力”變得更長 int pos lower_bound(d.begin(), d.end(), nums[i]) - d.begin(); d[pos] nums[i]; } } int ans d.size(); // d 的長度就是最長上升子序列的長度算法解析與對比O(N2) DP思路直觀。dp[i]依賴于所有j i且nums[j] nums[i]的狀態。缺點是數據規模超過 5000 就可能超時。O(N logN) 貪心二分這個算法非常巧妙。它維護的數組d并不直接記錄一個合法的LIS而是記錄每個長度下末尾元素的最小可能值。這個最小值序列d是單調遞增的可以用反證法證明。當遇到一個新數nums[i]如果它比所有末尾都大說明我們可以得到一個更長的上升子序列。否則我們找到d中第一個大于等于它的位置并替換。替換不會改變d的長度但讓這個長度的上升子序列的“門檻”變低了為后面接上更大的數創造了可能。如何獲取具體序列O(N logN) 的方法在過程中丟失了序列的具體信息。如果需要輸出一個具體的LIS通常需要配合一個parent數組來回溯或者使用 O(N2) 的DP方法。5. 模板的使用、調試與個性化5.1 如何將模板“內化”為己用死記硬背模板是低效的。正確的做法是理解每一行對于每個模板花時間搞懂每個變量、每行代碼的作用。特別是邊界條件和循環不變量的部分。可以嘗試用簡單的數據手動模擬執行過程。反復默寫在不看原模板的情況下嘗試自己從頭實現。卡住的時候再去看找到知識盲點。直到你能流暢、正確地默寫出核心模板。針對性練習在在線判題系統如藍橋杯練習系統、LeetCode、AcWing上尋找對應模板的經典題目進行練習。用你的模板去解題并適應不同的輸入輸出格式。制造錯誤故意寫錯一些地方比如二分查找去掉-1和1然后分析為什么錯了會產生什么后果死循環、錯誤答案。這種主動踩坑的經歷會讓你印象無比深刻。建立索引給你的模板庫加上清晰的注釋和目錄。可以按算法分類也可以按功能分類如“圖論-最短路徑”。在比賽或練習時能快速找到所需模板。5.2 調試模板的常見技巧即使模板經過千錘百煉在新的問題語境下也可能需要調整或出現錯誤。小數據測試用最簡單的、你知道答案的案例測試。例如測試二分查找可以用數組[1,3,5,7,9]分別查找0, 1, 4, 9, 10檢查返回值是否符合預期第一個target的位置。邊界測試測試空數組、單元素數組、所有元素相同、升序/降序數組等特殊情況。打印中間狀態在復雜的DP或搜索算法中在關鍵步驟后打印出狀態數組dp數組、visited數組等與你的手動推導進行對比。對拍對于不確定的題目可以寫一個“暴力算法”通常時間復雜度高但正確性顯然和你的“模板優化算法”進行對拍。用隨機生成的大量數據同時運行兩個程序比較輸出是否一致。這是競賽調試的終極武器。模塊化測試確保每個基礎模板如并查集、快速排序本身是正確的。將它們封裝成函數或類單獨編寫測試用例驗證。5.3 根據個人習慣進行個性化調整沒有絕對“最好”的模板只有“最適合你”的模板。在理解通用模板的基礎上可以根據你的思維習慣進行微調。變量命名如果你覺得l, r不如left, right直觀就改掉。一致性比遵循某種約定更重要。循環風格有人喜歡for循環有人喜歡while循環。只要邏輯正確用你順手的方式。代碼簡潔性 vs 可讀性在保證正確性和效率的前提下你可以選擇更簡潔或更詳細的寫法。例如DFS的遞歸部分有人喜歡把visited標記放在遞歸調用前有人喜歡放在剛進入函數時。只要不影響邏輯都可以。添加調試宏在本地開發時可以定義一些調試宏方便打印信息。比賽時則關閉它們。#ifdef LOCAL #define debug(...) fprintf(stderr, __VA_ARGS__) #else #define debug(...) 42 #endif最終這份“第十二屆_國賽藍橋杯個人模板_基礎篇”的價值不在于它代碼本身有多精妙而在于它代表了一種系統化、工程化的備賽方法。它強迫你去思考、去整理、去理解那些最本質的算法構件。當你真正擁有這樣一份屬于自己的、充滿注釋和心得的模板庫時你在賽場上的從容和自信將會是任何現成的代碼都無法給予的。