Onway

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

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

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

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

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

 第一階段： 練經(jīng)典常用算法，下面的每個(gè)算法給我打上十到二十遍，同時(shí)自己精簡(jiǎn)代碼，因?yàn)樘Ｓ?，所以要練到?xiě)時(shí)不用想，10-15分鐘內(nèi)打完。   

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

2．最小生成樹(shù)（先寫(xiě)個(gè)prim，kruscal要用并查集，不好寫(xiě)）；

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

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

5．叉乘、判線段相交、然后寫(xiě)個(gè)凸包；

6．BFS、DFS，同時(shí)熟練hash表（要熟，要靈活,代碼要簡(jiǎn)）；

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

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

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

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

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

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

3．線段樹(shù)；

4. 并查集；   

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

6．博弈類算法。博弈樹(shù)，二進(jìn)制法等；

7．最大團(tuán)，最大獨(dú)立集；

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

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

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

 算法書(shū) 有很多可以參考：

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

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

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

2、Introduction to Algorithms

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

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

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

吳文虎 王建德

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

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

謝政 李建平

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

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

N.Wirth

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

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

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