一直覺(jué)得ACM是個(gè)神奇的東西，ACM陪伴我度過(guò)了許多枯燥寂寞的時(shí)光，雖然在很多人看來(lái)這個(gè)也許是枯燥和無(wú)聊的。但是和其他ACMer一樣，我深深被它的魅力所吸引，雖然第一次比較正式的Regional的比賽也以悲劇告終，但我覺(jué)得不后悔。下面就簡(jiǎn)單的講一下我的ACM經(jīng)歷吧。

我接觸ACM的時(shí)間比較晚（我一直覺(jué)得這是我悲劇的根源），大一下的時(shí)候?qū)W了C程序設(shè)計(jì)，覺(jué)得編程還挺有意思的，除了完成老師布置的作業(yè)以外，我還自己用C語(yǔ)言編程實(shí)現(xiàn)課后的一些習(xí)題，學(xué)會(huì)了C語(yǔ)言的一些基本的東西。第一次聽(tīng)說(shuō)ACM是在大二下的時(shí)候,ACM亞洲區(qū)主席黃金雄來(lái)我校開(kāi)講座，講座中講了很多關(guān)于ACM的事情,講座后我去找了羅老師,羅老師給我介紹了學(xué)校ACM-ICPC競(jìng)賽隊(duì)的一些基本情況,介紹了一下怎么在oj上做題,怎么起步,然后我就開(kāi)始做題了, 開(kāi)始就做一些水題(也就是簡(jiǎn)單題)。

在暑假集訓(xùn)之前大概作了70+的題目,中間還暈乎乎參加的一次校賽,雖然十分的悲劇,但是讓我對(duì)算法有了初步的認(rèn)識(shí),讓我知道了算法可以提高效率,否則就會(huì)超時(shí)。

后來(lái)就迎來(lái)了暑假的集訓(xùn)，每天都重復(fù)機(jī)房——食堂——寢室的生活，開(kāi)始的幾天還是整天在pku上刷水題，后來(lái)就是個(gè)人賽 ，由于個(gè)人賽的題目很多都是以前的regional的題目，當(dāng)時(shí)我對(duì)算法的了解幾乎為零，做起來(lái)也比較吃力，成績(jī)也不太理想，不過(guò)那個(gè)時(shí)期是我開(kāi)始全面接觸ACM算法的時(shí)期，后來(lái)就是組隊(duì)賽，我當(dāng)時(shí)和FHX和ZYY組了女隊(duì)，個(gè)人感覺(jué)組隊(duì)賽比個(gè)人賽壓力小很多，因?yàn)橛腥齻€(gè)人一起做題，但是女隊(duì)比較弱，幾場(chǎng)網(wǎng)絡(luò)賽下來(lái)，我們經(jīng)常墊底，但那個(gè)時(shí)候是我學(xué)習(xí)全面了解ACM，學(xué)習(xí)了很多算法和數(shù)據(jù)結(jié)構(gòu)的知識(shí)，順便透露一下我那段時(shí)間每天的行程：早上機(jī)房----中午食堂-------下午機(jī)房------傍晚食堂------晚上機(jī)房------回寢室看動(dòng)畫片(那段時(shí)間很迷柯南）-----然后聊天-------然后再看一會(huì)題----然后睡覺(jué) ----在旁人看來(lái)這樣的生活確實(shí)是枯燥無(wú)味的，但是我覺(jué)得樂(lè)在其中，現(xiàn)在想起來(lái)還是挺懷念的。組隊(duì)賽后就迎來(lái)的了我大三的軍訓(xùn)，暑假集訓(xùn)算是結(jié)束了。

后來(lái)就是網(wǎng)絡(luò)賽了。哈爾濱，合肥，寧波，上海，武漢，總共做了五場(chǎng)的網(wǎng)絡(luò)賽。這段時(shí)間還是繼續(xù)再pku上做題，總的來(lái)說(shuō)還是有進(jìn)步的。后來(lái)羅老師終于為我們爭(zhēng)取到了上海賽區(qū)的比賽資格。上海Regional的比賽最終以悲劇告終，其實(shí)這是很正常的事情，學(xué)長(zhǎng)們都說(shuō)第一次比賽就是去受打擊了，但對(duì)于我這個(gè)大三的來(lái)說(shuō)，這可能是我唯一的一次Regional了，沒(méi)有拿獎(jiǎng)?wù)娴谋容^可惜，這次比賽也充分讓我認(rèn)識(shí)到差距的存在，很自己在ACM的學(xué)習(xí)之中的很多不足之處。可以在未來(lái)的學(xué)習(xí)中有所側(cè)重。下面我再介紹下關(guān)于ACM的學(xué)習(xí)吧。

