ACM主要算法介紹

（以下是自己覺(jué)得比較好的算法學(xué)習(xí)的博客鏈接，自己做了部分順序和分類(lèi)調(diào)整）（以下算法分類(lèi)來(lái)自于：ACM主要算法）

后續(xù)將繼續(xù)補(bǔ)充

數(shù)據(jù)結(jié)構(gòu)

• 棧，隊(duì)列，鏈表

• 哈希表，哈希數(shù)組

• 堆，優(yōu)先隊(duì)列
  雙端隊(duì)列
  可并堆（左偏樹(shù)）

• 二叉查找樹(shù)
  Treap
  伸展樹(shù)

• 并查集
  集合計(jì)數(shù)問(wèn)題
  二分圖的識(shí)別

• 平衡二叉樹(shù)

  紅黑樹(shù)（快速查詢最值）

• 二叉排序樹(shù)

• 線段樹(shù)（適合求區(qū)間和）
  一維線段樹(shù)
  二維線段樹(shù)

• 樹(shù)狀數(shù)組（適用于查詢區(qū)間和單點(diǎn)修改）
  一維樹(shù)狀數(shù)組（樹(shù)狀數(shù)組區(qū)間求和與區(qū)間最值）

  N維樹(shù)狀數(shù)組

• 字典樹(shù)（前綴樹(shù)）

• 后綴數(shù)組，后綴樹(shù)

• 塊狀鏈表

• 哈夫曼樹(shù)

• 桶，跳躍表

• Trie樹(shù)(靜態(tài)建樹(shù)、動(dòng)態(tài)建樹(shù))

• AC自動(dòng)機(jī)

• LCA和RMQ問(wèn)題

• 幾種常見(jiàn)的字符串匹配算法

  樸素算法

  Rabin-Karp算法

  KMP算法（AC自動(dòng)機(jī)的基礎(chǔ)）

  Boyer-Moore算法

  Sunday算法（強(qiáng)烈推薦）

圖論

• 基本圖算法圖
  廣度優(yōu)先遍歷
  深度優(yōu)先遍歷
  拓?fù)渑判?br> 割邊割點(diǎn)
  強(qiáng)連通分量
  Tarjan算法
  雙連通分量
  強(qiáng)連通分支及其縮點(diǎn)
  圖的割邊和割點(diǎn)
  最小割模型、網(wǎng)絡(luò)流規(guī)約
  2-SAT問(wèn)題
  歐拉回路
  哈密頓回路
• 最小生成樹(shù)
  Prim算法
  Kruskal算法(稀疏圖)
  Sollin算法
  次小生成樹(shù)
  第k小生成樹(shù)
  最優(yōu)比例生成樹(shù)
  最小樹(shù)形圖
  最小度限制生成樹(shù)
  平面點(diǎn)的歐幾里德最小生成樹(shù)
  平面點(diǎn)的曼哈頓最小生成樹(shù)
  最小平衡生成樹(shù)
• 最短路徑
  有向無(wú)環(huán)圖的最短路徑->拓?fù)渑判?br> 非負(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)對(duì)的最短路徑(優(yōu)化)
  雙標(biāo)準(zhǔn)限制最短路徑
• 最大流
  增廣路->Ford-Fulkerson算法
  預(yù)推流
  Dinic算法
  有上下界限制的最大流
  節(jié)點(diǎn)有限制的網(wǎng)絡(luò)流
  無(wú)向圖最小割->Stoer-Wagner算法
  有向圖和無(wú)向圖的邊不交路徑
  Ford-Fulkerson迭加算法
  含負(fù)費(fèi)用的最小費(fèi)用最大流
• 匹配
  Hungary算法
  最小點(diǎn)覆蓋
  最小路徑覆蓋
  最大獨(dú)立集問(wèn)題
  二分圖最優(yōu)完備匹配Kuhn-Munkras算法
  不帶權(quán)二分匹配：匈牙利算法
  帶權(quán)二分匹配：KM算法
  一般圖的最大基數(shù)匹配
  一般圖的賦權(quán)匹配問(wèn)題
• 拓?fù)渑判?/li>
• 弦圖
• 穩(wěn)定婚姻問(wèn)題

搜索

• 廣搜的狀態(tài)優(yōu)化
  利用M進(jìn)制數(shù)存儲(chǔ)狀態(tài)
  轉(zhuǎn)化為串用hash表判重
  按位壓縮存儲(chǔ)狀態(tài)
  雙向廣搜
  A*算法
• 深搜的優(yōu)化
  位運(yùn)算
  剪枝
  函數(shù)參數(shù)盡可能少
  層數(shù)不易過(guò)大
  雙向搜索或者是輪換搜索
  IDA*算法
• 記憶化搜索

動(dòng)態(tài)規(guī)劃

• 四邊形不等式理論
• 不完全狀態(tài)記錄
  青蛙過(guò)河問(wèn)題
  利用區(qū)間dp
• 背包類(lèi)問(wèn)題
  0-1背包，經(jīng)典問(wèn)題
  無(wú)限背包，經(jīng)典問(wèn)題
  判定性背包問(wèn)題
  帶附屬關(guān)系的背包問(wèn)題
  + -1背包問(wèn)題
  雙背包求最優(yōu)值
  構(gòu)造三角形問(wèn)題
  帶上下界限制的背包問(wèn)題(012背包)
