ACM 所有算法

1、ACM 所有算法數(shù)據(jù)結(jié)構(gòu) 棧，隊列，鏈表 哈希表，哈希數(shù)組 堆，優(yōu)先隊列雙端隊列可并堆左偏堆 二叉查找樹Treap伸展樹 并查集集合計數(shù)問題二分圖的識別 平衡二叉樹 二叉排序樹 線段樹一維線段樹二維線段樹 樹狀數(shù)組一維樹狀數(shù)組N維樹狀數(shù)組 字典樹 后綴數(shù)組，后綴樹 塊狀鏈表 哈夫曼樹 桶，跳躍表 Trie樹(靜態(tài)建樹、動態(tài)建樹) AC自動機(jī) LCA和RMQ問題 KMP算法圖論 基本圖算法圖廣度優(yōu)先遍歷深度優(yōu)先遍歷拓?fù)渑判蚋钸吀铧c(diǎn)強(qiáng)連通分量Tarjan算法雙連通分量強(qiáng)連通分支及其縮點(diǎn)圖的割邊和割點(diǎn)最小割模型、網(wǎng)絡(luò)流規(guī)約2-SAT問題歐拉回路哈密頓回路 最小生成樹Prim算法Kruskal算法(稀

2、疏圖)Sollin算法次小生成樹第k小生成樹最優(yōu)比例生成樹最小樹形圖最小度限制生成樹平面點(diǎn)的歐幾里德最小生成樹平面點(diǎn)的曼哈頓最小生成樹最小平衡生成樹 最短路徑有向無環(huán)圖的最短路徑-拓?fù)渑判蚍秦?fù)權(quán)值加權(quán)圖的最短路徑-Dijkstra算法(可使用二叉堆優(yōu)化)含負(fù)權(quán)值加權(quán)圖的最短路徑-Bellmanford算法含負(fù)權(quán)值加權(quán)圖的最短路徑-Spfa算法(稠密帶負(fù)權(quán)圖中SPFA的效率并不如Bellman-Ford高)全源最短路弗洛伊德算法Floyd全源最短路Johnson算法次短路徑第k短路徑差分約束系統(tǒng)平面點(diǎn)對的最短路徑(優(yōu)化)雙標(biāo)準(zhǔn)限制最短路徑 最大流增廣路-Ford-Fulkerson算法預(yù)推流Di

3、nic算法有上下界限制的最大流節(jié)點(diǎn)有限制的網(wǎng)絡(luò)流無向圖最小割-Stoer-Wagner算法有向圖和無向圖的邊不交路徑Ford-Fulkerson迭加算法含負(fù)費(fèi)用的最小費(fèi)用最大流 匹配Hungary算法最小點(diǎn)覆蓋最小路徑覆蓋最大獨(dú)立集問題二分圖最優(yōu)完備匹配Kuhn-Munkras算法不帶權(quán)二分匹配：匈牙利算法帶權(quán)二分匹配：KM算法一般圖的最大基數(shù)匹配一般圖的賦權(quán)匹配問題 拓?fù)渑判?弦圖 穩(wěn)定婚姻問題搜索 廣搜的狀態(tài)優(yōu)化利用M進(jìn)制數(shù)存儲狀態(tài)轉(zhuǎn)化為串用hash表判重按位壓縮存儲狀態(tài)雙向廣搜A*算法 深搜的優(yōu)化位運(yùn)算剪枝函數(shù)參數(shù)盡可能少層數(shù)不易過大雙向搜索或者是輪換搜索IDA*算法 記憶化搜索動態(tài)規(guī)劃