（1） 起步階段。

開(kāi)始的時(shí)候就是對(duì)C語(yǔ)言的基本知識(shí)的學(xué)習(xí)，學(xué)過(guò)C語(yǔ)言的同學(xué)就可以開(kāi)始做題了，最好不要一開(kāi)始就接觸算法，可以到一些學(xué)校的oj上找些簡(jiǎn)單的題目做，對(duì)于初學(xué)者,poj是個(gè)不錯(cuò)的選擇,很多題目在網(wǎng)上找到解題報(bào)告和源代碼.很多題目也比較簡(jiǎn)單.下面簡(jiǎn)單介紹一下：

  **關(guān)于poj：

網(wǎng)址: http://acm.pku.edu.cn/JudgeOnline/ 

一般都是在oj上看完題目后在本機(jī)的編譯器上進(jìn)行程序的程序的編寫和調(diào)試,直到運(yùn)行結(jié)果正確了再在oj上提交,提交后會(huì)返回一下幾種結(jié)果:

  Accept--------------------------表明你的程序結(jié)果是OK的;

  Wrong Answer----------------表明你的程序有問(wèn)題, 對(duì)oj上給出的測(cè)試數(shù)據(jù)運(yùn)行結(jié)果不正確;

  Time Limit Exceeded----------------表明你的程序有可能是正確的,但是運(yùn)行效率不高導(dǎo)致超時(shí);

Rutime Error---------------運(yùn)行時(shí)錯(cuò)誤,一般是數(shù)組越界,除零,或者訪問(wèn)了不該訪問(wèn)的內(nèi)存導(dǎo)致的,可能的原因可能是數(shù)組開(kāi)的太小等原因;

Presentation Error----------------如果返回的是這個(gè)的話，那么你離Accept已經(jīng)很近了近了。一般出現(xiàn)這個(gè)的原因是運(yùn)行的結(jié)果是正確的，只是結(jié)果的格式不正確，一般是多打過(guò)著少打了空格或者換行之類的，這時(shí)只要重新看一下題目，弄清輸出要求就行了；

Memory Limit Exceeded--------------超內(nèi)存，一般是數(shù)組開(kāi)太大導(dǎo)致；

Compire Error----------------編譯錯(cuò)誤，這種錯(cuò)誤一般是不該出現(xiàn)的，一般沒(méi)有人會(huì)在本機(jī)上編譯都通不過(guò)的情況下就提交 ，不過(guò)有時(shí)要看清oj的要求，比如用int64還是lld。

**關(guān)于做簡(jiǎn)單題

我剛開(kāi)始的時(shí)候是在梅隴客棧的程序板塊上找到了一個(gè)我們學(xué)校內(nèi)部的簡(jiǎn)單題的分類。不過(guò)也可以通過(guò)其他途徑，比如可以到google上搜pku 簡(jiǎn)單題，或者是跟著別人做題，一般大家學(xué)習(xí)ACM得時(shí)候都是從簡(jiǎn)單題開(kāi)始做的，可以打開(kāi)某個(gè)學(xué)長(zhǎng)的賬號(hào)然后順著他的題號(hào)往下切。

剛開(kāi)始做題的時(shí)候如果看到某個(gè)題目一點(diǎn)想法都沒(méi)有，不要急于求成,也不要急著找學(xué)長(zhǎng)要代碼看，或者讓學(xué)長(zhǎng)提示。可以先看其它的題然后過(guò)一段時(shí)間再來(lái)看，或者當(dāng)你的程序提交上去wa個(gè)不停，經(jīng)過(guò)兩三天的思考仍然沒(méi)有思路的時(shí)候可以看一下oj上面的discuss，一般里面會(huì)有人貼出解題思路甚至是代碼，會(huì)提醒你這到題目有什么陷阱（但是堅(jiān)決不倡議做題的時(shí)候不經(jīng)過(guò)自己思考就直接看discuss的行為）。

還有就是建議初學(xué)者在C語(yǔ)言的基礎(chǔ)上學(xué)一下C++，建議看一下C++ primer這本書，C++里面有很多容器，比如說(shuō)Vector,queue

