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