力扣算法Algorithm競賽模板庫（codeforces-go）：含了算法競賽中常用的數據結構和算法實現，助力開發者更高效地解決問題

1.算法Algorithm競賽模板庫（codeforces-go）

算法競賽模板庫，為算法競賽愛好者提供了一系列精心設計的算法模板。這個庫包含了算法競賽中常用的數據結構和算法實現，助力開發者更高效地解決問題

在這里插入圖片描述

一個算法模板應當涵蓋以下幾點：

對該算法的基本介紹（核心思想、復雜度等）
參考鏈接或書籍章節（講的比較好的資料）
模板代碼（可以包含一些注釋、使用說明）
模板補充內容（常見題型中的額外代碼、建模技巧等）
相關題目鏈接（模板題、經典題、思維轉換題等）

1.1 算法目錄

不了解 Go？快速入門教程

集合論與位運算

1.1.1 數據結構

單調棧 monotone_stack.go
單調隊列 monotone_queue.go
- 二維單調隊列
雙端隊列 deque.go
堆（優先隊列）heap.go
- 支持修改、刪除指定元素的堆
- 懶刪除堆
- 對頂維
- 前綴中位數
- 滑動窗口前 k 小元素和
并查集 union_find.go
- 點權并查集
- 邊權并查集（種類并查集）
- 可持久化并查集
- 回滾并查集 & 動態圖連通性
稀疏表（ST 表）sparse_table.go
樹狀數組 fenwick_tree.go
- 差分樹狀數組（支持區間加、區間求和）
- 樹套樹 & 三維偏序
線段樹 segment_tree.go
- 線段樹二分
- 延遲標記（懶標記）
- 動態開點
- 線段樹合并
- 線段樹分裂
- 持久化（主席樹）
0-1 線段樹 segment_tree01.go
左偏樹（可并堆）leftist_tree.go
笛卡爾樹 cartesian_tree.go
二叉搜索樹公共方法 bst.go
Treap treap.go
- 前 k 小元素和
伸展樹 splay.go
動態樹 LCT link_cut_tree.go
紅黑樹 red_black_tree.go
替罪羊樹 scapegoat_tree.go
k-d 樹 kd_tree.go
珂朵莉樹（ODT）
- 數組版 odt.go
- 平衡樹版 odt_bst.go
根號分治、分塊 sqrt_decomposition.go
莫隊算法 mo.go
- 普通莫隊
- 帶修莫隊
- 回滾莫隊
- 樹上莫隊

1.1.2 字符串 strings.go

字符串哈希
KMP
- pi 函數
- border
- 最小循環節
- fail 樹（失配樹 / border 樹）
擴展 KMP（Z algorithm）
最小表示法
最長回文子串
- Manacher 算法
回文自動機（回文樹，PAM）pam.go
后綴數組（SA）
后綴自動機（SAM）sam.go
字典樹 trie.go
- 可持久化字典樹
0-1 字典樹 trie01.go
- 最大異或和
- 第 k 大異或和
- 刪除元素
- 可持久化 0-1 字典樹
- 【研究】0-1 字典樹上最多有多少個節點
AC 自動機 acam.go

1.1.3 數學

數論 math.go
- 輾轉相除法（最大公因數 GCD）
- 類歐幾里得算法 ∑?(ai+b)/m?
- Pollard-Rho 質因數分解算法
- 埃氏篩（埃拉托斯特尼篩法）
- 歐拉篩（線性篩）
- 歐拉函數
- 原根
- 擴展 GCD
  - 二元一次不定方程
- 逆元
  - 線性求逆元
- 中國剩余定理（CRT）
  - 擴展中國剩余定理
- 離散對數
- 大步小步算法（BSGS）
  - 擴展大步小步算法
- 二次剩余
- Jacobi 符號
- N 次剩余
- 盧卡斯定理
  - 擴展盧卡斯定理
- 卡特蘭數
- 默慈金數
- 那羅延數
- 斯特林數
  - 第一類斯特林數（輪換）
  - 第二類斯特林數（子集）
- 貝爾數
- 歐拉數
- 數論分塊（整除分塊）
- 莫比烏斯函數
- 莫比烏斯反演
  - 互質計數問題
  - GCD 求和問題