Map之類，還有快速排序sort函數(shù)，二分查找函數(shù)bsearch以及求字典序全排列next_permutation,等，用起來(lái)真的很爽（雖然現(xiàn)在還用的不是很熟）。

萬(wàn)事開(kāi)頭難，除了高中搞過(guò)IO競(jìng)賽的，對(duì)于大多數(shù)人來(lái)說(shuō)都是第一次接觸ACM，剛開(kāi)始做簡(jiǎn)單題的時(shí)候我也感覺(jué)并不容易，比如題目都是英文的看起來(lái)比較費(fèi)勁，要看很久才能搞清楚題目意思，有時(shí)候簡(jiǎn)單題目交上去卻WA個(gè)不停，題目有很多trick，覺(jué)得很郁悶，但是不要灰心，個(gè)人覺(jué)得ACM貴在堅(jiān)持，只要堅(jiān)持下來(lái)，就會(huì)越來(lái)越體會(huì)到ACM 的無(wú)窮樂(lè)趣了。

（2）       關(guān)于各種算法的學(xué)習(xí)。

下面是我在網(wǎng)上找到一個(gè)算法的分類，感覺(jué)還是挺全的。

初期:
一.基本算法:
(1)枚舉. (poj1753,poj2965)
(2)貪心(poj1328,poj2109,poj2586)
(3)遞歸和分治法.
(4)遞推.
(5)構(gòu)造法.(poj3295)
(6)模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖算法:
(1)圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷.
(2)最短路徑算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成樹(shù)算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓?fù)渑判?span lang="EN-US"> (poj1094)
(5)二分圖的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增廣路算法(KM算法). (poj1459,poj3436)
三.數(shù)據(jù)結(jié)構(gòu).
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、歸并排(與逆序數(shù)有關(guān))、堆排) (poj2388,poj2299)
(3)簡(jiǎn)單并查集的應(yīng)用.
(4)哈希表和二分查找等高效查找法(數(shù)的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼樹(shù)(poj3253)
(6)堆
(7)trie樹(shù)(靜態(tài)建樹(shù)、動(dòng)態(tài)建樹(shù)) (poj2513)
四.簡(jiǎn)單搜索
(1)深度優(yōu)先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)廣度優(yōu)先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)簡(jiǎn)單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動(dòng)態(tài)規(guī)劃
(1)背包問(wèn)題. (poj1837,poj1276)
(2)型如下表的簡(jiǎn)單DP(可參考lrj的書 page149):
1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長(zhǎng)公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優(yōu)二分檢索樹(shù)問(wèn)題)
六.數(shù)學(xué)
(1)組合數(shù)學(xué):
1.加法原理和乘法原理.
2.排列組合.
3.遞推關(guān)系.
(POJ3252,poj1850,poj1019,poj1942)
(2)數(shù)論.
1.素?cái)?shù)與整除問(wèn)題
2.進(jìn)制位.
3.同余模運(yùn)算.
(poj2635, poj3292,poj1845,poj2115)
(3)計(jì)算方法.
1.二分法求解單調(diào)函數(shù)相關(guān)知識(shí).(poj3273,poj3258,poj1905,poj3122)
七.計(jì)算幾何學(xué).
(1)幾何公式.
(2)叉積和點(diǎn)積的運(yùn)用(如線段相交的判定,點(diǎn)到線段的距離等). (poj2031,poj1039)
(3)多邊型的簡(jiǎn)單算法(求面積)和相關(guān)判定(點(diǎn)在多邊型內(nèi),多邊型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)
中級(jí):
一.基本算法:
(1)C++的標(biāo)準(zhǔn)模版庫(kù)的應(yīng)用. (poj3096,poj3007)
(2)較為復(fù)雜的模擬題的訓(xùn)練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖算法:
(1)差分約束系統(tǒng)的建立和求解. (poj1201,poj2983)
(2)最小費(fèi)用最大流(poj2516,poj2516,poj2195)
(3)雙連通分量(poj2942)
(4)強(qiáng)連通分支及其縮點(diǎn).(poj2186)
(5)圖的割邊和割點(diǎn)(poj3352)
(6)最小割模型、網(wǎng)絡(luò)流規(guī)約(poj3308, )
三.數(shù)據(jù)結(jié)構(gòu).
(1)線段樹(shù). (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)靜態(tài)二叉檢索樹(shù). (poj2482,poj2352)
(3)樹(shù)狀樹(shù)組(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)并查集的高級(jí)應(yīng)用. (poj1703,2492)
(6)KMP算法. (poj1961,poj2406)
四.搜索
(1)最優(yōu)化剪枝和可行性剪枝
(2)搜索的技巧和優(yōu)化 (poj3411,poj1724)
(3)記憶化搜索(poj3373,poj1691)
五.動(dòng)態(tài)規(guī)劃
(1)較為復(fù)雜的動(dòng)態(tài)規(guī)劃(如動(dòng)態(tài)規(guī)劃解特別的施行商問(wèn)題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)記錄狀態(tài)的動(dòng)態(tài)規(guī)劃. (POJ3254,poj2411,poj1185)
(3)樹(shù)型動(dòng)態(tài)規(guī)劃(poj2057,poj1947,poj2486,poj3140)
六.數(shù)學(xué)
(1)組合數(shù)學(xué):
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關(guān)系和母函數(shù).
(2)數(shù)學(xué).
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問(wèn)題. (poj3071,poj3440)
3.GCD、擴(kuò)展的歐幾里德(中國(guó)剩余定理) (poj3101)
(3)計(jì)算方法.
1.0/1分?jǐn)?shù)規(guī)劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)隨機(jī)化算法(poj3318,poj2454)
(5)雜題.
(poj1870,poj3296,poj3286,poj1095)
七.計(jì)算幾何學(xué).
(1)坐標(biāo)離散化.
(2)掃描線算法(例如求矩形的面積和周長(zhǎng)并,常和線段樹(shù)或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多邊形的內(nèi)核(半平面交)(poj3130,poj3335)
(4)幾何工具的綜合應(yīng)用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高級(jí):
一.基本算法要求:
(1)代碼快速寫成,精簡(jiǎn)但不失風(fēng)格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保證正確性和高效性. poj3434
二.圖算法:
(1)度限制最小生成樹(shù)和第K最短路. (poj1639)
(2)最短路,最小生成樹(shù),二分圖,最大流問(wèn)題的相關(guān)理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最優(yōu)比率生成樹(shù). (poj2728)
(4)最小樹(shù)形圖(poj3164)
(5)次小生成樹(shù).
(6)無(wú)向圖、有向圖的最小環(huán)
三.數(shù)據(jù)結(jié)構(gòu).
(1)trie圖的建立和應(yīng)用. (poj2778)
(2)LCA和RMQ問(wèn)題(LCA(最近公共祖先問(wèn)題) 有離線算法(并查集+dfs) 和 在線算法
(RMQ+dfs)).(poj1330)
(3)雙端隊(duì)列和它的應(yīng)用(維護(hù)一個(gè)單調(diào)的隊(duì)列,常常在動(dòng)態(tài)規(guī)劃中起到優(yōu)化狀態(tài)轉(zhuǎn)移的
目的). (poj2823)
(4)左偏樹(shù)(可合并堆).
(5)后綴樹(shù)(非常有用的數(shù)據(jù)結(jié)構(gòu),也是賽區(qū)考題的熱點(diǎn)).
(poj3415,poj3294)
四.搜索
(1)較麻煩的搜索題目訓(xùn)練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)廣搜的狀態(tài)優(yōu)化:利用M進(jìn)制數(shù)存儲(chǔ)狀態(tài)、轉(zhuǎn)化為串用hash表判重、按位壓縮存儲(chǔ)狀態(tài)、雙向廣搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的優(yōu)化:盡量用位運(yùn)算、一定要加剪枝、函數(shù)參數(shù)盡可能少、層數(shù)不易過(guò)大、可以考慮雙向搜索或者是輪換搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.動(dòng)態(tài)規(guī)劃
(1)需要用數(shù)據(jù)結(jié)構(gòu)優(yōu)化的動(dòng)態(tài)規(guī)劃.
(poj2754,poj3378,poj3017)
(2)四邊形不等式理論.
(3)較難的狀態(tài)DP(poj3133)
六.數(shù)學(xué)
(1)組合數(shù)學(xué).
1.MoBius反演(poj2888,poj2154)
2.偏序關(guān)系理論.
(2)博奕論.
1.極大極小過(guò)程(poj3317,poj1085)
2.Nim問(wèn)題.
七.計(jì)算幾何學(xué).
(1)半平面求交(poj3384,poj2540)
(2)可視圖的建立(poj2966)
(3)點(diǎn)集最小圓覆蓋.
(4)對(duì)踵點(diǎn)(poj2079)
八.綜合題.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)
以及補(bǔ)充
Dp狀態(tài)設(shè)計(jì)與方程總結(jié)

