小編在大一的時候，參加了學校中的ACM社團，那時候啥都不知道，對一切都充滿了好奇，不過待了一年半就沒有繼續，原因挺多的，在這一年半中，學了許多聽都沒聽過的算法，也不能說徹底了解，隻能說“愛過”。

通過這一年半ACM，感覺 智商上的差距光靠努力是彌補不回來的，開個玩笑，努力總比不努力強一萬倍。

ACM的确很鍛煉思維，今天就在網上找了一下有關ACM的一些算法，來紀念我這一年半的經曆。

數據結構

• 棧，隊列，鍊表

• 哈希表，哈希數組

• 堆，優先隊列

  雙端隊列

  可并堆

  左偏堆

• 二叉查找樹

  Treap

  伸展樹

• 并查集

  集合計數問題

  二分圖的識别

• 平衡二叉樹

• 二叉排序樹

• 線段樹

• 基本圖算法圖

  廣度優先遍曆

  深度優先遍曆

  拓撲排序

  割邊割點

  強連通分量

  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問題

在網上找的，大多都沒見過，有能力的可以學習一下。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!