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