1.不完全狀態(tài)記錄
<1>青蛙過(guò)河問(wèn)題
<2>利用區(qū)間dp
2.背包類問(wèn)題
<1> 0-1背包，經(jīng)典問(wèn)題
<2>無(wú)限背包，經(jīng)典問(wèn)題
<3>判定性背包問(wèn)題
<4>帶附屬關(guān)系的背包問(wèn)題
<5> + -1背包問(wèn)題
<6>雙背包求最優(yōu)值
<7>構(gòu)造三角形問(wèn)題
<8>帶上下界限制的背包問(wèn)題(012背包)
3.線性的動(dòng)態(tài)規(guī)劃問(wèn)題
<1>積木游戲問(wèn)題
<2>決斗（判定性問(wèn)題）
<3>圓的最大多邊形問(wèn)題
<4>統(tǒng)計(jì)單詞個(gè)數(shù)問(wèn)題
<5>棋盤分割
<6>日程安排問(wèn)題
<7>最小逼近問(wèn)題(求出兩數(shù)之比最接近某數(shù)/兩數(shù)之和等于某數(shù)等等)
<8>方塊消除游戲(某區(qū)間可以連續(xù)消去求最大效益)
<9>資源分配問(wèn)題
<10>數(shù)字三角形問(wèn)題
<11>漂亮的打印
<12>郵局問(wèn)題與構(gòu)造答案
<13>最高積木問(wèn)題
<14>兩段連續(xù)和最大
<15>2次冪和問(wèn)題
<16>N個(gè)數(shù)的最大M段子段和
<17>交叉最大數(shù)問(wèn)題
4.判定性問(wèn)題的dp(如判定整除、判定可達(dá)性等)
<1>模K問(wèn)題的dp
<2>特殊的模K問(wèn)題，求最大(最小)模K的數(shù)
<3>變換數(shù)問(wèn)題
5.單調(diào)性優(yōu)化的動(dòng)態(tài)規(guī)劃
<1>1-SUM問(wèn)題
<2>2-SUM問(wèn)題
<3>序列劃分問(wèn)題(單調(diào)隊(duì)列優(yōu)化)
6.剖分問(wèn)題(多邊形剖分/石子合并/圓的剖分/乘積最大)
<1>凸多邊形的三角剖分問(wèn)題
<2>乘積最大問(wèn)題
<3>多邊形游戲(多邊形邊上是操作符,頂點(diǎn)有權(quán)值)
<4>石子合并(N^3/N^2/NLogN各種優(yōu)化)
7.貪心的動(dòng)態(tài)規(guī)劃
<1>最優(yōu)裝載問(wèn)題
<2>部分背包問(wèn)題
<3>乘船問(wèn)題
<4>貪心策略
<5>雙機(jī)調(diào)度問(wèn)題Johnson算法
8.狀態(tài)dp
<1>牛仔射擊問(wèn)題(博弈類)
<2>哈密頓路徑的狀態(tài)dp
<3>兩支點(diǎn)天平平衡問(wèn)題
<4>一個(gè)有向圖的最接近二部圖
9.樹(shù)型dp
<1>完美服務(wù)器問(wèn)題(每個(gè)節(jié)點(diǎn)有3種狀態(tài))
<2>小胖守皇宮問(wèn)題
<3>網(wǎng)絡(luò)收費(fèi)問(wèn)題
<4>樹(shù)中漫游問(wèn)題
<5>樹(shù)上的博弈
<6>樹(shù)的最大獨(dú)立集問(wèn)題
<7>樹(shù)的最大平衡值問(wèn)題
<8>構(gòu)造樹(shù)的最小環(huán)

