簡(jiǎn)介這是一份面向競(jìng)賽編程與算法學(xué)習(xí)者的C算法模板庫(kù)聚焦在有限時(shí)間內(nèi)快速調(diào)用經(jīng)過(guò)優(yōu)化的常用算法與數(shù)據(jù)結(jié)構(gòu)解決大規(guī)模數(shù)據(jù)與高性能計(jì)算場(chǎng)景下的實(shí)現(xiàn)難題。壓縮包共127個(gè)文件以123個(gè)cpp源碼為主體另含2個(gè)md說(shuō)明、1個(gè)tex與1個(gè)pdf文檔整體約730KB體量輕便、便于隨取隨用。內(nèi)容覆蓋基礎(chǔ)算法中的雙指針、離散化、前綴和與差分、二分查找、單調(diào)棧與單調(diào)隊(duì)列、尺取法、樹(shù)的中心、拓?fù)渑判驍?shù)學(xué)部分包含素?cái)?shù)篩法、質(zhì)因數(shù)分解、歐拉函數(shù)、組合數(shù)、擴(kuò)展歐幾里得、線(xiàn)性同余方程、容斥原理、高斯消元、矩陣乘法、莫比烏斯反演、BSGS與FFT數(shù)據(jù)結(jié)構(gòu)涉及并查集、Sparse Table、Trie、樹(shù)狀數(shù)組、線(xiàn)段樹(shù)、樹(shù)鏈剖分、可持久化線(xiàn)段樹(shù)與莫隊(duì)圖論則涵蓋Floyd、BellmanFord、SPFA、Dijkstra、分層圖最短路、差分約束、最小生成樹(shù)、LCA、二分圖匹配、強(qiáng)連通分量與2SAT等。已有76人學(xué)習(xí)適合希望系統(tǒng)整理模板、快速查漏補(bǔ)缺的選手參考。1. 算法模板庫(kù)到底解決什么問(wèn)題從一道單調(diào)棧題說(shuō)起刷題刷到一定階段你會(huì)發(fā)現(xiàn)一個(gè)尷尬的事實(shí)每道題的解法你好像都見(jiàn)過(guò)但真到寫(xiě)的時(shí)候二分邊界又調(diào)了十分鐘并查集的路徑壓縮又忘了寫(xiě)快速冪的取模又溢出了。這不是你笨而是算法競(jìng)賽和面試準(zhǔn)備本身就有一套「重復(fù)造輪子」的損耗?；?C 的算法模板庫(kù)本質(zhì)上就是把這套損耗一次性干掉——把二分、并查集、線(xiàn)段樹(shù)、單調(diào)棧、快速冪、圖論最短路這些高頻結(jié)構(gòu)提前寫(xiě)成經(jīng)過(guò)驗(yàn)證的、接口統(tǒng)一的頭文件比賽或面試時(shí)直接調(diào)用。這個(gè)方向適合三類(lèi)人一是準(zhǔn)備 C 面試、需要快速手寫(xiě)八股的求職者二是打算法競(jìng)賽、追求編碼速度的選手三是想把算法能力沉淀成個(gè)人資產(chǎn)、而不是每次從零推導(dǎo)的工程師。標(biāo)題里的「源碼」兩個(gè)字很關(guān)鍵——它不是讓你背模板而是讓你擁有一套可以編譯、可以改、可以按自己習(xí)慣重構(gòu)的代碼庫(kù)。接下來(lái)我會(huì)按「怎么組織這套庫(kù) → 每個(gè)模塊怎么寫(xiě) → 怎么驗(yàn)證 → 坑在哪」的順序把這件事講透。2. 模板庫(kù)的目錄結(jié)構(gòu)與編譯方式別把所有代碼塞進(jìn)一個(gè) main.cpp2.1 為什么模板庫(kù)要按「數(shù)據(jù)結(jié)構(gòu) / 圖論 / 數(shù)學(xué) / 字符串」分目錄很多人第一次攢模板習(xí)慣把所有函數(shù)寫(xiě)在一個(gè)template.cpp里用的時(shí)候整段復(fù)制。這個(gè)做法在只有十幾個(gè)模板時(shí)還能忍一旦超過(guò)三十個(gè)找起來(lái)就是災(zāi)難而且不同模板之間的宏定義、類(lèi)型別名會(huì)互相污染。常見(jiàn)做法是按算法領(lǐng)域拆成獨(dú)立頭文件每個(gè)頭文件自包含只依賴(lài)標(biāo)準(zhǔn)庫(kù)不依賴(lài)其他模板。這樣你在比賽時(shí)只需要#include segtree.hpp不會(huì)因?yàn)橐胍粋€(gè)二分而帶進(jìn)一堆無(wú)關(guān)代碼。我一般會(huì)這樣組織目錄algo-template/ ├── include/ │ ├── ds/ # 數(shù)據(jù)結(jié)構(gòu) │ │ ├── dsu.hpp │ │ ├── segtree.hpp │ │ └── monotonic_stack.hpp │ ├── graph/ # 圖論 │ │ ├── dijkstra.hpp │ │ └── topo_sort.hpp │ ├── math/ # 數(shù)學(xué) │ │ ├── fast_pow.hpp │ │ └── gcd_lcm.hpp │ └── string/ # 字符串 │ └── kmp.hpp ├── tests/ # 每個(gè)模板對(duì)應(yīng)的驗(yàn)證用例 │ ├── test_dsu.cpp │ └── test_segtree.cpp └── CMakeLists.txt這個(gè)結(jié)構(gòu)的好處是每個(gè).hpp可以單獨(dú)編譯測(cè)試tests/目錄保證你改完模板后能立刻驗(yàn)證沒(méi)寫(xiě)崩。CMakeLists 只負(fù)責(zé)把 tests 編譯成可執(zhí)行文件模板本身是 header-only不需要單獨(dú)編譯成庫(kù)。2.2 用 CMake 把模板庫(kù)跑起來(lái)的最小配置header-only 庫(kù)的 CMake 配置非常輕核心就是指定 include 路徑、開(kāi)啟 C17、把測(cè)試文件逐個(gè)注冊(cè)成可執(zhí)行目標(biāo)。下面是我常用的最小CMakeLists.txtcmake_minimum_required(VERSION 3.16) project(algo_template CXX) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) set(CMAKE_CXX_FLAGS ${CMAKE_CXX_FLAGS} -Wall -Wextra -O2) # 模板頭文件所在目錄 include_directories(${CMAKE_SOURCE_DIR}/include) # 自動(dòng)收集 tests 目錄下所有 cpp每個(gè)編譯成一個(gè)可執(zhí)行文件 file(GLOB TEST_SOURCES ${CMAKE_SOURCE_DIR}/tests/*.cpp) foreach(test_src ${TEST_SOURCES}) get_filename_component(test_name ${test_src} NAME_WE) add_executable(${test_name} ${test_src}) endforeach()邏輯說(shuō)明include_directories讓測(cè)試文件能直接#include ds/dsu.hppfile(GLOB ...)自動(dòng)發(fā)現(xiàn)測(cè)試文件新增一個(gè)test_xxx.cpp不用改 CMake-Wall -Wextra是必須的模板代碼里的符號(hào)比較、類(lèi)型截?cái)鄦?wèn)題全靠它暴露。參數(shù)上-O2在驗(yàn)證性能敏感模板比如線(xiàn)段樹(shù)時(shí)建議保留否則你可能誤判模板效率。編譯和運(yùn)行mkdir build cd build cmake .. make -j4 ./test_dsu如果test_dsu輸出全部用例通過(guò)說(shuō)明這套骨架已經(jīng)可用。接下來(lái)往里填模板就行。提示不要用-O0驗(yàn)證模板正確性某些未定義行為比如越界讀在-O2下才暴露而比賽和面試手寫(xiě)時(shí)通常默認(rèn)開(kāi)優(yōu)化。3. 高頻模板怎么寫(xiě)并查集、單調(diào)棧、快速冪三個(gè)樣板3.1 并查集路徑壓縮加按秩合并的完整實(shí)現(xiàn)并查集是模板庫(kù)里復(fù)用率最高的結(jié)構(gòu)之一面試手寫(xiě)頻率極高。核心就兩個(gè)操作find和unite。只寫(xiě)路徑壓縮已經(jīng)夠用但加上按秩合并能把均攤復(fù)雜度壓到接近常數(shù)。下面是我模板庫(kù)里的dsu.hpp#pragma once #include vector #include numeric class DSU { public: // n 個(gè)元素初始各自獨(dú)立 explicit DSU(int n) : parent_(n), rank_(n, 0) { std::iota(parent_.begin(), parent_.end(), 0); } // 查找根節(jié)點(diǎn)帶路徑壓縮 int find(int x) { if (parent_[x] ! x) parent_[x] find(parent_[x]); // 遞歸壓縮 return parent_[x]; } // 合并兩個(gè)集合按秩合并 bool unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; // 已在同一集合 if (rank_[ra] rank_[rb]) std::swap(ra, rb); parent_[rb] ra; if (rank_[ra] rank_[rb]) rank_[ra]; return true; } bool same(int a, int b) { return find(a) find(b); } private: std::vectorint parent_; std::vectorint rank_; };邏輯說(shuō)明find用遞歸實(shí)現(xiàn)路徑壓縮代碼最短unite先找根再按秩決定誰(shuí)掛到誰(shuí)下面秩相同才增加。參數(shù)上n是元素個(gè)數(shù)元素編號(hào)默認(rèn) 0 到 n-1如果你的題目是 1-based構(gòu)造時(shí)傳n1并忽略下標(biāo) 0 即可。注意遞歸find在極端鏈?zhǔn)綌?shù)據(jù)下可能爆棧如果數(shù)據(jù)量到 1e6 以上改成迭代版本更穩(wěn)。3.2 單調(diào)棧下一個(gè)更大元素的標(biāo)準(zhǔn)寫(xiě)法單調(diào)棧是「用空間換時(shí)間」的典型很多題柱狀圖最大矩形、每日溫度都是它的變體。模板庫(kù)里應(yīng)該有一個(gè)通用的「求每個(gè)元素左邊/右邊第一個(gè)更大/更小元素」的函數(shù)。下面這個(gè)版本返回每個(gè)位置右邊第一個(gè)更大元素的下標(biāo)不存在則為 -1#pragma once #include vector #include stack // 返回每個(gè)位置右側(cè)第一個(gè)嚴(yán)格更大元素的下標(biāo)無(wú)則 -1 std::vectorint nextGreaterElement(const std::vectorint nums) { int n nums.size(); std::vectorint res(n, -1); std::stackint st; // 存下標(biāo)對(duì)應(yīng)值單調(diào)遞減 for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { res[st.top()] i; // 找到了右側(cè)第一個(gè)更大 st.pop(); } st.push(i); } return res; }邏輯說(shuō)明棧里維護(hù)的是「還沒(méi)找到更大元素」的下標(biāo)且對(duì)應(yīng)值從棧底到棧頂遞減。遍歷到i時(shí)把所有比nums[i]小的棧頂彈出來(lái)它們右側(cè)第一個(gè)更大就是i。參數(shù)上nums傳值還是傳引用看習(xí)慣數(shù)據(jù)量大時(shí)建議傳const避免拷貝。把改成就變成「嚴(yán)格更大」和「非嚴(yán)格更大」的區(qū)別這是最容易翻車(chē)的地方寫(xiě)模板時(shí)一定要在注釋里標(biāo)清楚。3.3 快速冪取模版本和非取模版本要分開(kāi)快速冪是數(shù)學(xué)模塊的標(biāo)配但很多人只寫(xiě)一個(gè)版本結(jié)果在需要取模的題里溢出或者在不取模的題里被模數(shù)限制。我的做法是提供兩個(gè)重載一個(gè)帶模數(shù)一個(gè)不帶。帶模版本用long long防溢出#pragma once // 快速冪不取模注意結(jié)果可能溢出 long long fastPow(long long base, long long exp) { long long res 1; while (exp 0) { if (exp 1) res * base; base * base; exp 1; } return res; } // 快速冪取模mod 建議用 long long long long fastPowMod(long long base, long long exp, long long mod) { long long res 1 % mod; base % mod; while (exp 0) { if (exp 1) res res * base % mod; base base * base % mod; exp 1; } return res; }邏輯說(shuō)明二進(jìn)制拆分指數(shù)每次把底數(shù)平方。取模版本里res初始化為1 % mod是為了處理mod 1的邊界。參數(shù)上exp用long long是因?yàn)橛行╊}指數(shù)會(huì)超過(guò)intmod也建議long long避免兩個(gè)int相乘溢出。這兩個(gè)函數(shù)建議放在同一個(gè)頭文件里命名區(qū)分清楚別指望調(diào)用方記得住哪個(gè)取模。注意fastPow不取模版本在指數(shù)稍大時(shí)就會(huì)溢出模板庫(kù)里應(yīng)該默認(rèn)引導(dǎo)使用者用取模版本非取模版本只在明確知道結(jié)果范圍時(shí)使用。4. 模板庫(kù)的驗(yàn)證與測(cè)試別等比賽時(shí)才發(fā)現(xiàn)模板寫(xiě)錯(cuò)了4.1 每個(gè)模板配一個(gè)暴力對(duì)拍測(cè)試模板庫(kù)最大的風(fēng)險(xiǎn)不是「不會(huì)寫(xiě)」而是「寫(xiě)錯(cuò)了但自己不知道」。我見(jiàn)過(guò)太多人比賽時(shí)套自己模板結(jié)果線(xiàn)段樹(shù)區(qū)間更新寫(xiě)反調(diào)到最后發(fā)現(xiàn)是模板的鍋。解決辦法很土但有效每個(gè)模板配一個(gè)暴力版本用隨機(jī)數(shù)據(jù)對(duì)拍。以并查集為例#include ds/dsu.hpp #include cassert #include cstdlib #include iostream int main() { for (int iter 0; iter 1000; iter) { int n rand() % 50 1; DSU dsu(n); // 暴力維護(hù)連通性 std::vectorstd::vectorbool conn(n, std::vectorbool(n, false)); for (int i 0; i n; i) conn[i][i] true; for (int op 0; op 200; op) { int a rand() % n, b rand() % n; if (rand() % 2) { dsu.unite(a, b); for (int i 0; i n; i) for (int j 0; j n; j) if (conn[i][a] conn[b][j]) conn[i][j] true; } else { bool expect conn[a][b]; assert(dsu.same(a, b) expect); } } } std::cout DSU all tests passed\n; return 0; }邏輯說(shuō)明隨機(jī)生成操作序列一邊用模板跑一邊用暴力二維布爾數(shù)組維護(hù)連通性每次查詢(xún)都斷言?xún)烧咭恢?。參?shù)上迭代次數(shù) 1000、元素?cái)?shù)上限 50、操作數(shù) 200 是我常用的組合能在幾秒內(nèi)跑完且覆蓋大部分邊界。這個(gè)模式可以復(fù)制到線(xiàn)段樹(shù)、最短路等所有模板上暴力版本怎么寫(xiě)取決于模板功能但思路一致。4.2 用編譯期斷言檢查接口一致性模板庫(kù)的接口一旦定下來(lái)最好用static_assert鎖住關(guān)鍵類(lèi)型避免以后重構(gòu)時(shí)不小心改壞。比如快速冪取模版本可以斷言返回類(lèi)型和參數(shù)類(lèi)型一致#include math/fast_pow.hpp #include type_traits static_assert(std::is_same_vdecltype(fastPowMod(2LL, 10LL, 1000LL)), long long, fastPowMod should return long long);邏輯說(shuō)明static_assert在編譯期檢查不產(chǎn)生運(yùn)行時(shí)代價(jià)。參數(shù)上decltype推導(dǎo)函數(shù)返回類(lèi)型std::is_same_v做比較。這個(gè)技巧適合放在每個(gè)頭文件末尾作為接口契約的一部分。如果哪天有人把返回類(lèi)型改成int編譯直接失敗比運(yùn)行時(shí)出錯(cuò)早得多。提示對(duì)拍測(cè)試不要只跑一次就刪把它留在tests/目錄里每次改模板后重新make一遍這是模板庫(kù)能長(zhǎng)期可信的唯一保障。5. 避坑與常見(jiàn)問(wèn)題模板庫(kù)用錯(cuò)比不會(huì)更可怕5.1 現(xiàn)象并查集 find 遞歸爆棧原因數(shù)據(jù)退化成鏈解決改迭代或加路徑減半現(xiàn)象是程序在 1e6 級(jí)別數(shù)據(jù)上直接段錯(cuò)誤本地小數(shù)據(jù)卻正常。原因是find用遞歸實(shí)現(xiàn)如果合并順序不當(dāng)樹(shù)可能退化成一條長(zhǎng)鏈遞歸深度等于鏈長(zhǎng)。解決辦法有兩個(gè)一是把find改成迭代版本用循環(huán)一路向上找根再壓縮二是用「路徑減半」技巧在循環(huán)里每次讓parent_[x] parent_[parent_[x]]把深度砍半。我一般直接上迭代版本代碼稍長(zhǎng)但徹底免疫。5.2 現(xiàn)象單調(diào)棧結(jié)果和預(yù)期差一位原因嚴(yán)格與非嚴(yán)格比較搞混解決在函數(shù)名和注釋里寫(xiě)死現(xiàn)象是「下一個(gè)更大元素」在存在相等元素時(shí)返回了下標(biāo)而不是 -1。原因是模板里用了而不是把相等元素也當(dāng)成更大。解決辦法是在函數(shù)命名上區(qū)分比如nextGreaterStrict和nextGreaterOrEqual并在注釋第一行寫(xiě)明比較規(guī)則。這個(gè)坑我踩過(guò)不止一次后來(lái)干脆在模板庫(kù)里同時(shí)提供兩個(gè)函數(shù)調(diào)用方自己選。5.3 現(xiàn)象快速冪取模結(jié)果負(fù)數(shù)原因底數(shù)為負(fù)沒(méi)處理解決先取模再調(diào)整現(xiàn)象是fastPowMod(-2, 3, 100)返回負(fù)數(shù)。原因是 C 里負(fù)數(shù)取模結(jié)果符號(hào)跟被除數(shù)一致base % mod之后base仍是負(fù)的。解決辦法是在base % mod后加一句if (base 0) base mod;。參數(shù)上如果題目保證底數(shù)非負(fù)可以不加但模板庫(kù)應(yīng)該默認(rèn)處理因?yàn)檎{(diào)用方不一定記得。5.4 現(xiàn)象模板頭文件重復(fù)包含導(dǎo)致重定義原因沒(méi)寫(xiě) include guard 或 pragma once解決每個(gè)頭文件第一行加 pragma once現(xiàn)象是鏈接時(shí)報(bào) multiple definition。原因是兩個(gè)頭文件互相包含或者測(cè)試文件重復(fù)引入。解決辦法是每個(gè).hpp第一行寫(xiě)#pragma once這是最省事的做法。注意#pragma once不是標(biāo)準(zhǔn)但所有主流編譯器都支持模板庫(kù)場(chǎng)景下夠用。如果追求可移植性用傳統(tǒng) include guard 也行但名字要寫(xiě)全別用_DSU_H這種以下劃線(xiàn)開(kāi)頭的保留標(biāo)識(shí)符。5.5 現(xiàn)象CMake 編譯通過(guò)但運(yùn)行找不到頭文件原因include 路徑寫(xiě)成了相對(duì)路徑解決統(tǒng)一用 CMAKE_SOURCE_DIR 拼絕對(duì)路徑現(xiàn)象是cmake ..成功make時(shí)報(bào)fatal error: ds/dsu.hpp: No such file。原因是include_directories里寫(xiě)了include這種相對(duì)路徑而 CMake 的相對(duì)路徑基準(zhǔn)是當(dāng)前構(gòu)建目錄不是源碼目錄。解決辦法是統(tǒng)一用${CMAKE_SOURCE_DIR}/include拼絕對(duì)路徑。這個(gè)坑在新機(jī)器上第一次配環(huán)境時(shí)幾乎必踩記住就行。6. 讓模板庫(kù)真正省時(shí)間的兩個(gè)進(jìn)階習(xí)慣第一個(gè)習(xí)慣是給每個(gè)模板寫(xiě)「一行調(diào)用示例」放在頭文件頂部注釋里。比如dsu.hpp頂部寫(xiě)// DSU dsu(n); dsu.unite(a,b); dsu.same(a,b);。別小看這一行比賽時(shí)你腦子是熱的翻到頭文件看到調(diào)用示例比看函數(shù)簽名快得多。第二個(gè)習(xí)慣是定期做「模板瘦身」把半年沒(méi)用過(guò)的模板移到archive/目錄主目錄只留高頻的十幾個(gè)。模板庫(kù)不是越大越好越大越容易在關(guān)鍵時(shí)刻選錯(cuò)。驗(yàn)證模板庫(kù)是否合格有個(gè)很簡(jiǎn)單的標(biāo)準(zhǔn)隨機(jī)抽一道你做過(guò)的題只允許用模板庫(kù)里的代碼看能不能在 15 分鐘內(nèi)寫(xiě)完并通過(guò)。如果做不到說(shuō)明要么模板不全要么接口不順手。我自己的庫(kù)迭代了三年現(xiàn)在穩(wěn)定在 20 個(gè)頭文件左右每次比賽前跑一遍全部對(duì)拍測(cè)試通過(guò)才敢用。這個(gè)習(xí)慣幫我省下的調(diào)試時(shí)間遠(yuǎn)比攢模板花的時(shí)間多。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取