ACM中哪些演算法是應該敲的滾瓜爛熟的？

12-29

看到ACM大神敲代碼的時候，鍵盤"咔噠咔噠"之間線段樹出來了，再"咔噠咔噠"bfs出來了。這種手速肯定是對常用演算法已經熟練到了不用腦子的地步，所以，一般有哪些這樣的演算法呢？

不看模板能敲出來，並不意味著都是默寫的，就像樹套樹，可持久化線段樹這種，懂個線段樹然後隨手拓展一下就能在13年長春區域賽拿個sb了。這個有獎金的sb要把我笑死了哈哈哈哈。。

##### 第一次更新回答，不知道怎麼分割

好像以前搞acm的時候，能不看模板敲出來的有：

二分查找

並查集

bit

kmp

dij

tarjan

mst（手寫heap）

spfa

線段樹

ac自動機

伸展樹

sb樹

圓交

圓並

半平面交

isap

mcmf

manacher

模擬退火

km和hk演算法

穩定婚姻演算法

好像最後半年還可以寫出dancing link和後綴數組。其實上面也沒多少代碼嘛，哈哈哈哈，理解了就記住了。

可以參考一下SJTU的演算法模板：http://ad1024.tech/asset/doc/SJTU_Templates.pdf

定位不同（WF/金/銀/銅，thinker/幾何選手）的選手需要掌握的東西是不同，一張技能表並不適合所有的acmer。我覺得有練模板的時間不如多寫幾道題，什麼東西遇到的多，就說明什麼東西是你應該熟練掌握的，並且因為你寫的多自然就熟練了。

還有我對題目描述裡面的「對常用演算法已經熟練到了不用腦子的地步」不認可。理想情況下應該是對某個演算法的框架非常熟悉，然後順著框架一句一句地在腦內快速補完（在寫完正在寫的這一句之前），這樣的好處是可以針對題目做細節上的變動。如果真的不動腦子寫，一方面會浪費大量時間在記憶上，一方面寫的時候也不夠靈活。

一些簡單和非常常用的應該很熟練就能寫出來。

ds比如：線段樹、普通二叉搜索樹、樹狀數組、棧、單調棧、單調隊列、並查集、帶權並查集（向量思想）、哈希表、trie樹、cdq分治。

基本技巧例如：前向邊存圖、二分法、三分法、枚舉子集、莫隊離線、啟發式合併、基數排序（瀋陽賽區被這個坑了）。

圖論演算法比如：tarjan、dijkstra、kruscal、spfa、floyd。

字元串演算法如：kmp。

搜索：bfs、dfs、IDA*、A*、n進位枚舉、折半搜索。

這些都是相對來說代碼比較短，實現起來比較容易，而且出現次數也是非常多的，要求選手不看模板能熟練寫出來的。

平衡樹

所有會的都該

（我並不能，所以我弱

在OI中。。。會的一定要十分熟。。。

看描述一般是打oi打習慣了...從acm開始上手的一般是control+ccontrol+v……說實話高中打oi學到的東西我不看代碼也能比較快的寫出來，打acm後學的東西不看版子可能推起來也比較慢……QAQ不過可能仍然是我比較菜。

其實除了碼量很大的或者數學性很強的其他都要弄成這樣？

熟練的YY能力。

優雅的搜索。

（逃）

打表找規律

個人認為大部份網站的div2題有的演算法都應該要背熟。

利益申報: 在不知道有板子的情況下練了一年CF

oi出身的表示還沒用到過板子

oi的會很熟，我沒打過oi。。不過搜索和線段樹手搓還行，不過有些比較麻煩的就得看板子了。