關(guān)于算法的學(xué)習(xí)，可以看算法書籍，可以到圖書館借或者網(wǎng)上購(gòu)買，也可以直接到網(wǎng)上搜索有關(guān)算法的知識(shí) ，個(gè)人認(rèn)為有時(shí)候到網(wǎng)上搜的效果更好，因?yàn)榫W(wǎng)上經(jīng)常會(huì)提供某個(gè)算法的完整的源代碼，特別是對(duì)于初學(xué)者來(lái)說(shuō)，算法書上往往只提供算法的偽代碼，往往比較費(fèi)解。而且網(wǎng)上直接就有算法的分類和相應(yīng)的題目，；學(xué)習(xí)起來(lái)比較方便，下面大家推薦一些算法的書籍：

A原書名：The Art of Computer Programming
中文名：計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)
作者：Donald E.Knuth

B原書名：Introduction to Algorithms
中文名：算法導(dǎo)論
作者：Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein

C原書名：The Design and Analysis of Computer Algorithms
中文名：算法設(shè)計(jì)與分析
作者：Aho，Hopcroft，Ullman

D原書名：Data Structures and Algorithms
中文名：數(shù)據(jù)結(jié)構(gòu)與算法
作者：Aho，Hopcroft，Ullman

E原書名：Algorithms in C,Algorithms in C++,Algorithms in Java
中文名：算法I-IV（C實(shí)現(xiàn)），算法V（C實(shí)現(xiàn)）（C++實(shí)現(xiàn)）（Java實(shí)現(xiàn)）
作者：Robert Sedgewick

