ACM 中常用的演算法有哪些？

11-25

感謝邀請。
網路上流傳的答案有很多，估計提問者也曾經去網上搜過。所以根據自己微薄的經驗提點看法。
我ACM初期是訓練編碼能力，以水題為主（就是沒有任何演算法，自己靠動腦筋能夠實現的），這種題目特點是麻煩，但是不難，30-50道題目就可以了。
然後可以接觸一下基礎的演算法，我感覺搜索方向的比較不錯，可以解決很多問題，深搜，廣搜，然後各種剪枝能力的鍛煉。
搜索感覺不錯了就可以去看看貪心，圖論，和動態規劃方向的了。圖論有最短路徑，最小生成樹，網路流，拓撲排序等等很多，動態規劃先去書上看經典例子，最長公共子序列等。各種變形的題目。
數學是ACM中極具殺傷力的武器，我一向很羨慕數學好的隊友，精力有限自己數學方面的演算法只能說入門。這方面經典的數論，組合數學方面的比較多，計算幾何是很重要的，經典模型要熟悉，最近點對，二維三維，凸包以及各種應用。
數據結構方面的就比較多了，基礎的堆，棧，隊列，並查集，二叉查找樹，紅黑樹，trie樹，hash表等等。
用C++參賽的話STL要熟悉，有時候很有幫助，裡面的queue,list,map,stack等。
ACM到後來演算法就成了工具，不斷的靠自己意淫一個新的解法來解決問題是最開心的事情了。我們學校ACM一直是一屆帶一屆的，老師只提供經濟上的援助,上面的內容是我在大三當隊長時教給大一的新隊員的入門內容，再深的就靠每個人自己發掘了。

【轉自網路】----谷歌一下或者百度百度，有很多豐富的答案
一位高手對我的建議：

一般要做到50行以內的程序不用調試、100行以內的二分鐘內調試成功.acm主要是考演算法的
，主要時間是花在思考演算法上，不是花在寫程序與debug上。
下面給個計劃你練練：

第一階段：
練經典常用演算法，下面的每個演算法給我打上十到二十遍，同時自己精簡代碼，
因為太常用，所以要練到寫時不用想，10-15分鐘內打完，甚至關掉顯示器都可以把程序打
出來.
1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成樹(先寫個prim,kruscal要用並查集，不好寫)
3.大數（高精度）加減乘除
4.二分查找.
(代碼可在五行以內)
5.叉乘、判線段相交、然後寫個凸包.
6.BFS、DFS,同時熟練hash表(要熟，要靈活,代碼要簡)
7.數學上的有：輾轉相除（兩行內），線段交點、多角形面積公式.
8.
調用系統的qsort, 技巧很多，慢慢掌握.
9. 任意進位間的轉換

第二階段：
練習複雜一點，但也較常用的演算法。
如：
1. 二分圖匹配（匈牙利），最小路徑覆蓋
2.
網路流，最小費用流。
3. 線段樹.
4. 並查集。
5.
熟悉動態規劃的各個典型：LCS、最長遞增子串、三角剖分、記憶化dp
6.博弈類演算法。博弈樹，二進位法等。
7.最大團，最大獨立集。
8.判斷點在多邊形內。
9.
差分約束系統.
10. 雙向廣度搜索、A*演算法，最小耗散優先.

第三階段：
前兩個階段是打基礎，第三階段是鍛煉在比賽中可以快速建立模型、想新演算法
。這就要平時多做做綜合的題型了。
1.
把oibh上的論文看看（大概幾百篇的，我只看了一點點，呵呵）。
2.
平時掃掃zoj上的難題啦，別老做那些不用想的題.(中大acm的版主經常說我挑簡單的來
做:-P )
3.
多參加網上的比賽，感受一下比賽的氣氛，評估自己的實力.
4. 一道題不要過了就算，問一下人，有更好的演算法也打一下。
5. 做過的題要記好

以下內容摘自我手裡的某文檔,非本人原創
=============================================================================
ACMer必備知識（任重而道遠......）

圖論

路徑問題
0/1邊權最短路徑
BFS
非負邊權最短路徑（Dijkstra）
可以用Dijkstra解決問題的特徵
負邊權最短路徑
Bellman-Ford
Bellman-Ford的Yen-氏優化
差分約束系統
Floyd
廣義路徑問題
傳遞閉包
極小極大距離 / 極大極小距離
Euler Path / Tour
圈套圈演算法
混合圖的 Euler Path / Tour
Hamilton Path / Tour
特殊圖的Hamilton Path / Tour 構造

生成樹問題
最小生成樹
第k小生成樹
最優比率生成樹
0/1分數規劃
度限制生成樹

連通性問題
強大的DFS演算法
無向圖連通性
割點
割邊
二連通分支
有向圖連通性
強連通分支
2-SAT
最小點基

有向無環圖
拓撲排序
有向無環圖與動態規劃的關係

二分圖匹配問題
一般圖問題與二分圖問題的轉換思路
最大匹配
有向圖的最小路徑覆蓋
0 / 1矩陣的最小覆蓋
完備匹配
最優匹配
穩定婚姻

網路流問題
網路流模型的簡單特徵和與線性規劃的關係
最大流最小割定理
最大流問題
有上下界的最大流問題
循環流
最小費用最大流 / 最大費用最大流