4、 四邊形不等式理論 不完全狀態(tài)記錄青蛙過河問題利用區(qū)間dp 背包類問題0-1背包，經(jīng)典問題無限背包，經(jīng)典問題判定性背包問題帶附屬關(guān)系的背包問題+ -1背包問題雙背包求最優(yōu)值構(gòu)造三角形問題帶上下界限制的背包問題(012背包) 線性的動態(tài)規(guī)劃問題積木游戲問題決斗（判定性問題）圓的最大多邊形問題統(tǒng)計單詞個數(shù)問題棋盤分割日程安排問題最小逼近問題(求出兩數(shù)之比最接近某數(shù)/兩數(shù)之和等于某數(shù)等等)方塊消除游戲(某區(qū)間可以連續(xù)消去求最大效益)資源分配問題數(shù)字三角形問題漂亮的打印郵局問題與構(gòu)造答案最高積木問題兩段連續(xù)和最大2次冪和問題N個數(shù)的最大M段子段和交叉最大數(shù)問題 判定性問題的dp(如判定整除、判定可達(dá)性

5、等)模K問題的dp特殊的模K問題，求最大(最小)模K的數(shù)變換數(shù)問題 單調(diào)性優(yōu)化的動態(tài)規(guī)劃1-SUM問題2-SUM問題序列劃分問題(單調(diào)隊列優(yōu)化) 剖分問題(多邊形剖分/石子合并/圓的剖分/乘積最大)凸多邊形的三角剖分問題乘積最大問題多邊形游戲(多邊形邊上是操作符,頂點(diǎn)有權(quán)值)石子合并(N3/N2/NLogN各種優(yōu)化) 貪心的動態(tài)規(guī)劃最優(yōu)裝載問題部分背包問題乘船問題貪心策略雙機(jī)調(diào)度問題Johnson算法 狀態(tài)dp牛仔射擊問題(博弈類)哈密頓路徑的狀態(tài)dp兩支點(diǎn)天平平衡問題一個有向圖的最接近二部圖 樹型dp完美服務(wù)器問題(每個節(jié)點(diǎn)有3種狀態(tài))小胖守皇宮問題網(wǎng)絡(luò)收費(fèi)問題樹中漫游問題樹上的博弈樹的最大

6、獨(dú)立集問題樹的最大平衡值問題構(gòu)造樹的最小環(huán)數(shù)學(xué)數(shù)論 中國剩余定理 歐拉函數(shù) 歐幾里得定理 歐幾里德輾轉(zhuǎn)相除法求GCD(最大公約數(shù)) 擴(kuò)展歐幾里得 大數(shù)分解與素數(shù)判定 佩爾方程 同余定理(大數(shù)求余) 素數(shù)測試一千萬以內(nèi)：篩選法一千萬以外：米勒測試法 連分?jǐn)?shù)逼近 因式分解 循環(huán)群生成元 素數(shù)與整除問題 進(jìn)制位. 同余模運(yùn)算組合數(shù)學(xué) 排列組合 容斥原理 遞推關(guān)系和生成函數(shù) Polya計數(shù)法Polya計數(shù)公式Burnside定理 N皇后構(gòu)造解 幻方的構(gòu)造 滿足一定條件的hamilton圈的構(gòu)造 Catalan數(shù) Stirling數(shù) 斐波拉契數(shù) 調(diào)和數(shù) 連分?jǐn)?shù) MoBius反演 偏序關(guān)系理論 加法原理和

7、乘法原理計算幾何 基本公式叉乘點(diǎn)乘常見形狀的面積、周長、體積公式坐標(biāo)離散化 線段判斷兩線段（一直線、一線段）是否相交求兩線段的交點(diǎn) 多邊形判定凸多邊形,頂點(diǎn)按順時針或逆時針給出,(不)允許相鄰邊共線判點(diǎn)在凸多邊形內(nèi)或多邊形邊上,頂點(diǎn)按順時針或逆時針給出判點(diǎn)在凸多邊形內(nèi),頂點(diǎn)按順時針或逆時針給出,在多邊形邊上返回0判點(diǎn)在任意多邊形內(nèi),頂點(diǎn)按順時針或逆時針給出判線段在任意多邊形內(nèi),頂點(diǎn)按順時針或逆時針給出,與邊界相交返回1多邊形重心多邊形切割(半平面交)掃描線算法多邊形的內(nèi)核 三角形內(nèi)心外心重心垂心費(fèi)馬點(diǎn) 圓判直線和圓相交,包括相切判線段和圓相交,包括端點(diǎn)和相切判圓和圓相交,包括相切計算圓上到點(diǎn)p最近點(diǎn),如p與圓心重合,返回p本身計算直線與圓的交點(diǎn),保證直線與圓有交點(diǎn)計算線段與圓的交點(diǎn)可用這個函數(shù)后判點(diǎn)是否在線段上計算圓與圓的交點(diǎn),保證圓與圓有交點(diǎn),圓心不重合計算兩圓的內(nèi)外公切線計算線段到圓的切點(diǎn)點(diǎn)集最小圓覆蓋 可視圖的建立 對踵點(diǎn) 經(jīng)典問題平面凸包三維凸包Delaunay剖分/Voronoi圖計算方法 二分法二分法求解單調(diào)函數(shù)相關(guān)知識用矩陣加速