F原書名：Algorithms Design Techniques and Analysis
中文名：算法設(shè)計(jì)技巧與分析
作者：M.H.Alsuwaiyel

G
原書名：Introduction to The Design & Analysis of Algorithms
中文名：算法設(shè)計(jì)與分析基礎(chǔ)
作者：Anany Levitin

H原書名：Data Structures, Algorithms, and Applications in C++
中文名：數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用-C++語(yǔ)言描述
作者：Sartej Sahni 譯者：汪詩(shī)林等

I原書名：
中文名：算法與數(shù)據(jù)結(jié)構(gòu)
作者：傅清祥 王曉東

J原書名：
中文名：數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)
作者：嚴(yán)蔚敏 吳偉民

    **ACM=算法+數(shù)據(jù)結(jié)構(gòu)。

關(guān)于算法的學(xué)習(xí)，其實(shí)我也沒(méi)有什么特別好的經(jīng)驗(yàn)可以分享的，就談一下我學(xué)習(xí)的過(guò)程吧。我大概是從暑假集訓(xùn)的時(shí)候開(kāi)始對(duì)算法的學(xué)習(xí)，在這之前都是在oj上做一些簡(jiǎn)單題，以及高精度的題目，5月份的校內(nèi)競(jìng)賽我才對(duì)算法有了初步的認(rèn)識(shí)，記得那時(shí)做的兩三個(gè)題目都TLE了。現(xiàn)在還記得A題是求斐波那契數(shù)列，我們當(dāng)時(shí)很傻逼的寫了個(gè)遞歸，TLE無(wú)數(shù)次，賽后才知道要用到矩陣的方法。

這是第一次深刻體會(huì)到算法的重要性，我先是在圖書館借了幾本算法書來(lái)看，后來(lái)在YQ學(xué)長(zhǎng)的強(qiáng)烈推薦下買了《算法設(shè)計(jì)與分析》，王曉東的，這本書挺不錯(cuò)的，很適合初學(xué)者。其他還買了算法導(dǎo)論，C++Primer等書，陸陸續(xù)續(xù)都看了一遍，開(kāi)始的時(shí)候 做一些簡(jiǎn)單的貪心，動(dòng)態(tài)規(guī)劃的題目，比如貪心算法經(jīng)典的活動(dòng)安排問(wèn)題，最長(zhǎng)上升子序列，最長(zhǎng)公共子序列LCS等  。

后來(lái)漸漸被圖論吸引了，發(fā)現(xiàn)圖論是我搞的最多的東西了、目前為止圖論除了網(wǎng)絡(luò)流外，其他的東西我都多多少少搞過(guò)一些。還記得第一次接觸最短路的dijkstra算法，某次個(gè)人賽的時(shí)候求的是距離某個(gè)點(diǎn)第K近的路線，簡(jiǎn)單的dijkstra就可以實(shí)現(xiàn)，于是我就去看王曉東的算法設(shè)計(jì)與分析，看了很久才看懂，過(guò)了很久才把他A掉，感覺(jué)蠻興奮的；后來(lái)就開(kāi)始喜歡上圖論了。開(kāi)始研究最小生成樹(shù)prim，floyed，然后是并茶集，kruskal，二分匹配,然后就是拓?fù)渑判颉：髞?lái)對(duì)算法理解到一定程度的時(shí)候就要開(kāi)始注意對(duì)算法的深入理解和學(xué)習(xí)，比如說(shuō)求最短路dijstra算法就有很多變形，比如說(shuō)求使最大權(quán)值邊最小的路徑，二維dijikstra。比如說(shuō)floyed算法不僅看可以求最短路徑，還可以做傳遞閉包，如果求最短路如果出現(xiàn)負(fù)權(quán)邊的時(shí)候dijkstra算法就行不通了，這個(gè)時(shí)候就得用bellman_ford算法，但是bellman_ford算法效率太低，這個(gè)時(shí)候就得用優(yōu)化的SPFA算法、再比如所prim最小生成樹(shù)算法也有諸如求次小生成樹(shù)，判斷最小生成樹(shù)的唯一性等變形 。

