ACM 所有算法

• 棧，隊列，鏈表
• 哈希表，哈希數組
• 堆，優先隊列
  雙端隊列
  可并堆
  左偏堆
• 二叉查找樹
  Treap
  伸展樹
• 并查集
  集合計數問題
  二分圖的識別
• 平衡二叉樹
• 二叉排序樹
• 線段樹
  一維線段樹
  二維線段樹
• 樹狀數組
  一維樹狀數組
  N維樹狀數組
• 字典樹
• 后綴數組，后綴樹
• 塊狀鏈表
• 哈夫曼樹
• 桶，跳躍表
• Trie樹(靜態建樹、動態建樹)
• AC自動機
• LCA和RMQ問題
• KMP算法

• 基本圖算法圖
  廣度優先遍歷
  深度優先遍歷
  拓撲排序
  割邊割點
  強連通分量
  Tarjan算法
  雙連通分量
  強連通分支及其縮點
  圖的割邊和割點
  最小割模型、網絡流規約
  2-SAT問題
  歐拉回路
  哈密頓回路
• 最小生成樹
  Prim算法
  Kruskal算法(稀疏圖)
  Sollin算法
  次小生成樹
  第k小生成樹
  最優比例生成樹
  最小樹形圖
  最小度限制生成樹
  平面點的歐幾里德最小生成樹
  平面點的曼哈頓最小生成樹
  最小平衡生成樹
• 最短路徑
  有向無環圖的最短路徑->拓撲排序
  非負權值加權圖的最短路徑->Dijkstra算法(可使用二叉堆優化)
  含負權值加權圖的最短路徑->Bellmanford算法
  含負權值加權圖的最短路徑->Spfa算法
  (稠密帶負權圖中SPFA的效率并不如Bellman-Ford高)
  全源最短路弗洛伊德算法Floyd
  全源最短路Johnson算法
  次短路徑
  第k短路徑
  差分約束系統
  平面點對的最短路徑(優化)
  雙標準限制最短路徑
• 最大流
  增廣路->Ford-Fulkerson算法
  預推流
  Dinic算法
  有上下界限制的最大流
  節點有限制的網絡流
  無向圖最小割->Stoer-Wagner算法
  有向圖和無向圖的邊不交路徑
  Ford-Fulkerson迭加算法
  含負費用的最小費用最大流
• 匹配
  Hungary算法
  最小點覆蓋
  最小路徑覆蓋
  最大獨立集問題
  二分圖最優完備匹配Kuhn-Munkras算法
  不帶權二分匹配：匈牙利算法
  帶權二分匹配：KM算法
  一般圖的最大基數匹配
  一般圖的賦權匹配問題
• 拓撲排序
• 弦圖
• 穩定婚姻問題

• 廣搜的狀態優化
  利用M進制數存儲狀態
  轉化為串用hash表判重
  按位壓縮存儲狀態
  雙向廣搜
  A*算法
• 深搜的優化
  位運算
  剪枝
  函數參數盡可能少
  層數不易過大
  雙向搜索或者是輪換搜索
  IDA*算法
• 記憶化搜索

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

數學

• 中國剩余定理
• 歐拉函數
• 歐幾里得定理
• 歐幾里德輾轉相除法求GCD(最大公約數)
• 擴展歐幾里得
• 大數分解與素數判定
• 佩爾方程
• 同余定理(大數求余)
• 素數測試
  一千萬以內：篩選法
  一千萬以外：米勒測試法
• 連分數逼近
• 因式分解
• 循環群生成元
• 素數與整除問題
• 進制位.
• 同余模運算

• 排列組合
• 容斥原理
• 遞推關系和生成函數
• Polya計數法
  Polya計數公式
  Burnside定理
• N皇后構造解
• 幻方的構造
• 滿足一定條件的hamilton圈的構造
• Catalan數
• Stirling數
• 斐波拉契數
• 調和數
• 連分數
• MoBius反演
• 偏序關系理論
• 加法原理和乘法原理

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

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

• 極大極小過程
• Nim問題