Onway

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

 　　Wilbert即將畢業(yè)，作為一個菜鳥級的入門玩家，一直很想知道如何能在程序設(shè)計競賽中成為一個高手。即將無緣類似競賽的我，終于整理出了一些程序設(shè)計競賽ACM訓(xùn)練之道，愿與大家分享。

 　　首先是編程的能力，一般要做到50行以內(nèi)的程序不用調(diào)試、100行以內(nèi)的二分鐘內(nèi)調(diào)試成功。

 　　訓(xùn)練過ACM等程序設(shè)計競賽的人在算法上有較大的優(yōu)勢，這就說明當(dāng)你編程能力提高之后，主要時間是花在思考算法上，不是花在寫程序與debug上。

 我摘錄了網(wǎng)上的一個 訓(xùn)練計劃 ：

 第一階段： 練經(jīng)典常用算法，下面的每個算法給我打上十到二十遍，同時自己精簡代碼，因為太常用，所以要練到寫時不用想，10-15分鐘內(nèi)打完。   

1．最短路（Floyd、Dijstra、BellmanFord）；

2．最小生成樹（先寫個prim，kruscal要用并查集，不好寫）；

3．大數(shù)（高精度）加減乘除；

4．二分查找（代碼可在五行以內(nèi)）；

5．叉乘、判線段相交、然后寫個凸包；

6．BFS、DFS，同時熟練hash表（要熟，要靈活,代碼要簡）；

7．?dāng)?shù)學(xué)上的有：輾轉(zhuǎn)相除（兩行內(nèi)），線段交點、多角形面積公式；

8．調(diào)用系統(tǒng)的qsort, 技巧很多，慢慢掌握；

9．任意進制間的轉(zhuǎn)換......

第二階段： 練習(xí)復(fù)雜一點，但也較常用的算法。 如：   

1．二分圖匹配（匈牙利），最小路徑覆蓋；

2．網(wǎng)絡(luò)流，最小費用流；

3．線段樹；

4. 并查集；   

5．熟悉動態(tài)規(guī)劃的各個典型：LCS、最長遞增子串、三角剖分、記憶化dp    ；

6．博弈類算法。博弈樹，二進制法等；

7．最大團，最大獨立集；

　　8．判斷點在多邊形內(nèi)；

9．差分約束系統(tǒng)；   

10．雙向廣度搜索、A*算法，最小耗散優(yōu)先......

 算法書 有很多可以參考：

 1、Concrete Mathematics --- A Foundation For Computer Science

Ronald L. Graham ， Donald E. Knuth ， Oren Patashnik

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

2、Introduction to Algorithms

Thomas H. Cormen ，Charles E. Leiserson ，Ronald L. Rivest ，Clifford Stein

《算法導(dǎo)論》MIT計算機系的經(jīng)典算法教材。作者Rivest獲得過ACM Turing Award，牛！本書內(nèi)容全面，語言通俗，很適合大家入門。

3、實用算法的分析和程序設(shè)計

吳文虎 王建德

大名鼎鼎的“黑書”。內(nèi)容包括了競賽需要的各種算法，各種層次的讀者都適合。

4、網(wǎng)絡(luò)算法與復(fù)雜性理論

謝政 李建平

內(nèi)容很豐富的圖論教材

5、算法+數(shù)據(jù)結(jié)構(gòu)=程序

N.Wirth

Pascal語言的發(fā)明人Wirth教授的名著，深入闡述了算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系，對每個算法都提供詳細的Pascal源程序，適合各種水平的讀者。

 　　最后，在學(xué)習(xí)算法提升戰(zhàn)斗力的同時，也要多做題目，實戰(zhàn)是很有必要的。其實并不是所有的題目都是靠算法的，有一些題目是有多種可以優(yōu)化的手段，也有一些工程性比較強的題目。上手做和把題做精還是有很大區(qū)別的（慚愧的說，我就是屬于上手做，沒有做精，所以……）。

 　　愿每一位程序設(shè)計競賽愛好者挑戰(zhàn)極限！