每學(xué)一種算法的時(shí)候可以先看書或者上網(wǎng)查，搞清楚原理之后，可以從oj上找一些這類算法的簡(jiǎn)單題做，然后對(duì)這個(gè)算法比較熟了之后就可以找一些這種算法的變形等比較難的題目做。還有一點(diǎn)很重要的是要注意做好總結(jié)，沒(méi)做完一個(gè)題目可以寫下這題的解題報(bào)告，說(shuō)明用什么算法做的，要注意什么問(wèn)題，以后要看的時(shí)候比較方便。至于寫在博客還是qq空間上，或者記事本里就因人而異了。

其次，AC一道題目以后不要就這么算了了。可以跟別人對(duì)比一下代碼長(zhǎng)度，運(yùn)行時(shí)間。也可以去網(wǎng)上搜一下其他人的解題報(bào)告，看一下別人是怎么寫的。研究一下為什么別人的代碼比自己短，運(yùn)行時(shí)間比自己快；

（3） 關(guān)于編程

**編程環(huán)境

------------常有的編輯器一般有VC，devC，neatbeans等，個(gè)人比較喜歡用VC，感覺(jué)VC調(diào)試起來(lái)比較方便。下面簡(jiǎn)單介紹一下VC的調(diào)試方法：

F5----開(kāi)始調(diào)試

Shift+F5------停止調(diào)試

F10---單步調(diào)試，

F11---跟進(jìn)到所有代碼的函數(shù)內(nèi)部

Shift+F11---------從當(dāng)前函數(shù)中跳出

F9------設(shè)置（取消）斷點(diǎn)

Alt+F9------高級(jí)斷點(diǎn)設(shè)置

ctrl+F10-------運(yùn)行到光標(biāo)處

**編程的時(shí)候有一些小問(wèn)題：

（1）  一些傻逼錯(cuò)誤比如說(shuō)i寫成j，數(shù)字0寫成字母o。“==”寫成賦值符號(hào)“=”（這都是我常犯的錯(cuò)誤），注意字母大小寫。還有比如說(shuō)定義了全局變量就不要再main函數(shù)里再定義一遍了，否則就會(huì)導(dǎo)致變量重定義，出不了sample

（2）  還要注意oj上編輯器的問(wèn)題，有寫題目用C++超時(shí)，用G++卻神速無(wú)比，有時(shí)候又反過(guò)來(lái)，所以一些題目不妨用兩個(gè)編輯器都交一下。又比如說(shuō)一些涉及精度的題只有用C++交才能AC。

（3）  看到題目的時(shí)候先注意一下數(shù)據(jù)規(guī)模，是改用int，還是long或是double，數(shù)組應(yīng)該開(kāi)多大。

（4） 經(jīng)典問(wèn)題。

因?yàn)槲腋銏D論搞的比較多下面就介紹一下圖論的經(jīng)典算法吧

除了以上介紹的基本的圖論算法外，比較經(jīng)典的有：

A、         最優(yōu)比例生成樹(shù)；

B、         最小樹(shù)形圖：（其實(shí)就是最小生成樹(shù)，不過(guò)邊事有向的）

C、         強(qiáng)聯(lián)通分量

D、         啟發(fā)式搜索A*算法求最短路

E、         最小度限制生成樹(shù)

PS：這些都是比較經(jīng)典也比較難的算法，建議初學(xué)者先不要搞，等到有一定算法基礎(chǔ)的時(shí)候再來(lái)研究。

（5） 關(guān)于比賽

