標籤:

ACM演算法分類、推薦學習資料和配套習題(轉)

相信每一位玩ACM程序設計競賽的同學來說,都有一個從入門到精通的過程,而且分享他們經驗的時候,見到最多的就是一種合作和拼搏精神,樂在其中的那種激情。

Wilbert即將畢業,作為一個菜鳥級的入門玩家,一直很想知道如何能在程序設計競賽中成為一個高手。即將無緣類似競賽的我,終於整理出了一些程序設計競賽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、Concrete Mathematics --- A Foundation For Computer ScienceRonald L. Graham , Donald E. Knuth , Oren Patashnik  

這本書《具體數學》是Stanford計算機系的教材(1970 年開始給研究生授課),書的內容是Knuth的巨著TAOCP第一章的擴展,涉及了計算機科學領域內幾乎所有可能遇到的數學知識。書中許多經典問題的解答比目前廣泛流傳的解法更易懂。對於提高大家的數學修養有很大幫助。

2、Introduction to AlgorithmsThomas H. Cormen ,Charles E. Leiserson ,Ronald L. Rivest ,Clifford Stein  

《演算法導論》MIT計算機系的經典演算法教材。作者Rivest獲得過ACM Turing Award,牛!本書內容全面,語言通俗,很適合大家入門。

3、實用演算法的分析和程序設計,吳文虎 王建德  

大名鼎鼎的「黑書」。內容包括了競賽需要的各種演算法,各種層次的讀者都適合。

4、網路演算法與複雜性理論謝政 李建平  

內容很豐富的圖論教材

5、演算法+數據結構=程序N.Wirth  

Pascal語言的發明人Wirth教授的名著,深入闡述了演算法與數據結構的關係,對每個演算法都提供詳細的Pascal源程序,適合各種水平的讀者。

一.動態規劃

參考資料:

劉汝佳《演算法藝術與信息學競賽》《演算法導論》

推薦題目:

acm.pku.edu.cn/JudgeOnl

簡單

acm.pku.edu.cn/JudgeOnl

中等,經典TSP問題

acm.pku.edu.cn/JudgeOnl

中等,狀態壓縮DP

acm.pku.edu.cn/JudgeOnl

中等

acm.pku.edu.cn/JudgeOnl

中等,樹形DP。可參考《演算法藝術與信息學競賽》動態規劃一節的樹狀模型

acm.zju.edu.cn/show_pro

中等,《演算法藝術與信息學競賽》中的習題

acm.pku.edu.cn/JudgeOnl

中等,《演算法藝術與信息學競賽》中的習題

acm.pku.edu.cn/JudgeOnl

中等,《演算法藝術與信息學競賽》中的習題

acm.pku.edu.cn/JudgeOnl

中等,遞推

acm.pku.edu.cn/JudgeOnl

中等,需要減少冗餘計算

acm.zju.edu.cn/show_pro

中等,四邊形不等式的簡單應用

acm.pku.edu.cn/JudgeOnl

較難,狀態壓縮DP,《演算法藝術與信息學競賽》中有解答

acm.pku.edu.cn/JudgeOnl

較難,《演算法藝術與信息學競賽》中有解答

acm.pku.edu.cn/JudgeOnl

較難,需要配合數據結構優化(我的題目^_^)

acm.pku.edu.cn/JudgeOnl

較難,寫起來比較麻煩

acm.pku.edu.cn/JudgeOnl

較難

acm.pku.edu.cn/JudgeOnl

難,樹形DP

acm.pku.edu.cn/JudgeOnl

難,狀態壓縮DP,題目很有意思

acm.pku.edu.cn/JudgeOnl

acm.pku.edu.cn/JudgeOnl

非常難

二.搜索

參考資料:

劉汝佳《演算法藝術與信息學競賽》

推薦題目:

acm.pku.edu.cn/JudgeOnl

簡單,深搜入門題

acm.pku.edu.cn/JudgeOnl

中等,廣搜

acm.pku.edu.cn/JudgeOnl

中等,廣搜

acm.pku.edu.cn/JudgeOnl

較難,廣搜

acm.pku.edu.cn/JudgeOnl

難,IDA,迭代加深搜索,需要較好的啟發函數

acm.pku.edu.cn/JudgeOnl

難,可重複K最短路,A
。可參考解題報告:

acm.pku.edu.cn/JudgeOnl

acm.pku.edu.cn/JudgeOnl

難,深搜剪枝,《演算法藝術與信息學競賽》中有解答

acm.pku.edu.cn/JudgeOnl

難,《演算法藝術與信息學競賽》習題

acm.pku.edu.cn/JudgeOnl

難,深搜

acm.pku.edu.cn/JudgeOnl

較難,《演算法藝術與信息學競賽》中有解答

acm.pku.edu.cn/JudgeOnl

很難

三. 常用數據結構

參考資料:

劉汝佳《演算法藝術與信息學競賽》

《演算法導論》

線段樹資料:

