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