- 杜教篩
組合數學 math_comb.go
- 常見模型
- 常用恒等式
- 容斥原理
快速傅里葉變換 FFT math_fft.go
快速數論變換 NTT math_ntt.go
- 包含多項式全家桶（求逆、開方等等）
快速沃爾什變換 FWT math_fwt.go
連分數、佩爾方程 math_continued_fraction.go
線性代數 math_matrix.go
- 矩陣相關運算
- 高斯消元
- 行列式
- 線性基
數值分析 math_numerical_analysis.go
- 自適應辛普森積分
- 拉格朗日插值
計算幾何 geometry.go
- 線與點
- 線與線
- 圓與點
  - 最小圓覆蓋
    - Welzl 隨機增量法
  - 固定半徑覆蓋最多點
- 圓與線
- 圓與圓
- 圓與矩形
- 最近點對
- 多邊形與點
  - 判斷點在凸多邊形內 O(log n)
  - 判斷點在任意多邊形內
    - 轉角法（統計繞數）
- 凸包
- 最遠點對
  - 旋轉卡殼
- 半平面交
博弈論 games.go
- SG 函數

1.1.4 動態規劃 dp.go

背包
- 0-1 背包
- 完全背包
- 多重背包
  - 二進制優化
  - 單調隊列優化
  - 同余前綴和優化（求方案數）
- 分組背包
- 樹上背包（依賴背包）
- 字典序最小方案
線性 DP
- 最大子段和
- LCS
- LPS
- LIS
  - 狄爾沃斯定理
- LCIS
- 長度為 m 的 LIS 個數
- 本質不同子序列個數
區間 DP
環形 DP
博弈 DP
概率 DP
期望 DP
狀壓 DP
- 全排列 DP
- 旅行商問題（TSP）
- 子集 DP
- 高維前綴和（SOS DP）
- 插頭 DP
數位 DP
- 記憶化搜索（同時跑上下界）
倍增優化 DP
斜率優化 DP（CHT）
WQS 二分優化 DP（凸優化 DP / 帶權二分）
樹形 DP
- 樹的直徑個數
- 在任一直徑上的節點個數
- 樹上最大獨立集
- 樹上最小頂點覆蓋
- 樹上最小支配集
- 樹上最大匹配
- 換根 DP（二次掃描法）

1.1.5 圖論 graph.go

鏈式前向星
DFS 常用技巧
BFS 常用技巧
歐拉回路和歐拉路徑
- 無向圖
- 有向圖
割點
割邊（橋）
雙連通分量（BCC）
- v-BCC
- e-BCC
仙人掌 & 圓方樹
最短路
- Dijkstra
- SPFA（隊列優化的 Bellman-Ford）
  - 差分約束系統
- Floyd-Warshall
- Johnson
- 0-1 BFS（雙端隊列 BFS）
- 字典序最小最短路
- 同余最短路
最小環
最小斯坦納樹
最小生成樹（MST）
- Kruskal
- Prim
單度限制最小生成樹
次小生成樹
曼哈頓距離最小生成樹
最小差值生成樹
最小樹形圖
- 朱劉算法
二分圖判定（染色）
二分圖找奇環
二分圖最大匹配
- 匈牙利算法
帶權二分圖最大完美匹配
- Kuhn–Munkres 算法
拓撲排序
強連通分量（SCC）
- Kosaraju
- Tarjan
2-SAT
基環樹
最大流
- Dinic
- ISAP
- HLPP
最小費用最大流
- SPFA
- Dijkstra
三元環計數
四元環計數
樹上問題 graph_tree.go
- 直徑
- 重心
- 點分治
- 點分樹
- 最近公共祖先（LCA）
  - 倍增
  - ST 表
  - Tarjan
  - 樹上差分
  - 虛樹
- 重鏈剖分（HLD）
- 長鏈剖分
- 樹上啟發式合并（small to large）
  - 按大小合并
  - 輕重兒子合并
- 樹分塊
- Prufer 序列

1.1.6 其他

位運算筆記 bits.go
- bitset
- 區間位運算 trick（含 GCD）
二分三分 sort.go
- 二分答案
- 0-1 分數規劃
- 整體二分
搜索 search.go
- 枚舉排列
- 枚舉組合
- 生成下一個排列
- 康托展開
- 逆康托展開
- 枚舉子集
  - Gosper’s Hack
- 折半枚舉（Meet in the middle）
  - 超大背包問題
隨機算法 rand.go
- 模擬退火
基礎算法 common.go
- 算法思路整理
- 滑動窗口
- 前綴和
- 二維前綴和
- 二維差分
- 離散化
雜項 misc.go
快速輸入輸出模板 io.go

1.2 如何選擇題目 How to Choose Problems

1.2.1 Rating < 2100