home.ustc.edu.cn/~zhuhc

樹狀數組資料

home.ustc.edu.cn/~zhuhc

關於線段樹和樹狀數組更多相關內容可在網上搜到

後綴數組資料

home.ustc.edu.cn/~zhuhc

home.ustc.edu.cn/~zhuhc

推薦題目

acm.pku.edu.cn/JudgeOnl

較難,線段樹應用,《演算法藝術與信息學競賽》中有解答

acm.pku.edu.cn/JudgeOnl

簡單,線段樹應用矩形面積並,《演算法藝術與信息學競賽》中有解答

acm.pku.edu.cn/JudgeOnl

較難,線段樹應用,可參考解題報告

acm.pku.edu.cn/JudgeOnl

acm.pku.edu.cn/JudgeOnl

難,二維樹狀數組。

acm.pku.edu.cn/JudgeOnl

中等,線段樹應用。

acm.pku.edu.cn/JudgeOnl

難,堆的應用,《演算法藝術與信息學競賽》中有解答

acm.zju.edu.cn/show_pro

中等,左偏樹,二項式堆或其他可合併堆的應用。

左偏樹參考 nist.gov/dads/HTML/left

二項式堆參見《演算法導論》相關章節

acm.pku.edu.cn/JudgeOnl

中等,並查集

acm.pku.edu.cn/JudgeOnl

中等,字典樹

acm.pku.edu.cn/JudgeOnl

較難,多串匹配樹

參考: home.ustc.edu.cn/~zhuhc

acm.pku.edu.cn/JudgeOnl

難,後綴數組

acm.pku.edu.cn/JudgeOnl

較難,最長公共子串,經典問題,後綴數組

acm.pku.edu.cn/JudgeOnl

很難,後綴數組

可參考解題報告

acm.pku.edu.cn/JudgeOnl

acm.pku.edu.cn/JudgeOnl

很難,數據結構綜合運用

四.圖論基礎

參考資料:

劉汝佳《演算法藝術與信息學競賽》《演算法導論》《網路演算法與複雜性理論》謝政

推薦題目:

acm.pku.edu.cn/JudgeOnl

簡單,歐拉路

acm.pku.edu.cn/JudgeOnl

中等,無向圖割邊

acm.pku.edu.cn/JudgeOnl

較難,無向圖雙連通分支

acm.pku.edu.cn/JudgeOnl

中等,最小度限制生成樹,《演算法藝術與信息學競賽》中有解答

acm.pku.edu.cn/JudgeOnl

中等,最小比率生成樹,《演算法藝術與信息學競賽》中有解答

acm.pku.edu.cn/JudgeOnl

簡單,最短路問題

acm.pku.edu.cn/JudgeOnl

中等,差分約束系統,Bellman-Ford求解,《演算法藝術與信息學競賽》中有解答

acm.pku.edu.cn/JudgeOnl

簡單,Bellman-Ford

acm.pku.edu.cn/JudgeOnl

中等,網路流

acm.pku.edu.cn/JudgeOnl

較難,網路流

acm.pku.edu.cn/JudgeOnl

中等,二部圖最大匹配

acm.pku.edu.cn/JudgeOnl

較難,二部圖最大匹配

acm.pku.edu.cn/JudgeOnl

中等,二部圖最大權匹配

KM演算法參考《網路演算法與複雜性理論》

acm.pku.edu.cn/JudgeOnl

較難,二部圖最大權匹配

acm.pku.edu.cn/JudgeOnl

中等,LCA(最近公共祖先)問題

參考Tarjans LCA algorithm 《演算法導論》第21章習題

acm.pku.edu.cn/JudgeOnl

較難,2-SAT問題

參考:home.ustc.edu.cn/~zhuhc

acm.pku.edu.cn/JudgeOnl

較難,2-SAT問題

acm.pku.edu.cn/JudgeOnl

較難,最小樹形圖

參考《網路演算法與複雜性理論》中朱-劉演算法

五.數論及組合計數基礎

acm.pku.edu.cn/JudgeOnl

簡單,素數判定,大數分解

參考演算法導論相關章節

acm.pku.edu.cn/JudgeOnl

較難,Burnside引理

acm.pku.edu.cn/JudgeOnl

中等,解模方程組

acm.pku.edu.cn/JudgeOnl

中等,經典問題,波利亞定理

cs.scu.edu.cn/soj/probl

難,極好的題目,Burnside引理+模線性方程組

acm.pku.edu.cn/JudgeOnl

較難,需要數學方法,該方法在《具體數學》第七章有講

acm.pku.edu.cn/JudgeOnl

簡單,矩陣快速乘法


推薦閱讀:

最大流最小費用演算法中的spfa找增廣路是貪心演算法嗎?
如何評價NOI2017?
如何評價2017 ACM/ICPC 亞洲區(南寧賽區)網路賽 / 英語閱讀大賽?
東北大學秦皇島分校acm實力如何?
二分思想入門—快速排序

TAG:ACM |