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源程序,適合各種水平的讀者。
一.動態規劃
參考資料:
劉汝佳《演算法藝術與信息學競賽》《演算法導論》推薦題目:http://acm.pku.edu.cn/JudgeOnline/problem?id=1141簡單http://acm.pku.edu.cn/JudgeOnline/problem?id=2288中等,經典TSP問題http://acm.pku.edu.cn/JudgeOnline/problem?id=2411中等,狀態壓縮DPhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1112
中等http://acm.pku.edu.cn/JudgeOnline/problem?id=1848中等,樹形DP。可參考《演算法藝術與信息學競賽》動態規劃一節的樹狀模型http://acm.zju.edu.cn/show_problem.php?pid=1234中等,《演算法藝術與信息學競賽》中的習題http://acm.pku.edu.cn/JudgeOnline/problem?id=1947中等,《演算法藝術與信息學競賽》中的習題http://acm.pku.edu.cn/JudgeOnline/problem?id=1946中等,《演算法藝術與信息學競賽》中的習題http://acm.pku.edu.cn/JudgeOnline/problem?id=1737
中等,遞推http://acm.pku.edu.cn/JudgeOnline/problem?id=1821中等,需要減少冗餘計算http://acm.zju.edu.cn/show_problem.php?pid=2561中等,四邊形不等式的簡單應用http://acm.pku.edu.cn/JudgeOnline/problem?id=1038較難,狀態壓縮DP,《演算法藝術與信息學競賽》中有解答http://acm.pku.edu.cn/JudgeOnline/problem?id=1390較難,《演算法藝術與信息學競賽》中有解答http://acm.pku.edu.cn/JudgeOnline/problem?id=3017
較難,需要配合數據結構優化(我的題目^_^)http://acm.pku.edu.cn/JudgeOnline/problem?id=1682較難,寫起來比較麻煩http://acm.pku.edu.cn/JudgeOnline/problem?id=2047較難http://acm.pku.edu.cn/JudgeOnline/problem?id=2152難,樹形DPhttp://acm.pku.edu.cn/JudgeOnline/problem?id=3028難,狀態壓縮DP,題目很有意思http://acm.pku.edu.cn/JudgeOnline/problem?id=3124
難http://acm.pku.edu.cn/JudgeOnline/problem?id=2915非常難二.搜索
參考資料:
劉汝佳《演算法藝術與信息學競賽》推薦題目:http://acm.pku.edu.cn/JudgeOnline/problem?id=1011簡單,深搜入門題http://acm.pku.edu.cn/JudgeOnline/problem?id=1324中等,廣搜
http://acm.pku.edu.cn/JudgeOnline/problem?id=2044中等,廣搜http://acm.pku.edu.cn/JudgeOnline/problem?id=2286較難,廣搜http://acm.pku.edu.cn/JudgeOnline/problem?id=1945難,IDA,迭代加深搜索,需要較好的啟發函數http://acm.pku.edu.cn/JudgeOnline/problem?id=2449難,可重複K最短路,A。可參考解題報告:http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144http://acm.pku.edu.cn/JudgeOnline/problem?id=1190難,深搜剪枝,《演算法藝術與信息學競賽》中有解答http://acm.pku.edu.cn/JudgeOnline/problem?id=1084難,《演算法藝術與信息學競賽》習題http://acm.pku.edu.cn/JudgeOnline/problem?id=2989難,深搜http://acm.pku.edu.cn/JudgeOnline/problem?id=1167較難,《演算法藝術與信息學競賽》中有解答http://acm.pku.edu.cn/JudgeOnline/problem?id=1069很難三. 常用數據結構
參考資料:
劉汝佳《演算法藝術與信息學競賽》《演算法導論》線段樹資料:http://home.ustc.edu.cn/~zhuhcheng/ACM/segment_tree.pdf樹狀數組資料http://home.ustc.edu.cn/~zhuhcheng/ACM/tree.ppt關於線段樹和樹狀數組更多相關內容可在網上搜到後綴數組資料http://home.ustc.edu.cn/~zhuhcheng/ACM/suffix_array.pdfhttp://home.ustc.edu.cn/~zhuhcheng/ACM/linear_suffix.pdf推薦題目http://acm.pku.edu.cn/JudgeOnline/problem?id=2482較難,線段樹應用,《演算法藝術與信息學競賽》中有解答http://acm.pku.edu.cn/JudgeOnline/problem?id=1151簡單,線段樹應用矩形面積並,《演算法藝術與信息學競賽》中有解答http://acm.pku.edu.cn/JudgeOnline/problem?id=3225較難,線段樹應用,可參考解題報告http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1233http://acm.pku.edu.cn/JudgeOnline/problem?id=2155難,二維樹狀數組。http://acm.pku.edu.cn/JudgeOnline/problem?id=2777中等,線段樹應用。http://acm.pku.edu.cn/JudgeOnline/problem?id=2274難,堆的應用,《演算法藝術與信息學競賽》中有解答http://acm.zju.edu.cn/show_problem.php?pid=2334中等,左偏樹,二項式堆或其他可合併堆的應用。左偏樹參考 http://www.nist.gov/dads/HTML/leftisttree.html二項式堆參見《演算法導論》相關章節http://acm.pku.edu.cn/JudgeOnline/problem?id=1182中等,並查集http://acm.pku.edu.cn/JudgeOnline/problem?id=1816中等,字典樹http://acm.pku.edu.cn/JudgeOnline/problem?id=2778較難,多串匹配樹參考: http://home.ustc.edu.cn/~zhuhcheng/ACM/zzy2004.pdfhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1743難,後綴數組http://acm.pku.edu.cn/JudgeOnline/problem?id=2774較難,最長公共子串,經典問題,後綴數組http://acm.pku.edu.cn/JudgeOnline/problem?id=2758很難,後綴數組可參考解題報告http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1178http://acm.pku.edu.cn/JudgeOnline/problem?id=2448很難,數據結構綜合運用四.圖論基礎
參考資料:
劉汝佳《演算法藝術與信息學競賽》《演算法導論》《網路演算法與複雜性理論》謝政推薦題目:http://acm.pku.edu.cn/JudgeOnline/problem?id=2337簡單,歐拉路http://acm.pku.edu.cn/JudgeOnline/problem?id=3177中等,無向圖割邊http://acm.pku.edu.cn/JudgeOnline/problem?id=2942較難,無向圖雙連通分支http://acm.pku.edu.cn/JudgeOnline/problem?id=1639中等,最小度限制生成樹,《演算法藝術與信息學競賽》中有解答http://acm.pku.edu.cn/JudgeOnline/problem?id=2728中等,最小比率生成樹,《演算法藝術與信息學競賽》中有解答http://acm.pku.edu.cn/JudgeOnline/problem?id=3013簡單,最短路問題http://acm.pku.edu.cn/JudgeOnline/problem?id=1275中等,差分約束系統,Bellman-Ford求解,《演算法藝術與信息學競賽》中有解答http://acm.pku.edu.cn/JudgeOnline/problem?id=1252簡單,Bellman-Fordhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1459中等,網路流http://acm.pku.edu.cn/JudgeOnline/problem?id=2391較難,網路流http://acm.pku.edu.cn/JudgeOnline/problem?id=1325中等,二部圖最大匹配http://acm.pku.edu.cn/JudgeOnline/problem?id=2226較難,二部圖最大匹配http://acm.pku.edu.cn/JudgeOnline/problem?id=2195中等,二部圖最大權匹配KM演算法參考《網路演算法與複雜性理論》http://acm.pku.edu.cn/JudgeOnline/problem?id=2516較難,二部圖最大權匹配http://acm.pku.edu.cn/JudgeOnline/problem?id=1986中等,LCA(最近公共祖先)問題參考Tarjans LCA algorithm 《演算法導論》第21章習題http://acm.pku.edu.cn/JudgeOnline/problem?id=2723較難,2-SAT問題參考:http://home.ustc.edu.cn/~zhuhcheng/ACM/2-SAT.PPThttp://acm.pku.edu.cn/JudgeOnline/problem?id=2749較難,2-SAT問題http://acm.pku.edu.cn/JudgeOnline/problem?id=3164較難,最小樹形圖參考《網路演算法與複雜性理論》中朱-劉演算法五.數論及組合計數基礎
http://acm.pku.edu.cn/JudgeOnline/problem?id=1811
簡單,素數判定,大數分解參考演算法導論相關章節http://acm.pku.edu.cn/JudgeOnline/problem?id=2888較難,Burnside引理http://acm.pku.edu.cn/JudgeOnline/problem?id=2891中等,解模方程組http://acm.pku.edu.cn/JudgeOnline/problem?id=2154中等,經典問題,波利亞定理http://cs.scu.edu.cn/soj/problem.action?id=2703難,極好的題目,Burnside引理+模線性方程組http://acm.pku.edu.cn/JudgeOnline/problem?id=2764較難,需要數學方法,該方法在《具體數學》第七章有講http://acm.pku.edu.cn/JudgeOnline/problem?id=1977簡單,矩陣快速乘法推薦閱讀:
※最大流最小費用演算法中的spfa找增廣路是貪心演算法嗎?
※如何評價NOI2017?
※如何評價2017 ACM/ICPC 亞洲區(南寧賽區)網路賽 / 英語閱讀大賽?
※東北大學秦皇島分校acm實力如何?
※二分思想入門—快速排序
TAG:ACM |