這一階段主要目標是提高對問題的觀察能力。做構造題可以針對性地訓練這一點。

選擇難度在自己 rating 到 rating+200 范圍內的構造題 (tag: constructive algorithms)，按照過題人數降序做題，比如 [1700,1900] 區間的就是下面這個鏈接：

https://codeforces.com/problemset?order=BY_SOLVED_DESC&tags=constructive+algorithms%2C1700-1900

通過大量的構造題訓練，提高觀察能力，快速找到切題入口。具體見我在知乎上的這篇回答。

1.2.2 Rating >= 2100（個人訓練用，僅供參考）

見識更高的山、更廣的海。

按人數從高到低，做 2200+ 的題目。建議不設置難度上限！由于按人數排序，難度分不會太高，不設上限可以避免錯過高分好題。

構造題 2200+：鍛煉手玩能力。
DP 2200+：幾乎每場都有 DP。
數學綜合：數論、組合數學、概率期望等 2200+：包含 6 個 tag。
圖論綜合：圖論+樹上問題 2200+：包含 7 個 tag。
字符串 2200+：數據結構題不好篩選，可以找樹狀數組/線段樹的題單，這里只單獨篩選字符串的題。
交互 2200+：偶爾做做，了解一些解題套路。
博弈 2000+：也適合鍛煉手玩。由于題目比較少，從 2000 開始篩選。

1.3 測試及對拍 Testing

編寫一個 run(io.Reader, io.Writer) 函數來處理輸入輸出。這樣寫的理由是：

在 main 中調用 run(os.Stdin, os.Stdout) 來執行代碼；
測試時，將測試數據轉換成 strings.Reader 當作輸入，并用一個 strings.Builder 來接收輸出，將這二者傳入 run 中，然后就能比較輸出與答案了；
對拍時需要實現一個暴力算法 runAC，參數和 run 一樣。通過隨機數據生成器來生成數據，分別傳入 runAC 和 run，通過比對各自的輸出，來檢查 run 中的問題。

具體可以見 Codeforces 代碼倉庫 main，所有非交互題的代碼及其對應測試全部按照上述框架實現。

例如：1439C_test.go

交互題的寫法要復雜一些，需要把涉及輸入輸出的地方抽象成接口，詳見 interactive_problem。

2. 學習資料及題目 Resources

2.1 常見資料收集

注：由于入門經典上選了很多區域賽的題，一部分題目可以在 GYM 上找到，這樣可以就可以用 Go 編程提交了。

算法競賽入門經典（第二版）

算法競賽入門經典訓練指南

算法競賽入門經典訓練指南（升級版）

算法競賽進階指南

算法競賽入門到進階

《算法競賽》配套題單

OI Public Library（含國家隊論文）

算法競賽 (ICPC, OI, etc) 論文，課件，文檔，筆記等

算法競賽課件分享 by hzwer

算法第四版 Java 源碼

數據結構和算法動態可視化

OI Wiki

CP-Algorithms

The Ultimate Topic List (with Resources, Problems and Templates)

洛谷日報

All the good tutorials found for Competitive Programming

Codeforces Problem Topics

The Ultimate Topic List(with Tutorials, Problems, and Templates)

GeeksforGeeks 上的算法合集

Pepcy 模板

F0RE1GNERS 模板

https://github.com/hh2048/XCPC 含 jiangly 模板

https://www.cnblogs.com/alex-wei/p/contents.html

【模板整合計劃】目錄

算法學習筆記（目錄）

洛谷模板題（建議按難度篩選）

能力全面提升綜合題單

Luogu Problem List

洛谷原試煉場

Links of ICPC/CCPC Contests from China

AtCoder 題目分類

2.2 AtCoder 版《挑戰程序設計競賽》

AtCoder 版！蟻本 (初級編)

AtCoder 版！蟻本 (中級編)

AtCoder 版！蟻本 (上級編)

AtCoder 版！蟻本 (発展的トピック編)

2.3 待整理

【雜文】記一些有用的神奇網站

偶然在 GitHub 上發現的超長列表

算法競賽訓練中較難的部分

算法競賽中可能不太會遇到的論文題

[雜談]OI/ACM中冷門算法

Things I don’t know

[meme] If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

https://blog.csdn.net/calabash_boy/article/details/79973483

https://github.com/zimpha/algorithmic-library

https://www.luogu.com.cn/blog/command-block/blog-suo-yin-zhi-ding-post

https://wcysai.github.io/

https://www.luogu.com.cn/blog/Troverld/index

C++ @cache