• 線性的動(dòng)態(tài)規(guī)劃問(wèn)題
  積木游戲問(wèn)題
  決斗（判定性問(wèn)題）
  圓的最大多邊形問(wèn)題
  統(tǒng)計(jì)單詞個(gè)數(shù)問(wèn)題
  棋盤(pán)分割
  日程安排問(wèn)題
  最小逼近問(wèn)題(求出兩數(shù)之比最接近某數(shù)/兩數(shù)之和等于某數(shù)等等)
  方塊消除游戲(某區(qū)間可以連續(xù)消去求最大效益)
  資源分配問(wèn)題
  數(shù)字三角形問(wèn)題
  漂亮的打印
  郵局問(wèn)題與構(gòu)造答案
  最高積木問(wèn)題
  兩段連續(xù)和最大
  2次冪和問(wèn)題
  N個(gè)數(shù)的最大M段子段和
  交叉最大數(shù)問(wèn)題
• 判定性問(wèn)題的dp(如判定整除、判定可達(dá)性等)
  模K問(wèn)題的dp
  特殊的模K問(wèn)題，求最大(最小)模K的數(shù)
  變換數(shù)問(wèn)題
• 單調(diào)性優(yōu)化的動(dòng)態(tài)規(guī)劃
  1-SUM問(wèn)題
  2-SUM問(wèn)題
  序列劃分問(wèn)題(單調(diào)隊(duì)列優(yōu)化)
• 剖分問(wèn)題(多邊形剖分/石子合并/圓的剖分/乘積最大)
  凸多邊形的三角剖分問(wèn)題
  乘積最大問(wèn)題
  多邊形游戲(多邊形邊上是操作符,頂點(diǎn)有權(quán)值)
  石子合并(N^3/N2/NLogN各種優(yōu)化)
• 貪心的動(dòng)態(tài)規(guī)劃
  最優(yōu)裝載問(wèn)題
  部分背包問(wèn)題
  乘船問(wèn)題
  貪心策略
  雙機(jī)調(diào)度問(wèn)題Johnson算法
• 狀態(tài)dp
  牛仔射擊問(wèn)題(博弈類(lèi))
  哈密頓路徑的狀態(tài)dp
  兩支點(diǎn)天平平衡問(wèn)題
  一個(gè)有向圖的最接近二部圖
• 樹(shù)型dp
  完美服務(wù)器問(wèn)題(每個(gè)節(jié)點(diǎn)有3種狀態(tài))
  小胖守皇宮問(wèn)題
  網(wǎng)絡(luò)收費(fèi)問(wèn)題
  樹(shù)中漫游問(wèn)題
  樹(shù)上的博弈
  樹(shù)的最大獨(dú)立集問(wèn)題
  樹(shù)的最大平衡值問(wèn)題
  構(gòu)造樹(shù)的最小環(huán)

數(shù)學(xué)

1. 數(shù)論

   • 中國(guó)剩余定理
   • 歐拉函數(shù)
   • 歐幾里得定理
   • 歐幾里德輾轉(zhuǎn)相除法求GCD(最大公約數(shù))
   • 擴(kuò)展歐幾里得
   • 大數(shù)分解與素?cái)?shù)判定
   • 佩爾方程
   • 同余定理(大數(shù)求余)
   • 素?cái)?shù)測(cè)試
     一千萬(wàn)以內(nèi)：篩選法
     一千萬(wàn)以外：米勒測(cè)試法
   • 連分?jǐn)?shù)逼近
   • 因式分解
   • 循環(huán)群生成元
   • 素?cái)?shù)與整除問(wèn)題
   • 進(jìn)制位.
   • 同余模運(yùn)算

2. 組合數(shù)學(xué)

   • 排列組合
   • 容斥原理
   • 遞推關(guān)系和生成函數(shù)
   • Polya計(jì)數(shù)法
     Polya計(jì)數(shù)公式
     Burnside定理
   • N皇后構(gòu)造解
   • 幻方的構(gòu)造
   • 滿足一定條件的hamilton圈的構(gòu)造
   • Catalan數(shù)
   • Stirling數(shù)
   • 斐波拉契數(shù)
   • 調(diào)和數(shù)
   • 連分?jǐn)?shù)
   • MoBius反演
   • 偏序關(guān)系理論
   • 加法原理和乘法原理

3. 計(jì)算幾何

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

4. 計(jì)算方法

   • 二分法
     二分法求解單調(diào)函數(shù)相關(guān)知識(shí)
     用矩陣加速的計(jì)算
   • 迭代法
   • 三分法
   • 解線性方程組
     LUP分解
     高斯消元
   • 解模線性方程組
   • 定積分計(jì)算
   • 多項(xiàng)式求根
   • 周期性方程
   • 線性規(guī)劃
   • 快速傅立葉變換
   • 隨機(jī)算法
   • 0/1分?jǐn)?shù)規(guī)劃
   • 三分法求解單峰(單谷)的極值
   • 迭代逼近
   • 矩陣法

5. 博弈論

   • 極大極小過(guò)程

   • Nim問(wèn)題