ACM主要算法介紹
（以下是自己覺得比較好的算法學習的博客鏈接，自己做了部分順序和分類調(diào)整）（以下算法分類來自于：ACM主要算法）
后續(xù)將繼續(xù)補充
數(shù)據(jù)結構
棧溉痢，隊列僻造，鏈表
堆孩饼，優(yōu)先隊列
雙端隊列
可并堆（左偏樹）并查集
集合計數(shù)問題
二分圖的識別-
紅黑樹（快速查詢最值）
-
樹狀數(shù)組（適用于查詢區(qū)間和單點修改）
一維樹狀數(shù)組（樹狀數(shù)組區(qū)間求和與區(qū)間最值）N維樹狀數(shù)組
字典樹（前綴樹）
后綴數(shù)組髓削，后綴樹
桶，跳躍表
-
樸素算法
Rabin-Karp算法
KMP算法（AC自動機的基礎）
Boyer-Moore算法
Sunday算法（強烈推薦）
圖論
- 基本圖算法圖
廣度優(yōu)先遍歷
深度優(yōu)先遍歷
拓撲排序
割邊割點
強連通分量
Tarjan算法
雙連通分量
強連通分支及其縮點
圖的割邊和割點
最小割模型立膛、網(wǎng)絡流規(guī)約
2-SAT問題
歐拉回路
哈密頓回路 - 最小生成樹
Prim算法
Kruskal算法(稀疏圖)
Sollin算法
次小生成樹
第k小生成樹
最優(yōu)比例生成樹
最小樹形圖
最小度限制生成樹
平面點的歐幾里德最小生成樹
平面點的曼哈頓最小生成樹
最小平衡生成樹 - 最短路徑
有向無環(huán)圖的最短路徑->拓撲排序
非負權值加權圖的最短路徑->Dijkstra算法(可使用二叉堆優(yōu)化)
含負權值加權圖的最短路徑->Bellmanford算法
含負權值加權圖的最短路徑->Spfa算法
(稠密帶負權圖中SPFA的效率并不如Bellman-Ford高)
全源最短路弗洛伊德算法Floyd
全源最短路Johnson算法
次短路徑
第k短路徑
差分約束系統(tǒng)
平面點對的最短路徑(優(yōu)化)
雙標準限制最短路徑 - 最大流
增廣路->Ford-Fulkerson算法
預推流
Dinic算法
有上下界限制的最大流
節(jié)點有限制的網(wǎng)絡流
無向圖最小割->Stoer-Wagner算法
有向圖和無向圖的邊不交路徑
Ford-Fulkerson迭加算法
含負費用的最小費用最大流 - 匹配
Hungary算法
最小點覆蓋
最小路徑覆蓋
最大獨立集問題
二分圖最優(yōu)完備匹配Kuhn-Munkras算法
不帶權二分匹配：匈牙利算法
帶權二分匹配：KM算法
一般圖的最大基數(shù)匹配
一般圖的賦權匹配問題 - 拓撲排序
- 弦圖
- 穩(wěn)定婚姻問題
搜索
- 廣搜的狀態(tài)優(yōu)化
利用M進制數(shù)存儲狀態(tài)
轉(zhuǎn)化為串用hash表判重
按位壓縮存儲狀態(tài)
雙向廣搜
A*算法 - 深搜的優(yōu)化
位運算
剪枝
函數(shù)參數(shù)盡可能少
層數(shù)不易過大
雙向搜索或者是輪換搜索
IDA*算法 - 記憶化搜索
動態(tài)規(guī)劃
- 四邊形不等式理論
- 不完全狀態(tài)記錄
青蛙過河問題
利用區(qū)間dp - 背包類問題
0-1背包，經(jīng)典問題
無限背包梯码，經(jīng)典問題
判定性背包問題
帶附屬關系的背包問題
+ -1背包問題
雙背包求最優(yōu)值
構造三角形問題
帶上下界限制的背包問題(012背包) - 線性的動態(tài)規(guī)劃問題
積木游戲問題
決斗（判定性問題）
圓的最大多邊形問題
統(tǒng)計單詞個數(shù)問題
棋盤分割
日程安排問題
最小逼近問題(求出兩數(shù)之比最接近某數(shù)/兩數(shù)之和等于某數(shù)等等)
方塊消除游戲(某區(qū)間可以連續(xù)消去求最大效益)
資源分配問題
數(shù)字三角形問題
漂亮的打印
郵局問題與構造答案
最高積木問題
兩段連續(xù)和最大
2次冪和問題
N個數(shù)的最大M段子段和
交叉最大數(shù)問題 - 判定性問題的dp(如判定整除宝泵、判定可達性等)
模K問題的dp
特殊的模K問題，求最大(最小)模K的數(shù)
變換數(shù)問題 - 單調(diào)性優(yōu)化的動態(tài)規(guī)劃
1-SUM問題
2-SUM問題
序列劃分問題(單調(diào)隊列優(yōu)化) - 剖分問題(多邊形剖分/石子合并/圓的剖分/乘積最大)
凸多邊形的三角剖分問題
乘積最大問題
多邊形游戲(多邊形邊上是操作符,頂點有權值)
石子合并(N3/N2/NLogN各種優(yōu)化) - 貪心的動態(tài)規(guī)劃
最優(yōu)裝載問題
部分背包問題
乘船問題
貪心策略
雙機調(diào)度問題Johnson算法 - 狀態(tài)dp
牛仔射擊問題(博弈類)
哈密頓路徑的狀態(tài)dp
兩支點天平平衡問題
一個有向圖的最接近二部圖 - 樹型dp
完美服務器問題(每個節(jié)點有3種狀態(tài))
小胖守皇宮問題
網(wǎng)絡收費問題
樹中漫游問題
樹上的博弈
樹的最大獨立集問題
樹的最大平衡值問題
構造樹的最小環(huán)
數(shù)學
-
數(shù)論
- 中國剩余定理
- 歐拉函數(shù)
- 歐幾里得定理
- 歐幾里德輾轉(zhuǎn)相除法求GCD(最大公約數(shù))
- 擴展歐幾里得
- 大數(shù)分解與素數(shù)判定
- 佩爾方程
- 同余定理(大數(shù)求余)
- 素數(shù)測試
一千萬以內(nèi)：篩選法
一千萬以外：米勒測試法 - 連分數(shù)逼近
- 因式分解
- 循環(huán)群生成元
- 素數(shù)與整除問題
- 進制位.
- 同余模運算
-
組合數(shù)學
- 排列組合
- 容斥原理
- 遞推關系和生成函數(shù)
- Polya計數(shù)法
Polya計數(shù)公式
Burnside定理 - N皇后構造解
- 幻方的構造
- 滿足一定條件的hamilton圈的構造
- Catalan數(shù)
- Stirling數(shù)
- 斐波拉契數(shù)
- 調(diào)和數(shù)
- 連分數(shù)
- MoBius反演
- 偏序關系理論
- 加法原理和乘法原理
-
計算幾何
- 基本公式
叉乘
點乘
常見形狀的面積轩娶、周長儿奶、體積公式
坐標離散化 - 線段
判斷兩線段（一直線、一線段）是否相交
求兩線段的交點 - 多邊形
判定凸多邊形,頂點按順時針或逆時針給出,(不)允許相鄰邊共線
判點在凸多邊形內(nèi)或多邊形邊上,頂點按順時針或逆時針給出
判點在凸多邊形內(nèi),頂點按順時針或逆時針給出,在多邊形邊上返回0
判點在任意多邊形內(nèi),頂點按順時針或逆時針給出
判線段在任意多邊形內(nèi),頂點按順時針或逆時針給出,與邊界相交返回1
多邊形重心
多邊形切割(半平面交)
掃描線算法
多邊形的內(nèi)核 - 三角形
內(nèi)心
外心
重心
垂心
費馬點 - 圓
判直線和圓相交,包括相切
判線段和圓相交,包括端點和相切
判圓和圓相交,包括相切
計算圓上到點p最近點,如p與圓心重合,返回p本身
計算直線與圓的交點,保證直線與圓有交點
計算線段與圓的交點可用這個函數(shù)后判點是否在線段上
計算圓與圓的交點,保證圓與圓有交點,圓心不重合
計算兩圓的內(nèi)外公切線
計算線段到圓的切點
點集最小圓覆蓋 - 可視圖的建立
- 對踵點
- 經(jīng)典問題
平面凸包
三維凸包
Delaunay剖分和Voronoi圖
- 基本公式
-
計算方法
- 二分法
二分法求解單調(diào)函數(shù)相關知識
用矩陣加速的計算 - 迭代法
- 三分法
- 解線性方程組
LUP分解
高斯消元 - 解模線性方程組
- 定積分計算
- 多項式求根
- 周期性方程
- 線性規(guī)劃
- 快速傅立葉變換
- 隨機算法
- 0/1分數(shù)規(guī)劃
- 三分法求解單峰(單谷)的極值
- 迭代逼近
- 矩陣法
- 二分法
-
博弈論
極大極小過程
Nim問題