弦圖的性質和判定

組合數學

解決組合數學問題時常用的思想
逼近
遞推 / 動態規劃
概率問題
Polya定理

計算幾何 / 解析幾何

計算幾何的核心：叉積 / 面積
解析幾何的主力：複數

基本形
點
直線，線段
多邊形

凸多邊形 / 凸包
凸包演算法的引進，卷包裹法

Graham掃描法
水平序的引進，共線凸包的補丁

完美凸包演算法

相關判定
兩直線相交
兩線段相交
點在任意多邊形內的判定
點在凸多邊形內的判定

經典問題
最小外接圓
近似O(n)的最小外接圓演算法
點集直徑
旋轉卡殼，對踵點
多邊形的三角剖分

數學 / 數論

最大公約數
Euclid演算法
擴展的Euclid演算法
同餘方程 / 二元一次不定方程
同餘方程組

線性方程組
高斯消元法
解mod 2域上的線性方程組
整係數方程組的精確解法

矩陣
行列式的計算
利用矩陣乘法快速計算遞推關係

分數
分數樹
連分數逼近

數論計算
求N的約數個數
求phi(N)
求約數和
快速數論變換
……

素數問題
概率判素演算法
概率因子分解

數據結構

組織結構
二叉堆
左偏樹
二項樹
勝者樹
跳躍表
樣式圖標
斜堆
reap

統計結構
樹狀數組
虛二叉樹
線段樹
矩形面積並
圓形面積並

關係結構
Hash表
並查集
路徑壓縮思想的應用

STL中的數據結構
vector
deque
set / map

動態規劃 / 記憶化搜索

動態規劃和記憶化搜索在思考方式上的區別

最長子序列系列問題
最長不下降子序列
最長公共子序列
最長公共不下降子序列

一類NP問題的動態規劃解法

樹型動態規劃

背包問題

動態規劃的優化
四邊形不等式
函數的凸凹性
狀態設計
規劃方向

線性規劃

常用思想

二分
最小表示法

串

KMP
Trie結構
後綴樹/後綴數組
LCA/RMQ
有限狀態自動機理論

排序
選擇/冒泡
快速排序
堆排序
歸併排序
基數排序
拓撲排序
排序網路

謝邀，來遲了抱歉。
樓上關於演算法的分類都說得很清楚，我就不重複了。
不過我揣摩題主提這個問題的目的，應該是想知道如何讓自己成為一個合格的會常見演算法的ACM選手，這樣的話其實根據演算法分類之類的去學習沒什麼意義。
一切脫離實戰題目的演算法學習都是耍流氓。
推薦 Modzieowa Akademia Informatyczna (MAIN)

貼一下hzwer巨巨的總結帖，侵刪~
OI省選演算法匯總

IOI Syllabus: http://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus.pdf

上邊列的知識點挺全的，雖然是針對IOI的，不過對ACM也有參考價值吧。

數據結構：
樹狀數組，線段樹，treap，splay
字元串：
kmp,exkmp,ac自動機,後綴數組,manacher,hash
數論：
篩法，miller-rabin，大數質因分解，中國剩餘定理，原根
計算幾何：
直線，線段，三角形，多邊形，圓，能求交的都求交。。
凸包，半平面交，掃麵線，旋轉卡殼
圖論：
割點割邊，最短路，最小生成樹。
還有一些雜項，做得題多了就都碰到了。

邏輯類：枚舉、貪心、動態規劃、深搜廣搜
結構類：棧、並查集、堆、樹、拓撲圖、圖論
幾何類：凸包
公式類：Fibonacci，排列組合，概率
幾何類的小演算法很多，比如求點線關係；還有線性方程組、最大最小流；還有一些特定的演算法：最短路勁、排序等。

我感覺最其中重要的是搜索，搜索可以對大部分問題提供通解，但會有效率問題，於是有雙向廣搜、A星搜索等等。在現實應用中，我覺得相對其他一些來講，搜索也是比較有用的。

演算法神馬弱爆了，數學完爆一切……
神經歷：
計算機學院逗比：這題 O(n^2)複雜度啊，我想想怎麼優化到 nLogn
數學系MM：這題給我，我覺得有公式，1個半小時時間來推導吧。
…………
1個小時候，公式誕生， O(1)………………
有木有啊！！！！ O（1）！！！！！！直接帶入 input 數據就出結果了，迭代都不需要……

編程進階 - Cifer
這個感覺挺靠譜的。。。

推薦ACM書籍《挑戰程序設計競賽》，這本書涵蓋了ACM中所以到的演算法所有知識。

傳說中的一切演算法皆搜索

USACO裡面有這麼一個介紹，這是針對IOI的，供樓主參考。

Hal Burch conducted an analysis over spring break of 1999 and made an amazing discovery: there are only 16 types of programming contest problems! Furthermore, the top several comprise almost 80% of the problems seen at the IOI. Here they are:

Dynamic Programming
Greedy
Complete Search
Flood Fill
Shortest Path
Recursive Search Techniques
Minimum Spanning Tree
Knapsack
Computational Geometry
Network Flow
Eulerian Path
Two-Dimensional Convex Hull
BigNums
Heuristic Search
Approximate Search
Ad Hoc Problems

Quora：What are the algorithms required to solve all problems (using C++) in any competitive coding contest?