個(gè)人賽沒(méi)什么好說(shuō)的，說(shuō)一下組隊(duì)賽吧。開(kāi)使的時(shí)候我是和馮紅霞和張?jiān)接罱M了女隊(duì)，當(dāng)時(shí)覺(jué)得自己很菜，也沒(méi)有想去參加什么比賽，剛開(kāi)始我們是這樣分配任務(wù)的，我主攻--------圖論、搜索，Fhx主攻------字符串，模擬，zyy主攻-----數(shù)學(xué)，貪心，其他大家搞。開(kāi)始組隊(duì)賽的是候比較不正規(guī)，大家都是各自用自己的電腦做題然后提交（正式比賽時(shí)三個(gè)人一臺(tái)電腦），感覺(jué)壓力比個(gè)人賽要小很多。不過(guò)幾場(chǎng)比賽下來(lái)成績(jī)不是很理想。

后來(lái)馮紅霞由于太忙退出了ACM的比賽，羅老師就讓王碩鴻加入了我們隊(duì)員的情況。后來(lái)羅老師為我們申請(qǐng)到了比賽的名額，我們就參加了上海的regional比賽。先介紹一下我們隊(duì)的情況

隊(duì)伍名：CFZ_SG

下面介紹一下我的兩個(gè)隊(duì)友，

王碩鴻--=---主要負(fù)責(zé)計(jì)算幾何和模擬，有名的切題神速的人，大二里目前在pku上作題最多的mm。因?yàn)樽鲱}多，對(duì)dp，貪心等算法也有一定研究（除了圖論，以至于我圖論卡思路的時(shí)候沒(méi)人可以討論），coding速度較快（但是有時(shí)也會(huì)nc）。

張?jiān)接?span lang="EN-US">-------主要負(fù)責(zé)數(shù)學(xué)題，邏輯思維比較好（還是數(shù)模強(qiáng)人哦）。但是coding比較慢，做的題目比較少，代碼能力比較差。

（6）總結(jié)一下我個(gè)人的悲劇

悲劇之一

----------起步晚，大二下學(xué)期才開(kāi)始ACM 的學(xué)習(xí)，大一的時(shí)候有很多空閑的時(shí)間都不知道干什么了，大二的時(shí)候信工的課是處了名的多，導(dǎo)致很難抽出時(shí)間花在ACM上；

悲劇之二-

---------關(guān)于算法的學(xué)習(xí)沒(méi)有掌握正確的方法。對(duì)于算法沒(méi)有研究深研究透，這可能也是我們隊(duì)在regional比賽悲劇的重要原因之一。平時(shí)喜歡在pku上刷題，但是不太注意總結(jié)，對(duì)算法的理解并不深刻，不能獨(dú)立coding出來(lái)，只會(huì)套模板。上海熱身賽和現(xiàn)場(chǎng)賽的A題DFS我們都沒(méi)有出，原因就是對(duì)DFS的理解并不深刻。

（7）、關(guān)于退役

     可能是因?yàn)槊χ佳谢蛘叱鰢?guó)或者工作，我們學(xué)校的很多ACMer到了大三就退役了，如果我現(xiàn)在就退役的話，ACM對(duì)我來(lái)說(shuō)就真的是一個(gè)悲劇+慘劇，一個(gè)學(xué)期+一個(gè)暑假，唯一的regional如此悲劇，實(shí)在不甘心啊，總之有機(jī)會(huì)我還會(huì)繼續(xù)努力的，但是機(jī)會(huì)總是給有準(zhǔn)備的人，所以課余有時(shí)間我還是會(huì)努力提高coding水平的，計(jì)劃是：圖論更進(jìn)一步研究，dp，貪心，搜索繼續(xù)，模擬要加強(qiáng)。

(八)特別鳴謝

** 05級(jí)學(xué)長(zhǎng)尹慶,在我們暑假的集訓(xùn)的時(shí)候來(lái)給我們組織比賽和獎(jiǎng)?lì)}.,包括個(gè)人賽組隊(duì)賽,和網(wǎng)絡(luò)賽.,強(qiáng)烈建議學(xué)校聘請(qǐng)yq做ACM的指導(dǎo)教練...

**教練羅老師,感謝羅老師為我們爭(zhēng)取到了去東華的名額,給我們這次鍛煉的機(jī)會(huì)…

**ssjia  因?yàn)楦杏X(jué)比較面善，所以經(jīng)常問(wèn)他算法上的問(wèn)題，幫我解決了不少疑問(wèn)….

**ben1222 可以說(shuō)是入門teachar吧….

**隊(duì)友sh和zyy，特別是sh，陪我度過(guò)了暑假集訓(xùn)的美好時(shí)光，讓我更加體會(huì)到了ACM的無(wú)窮魅力……