首先，我想說的就是，我是一個很普通的ACMer，高中沒有參加過任何計算機和數學競賽的經歷，也沒有ben那樣過人的天資，努力至今也未能取得什么成績，我之所以寫下這篇文章，只是希望給剛進大學或者剛進ACM隊的同學一點小小的幫助，希望你們可以少走一些彎路，更希望你們可以幫助華理取得我沒能取得的輝煌。
(1).起步階段
我是從大二開始接觸ACM的，要說基礎的話就是大一的C語言課程了，語言方面的基礎也弱，不過ACM起步階段對于語言的要求并不是太高，只要掌握了學校C語言的課程，基本就可以開始你ACM的歷程了，不過這也僅限于開始的時候，當你的ACM學到一定程度的時候，每道題的代碼長度也會越來越長，你會發現一些C++的語言特性可以極大得簡化你的代碼長度及思路，而且C++本身就是一門非常重要的語言，啃下C++無論是對于ACM水平的提高，還是為后繼Windows編程打下基礎，都是有極大的幫助的。至于很多人所遇到的所謂“不知如何開頭”的問題，我也想談談我的看法，首先你需要做的就是把PKU上一些最基礎的模擬題敲一下，為什么呢？對于一個過去沒有接觸過編程的人來說，模擬題可以在相當程度上幫助你提高的編碼能力，這里的編碼能力，即將你的想法或者說是思路，在盡可能短的時間內，用盡可能優美的代碼去完全正確地實現它，至于何為優美，我想在你學習的過程中你會慢慢體會到的。這里你可能要問了，去哪里找那么多模擬題呢？我想你只要在Google上搜索下“PKU 水題”之類的關鍵字，或者直接看下我們學校的題目分類(想要的同學可以發郵件給我問我要)就可以找到了。那么這樣的題要做多少道呢？我想，對于一個初學者來說，做上大約30道～50道的簡單模擬題就足夠了。
我從大二的暑假開始在PKU上做題，由于那個時候主要抱著一個“玩玩”的心態，根本就沒有任何比賽的打算，整個暑假邊玩邊學，基本上沒怎么接觸過算法題，也就切了幾十道最簡單的水題，直到暑假集訓結束了也沒什么長進，由于暑假最后大二的學長(那個時候我是大一)還有軍訓，所以我們這些大一的就全部回家了，回家之后就完全把ACM放到一邊了，基本就沒有碰過，這種頹廢的狀態一直持續到了大二開始后相當長一段時間，不知什么原因我又開始切題了(我真的忘記當初是為什么又開始切題了)，并且開始接觸各種基礎算法了，剛開始的時候確實比較痛苦，但靠著天哥和ben牛的幫助以及上網看別人的解題報告總算摸爬滾打做了200道題左右，這個時候大二上差不多已經要結束了，而我由于要出國的原因在寒假中參加了新東方TOEFL的培訓班，ACM又被我“正當理由”放到了一邊，而且整個寒假幾乎都沒有碰過。而大二下學期開學后我又復習了一段時間TOEFL，直到考試結束我才又開始了切題的生涯，其實從嚴格意義上來說，知道這個時候我才開始了真正意義上有計劃的且比較刻苦的ACM訓練，一直訓練到了上海邀請賽的時候。這是我參加ACM以來參加的第一次比賽，也是我第一次用自己的眼睛確認了自己和別人之間的差距，這場比賽給我的震撼很大，一樣是大學生，一樣的年齡，但是差距卻如此之大，確實令人深思。知道這個時候我才真正意識到了自己曾經浪費了多少的時間，意識到了自己的水平竟然和別人有那么大的差距。這之后不久，大二的暑假集訓就開始了，這兩個月是我搞ACM以來進步最快的一段時間。下面，我就想把自己的一些做題的經驗和感受告訴大家，希望能對大家有幫助。
(2).做題要點
首先，我認為最重要的是獨立思考和敢于嘗試，所謂的獨立思考，就是不要養成做不來就上網搜別人代碼的習慣，如果實在做不出來，可以嘗試問一下別人思路，然后再嘗試自己去實現，等做出來之后再看別人的代碼，學習一些好的地方。而所謂的敢于嘗試，就是不要怕錯，編程是一件很特別的事情，他可以在當場驗證你的理論的正確性，所以，不要把錯藏在心里，打開電腦自己試下，自然就明了了，也只有這樣，你才能從自己完成的每一道題中獲得快樂。其次，就是要寫解題報告，把自己在這道題中學到的知識和碰到的問題記下來，并經常梳理總結自己學過的知識，把他們聯系在一起。當你堅持到這里的時候，我想和你說，你是好樣的，但是，還請你繼續堅持下去，因為ACM中真正的樂趣才剛剛開始，也就是算法。我想，包括我在內的大部分初識算法的同學都會感到非常的迷茫，因為就我的經歷來說，我是幾乎每拿到一道題，大部分情況下都是一點沒有思路，難得有點思，寫了老半天還可能是錯的，我想，碰到這種情況的你完全不必擔心，因為有相當一批人都是和你一樣的，同時，在他們當中也有很多的人成為了相當出色的ACMer，當然了，這也是在他們付出了相當的努力之后才取得的結果。所以，我相信，只要你堅持下去，終會有收獲的一天的。那么在下面一大點中，我想說下你們要攻克的幾個最主要的方面。
(3).動態規劃(Dynamic Programming,以下簡稱DP)
俗話說，要看一個人的算法水平，只要看一下他做DP題的水平就OK了，而在ACM這個多變的賽場上，幾多算法沉浮，唯有DP幾乎從未消失過，如果你問我什么類型的題在賽場上出現的概率最高，我可以毫不猶豫地告訴你，是DP。由此也可以看出，DP的地位有多么重要，那么這樣一個幾乎每場比賽都會出現的題型，應該很難啊，為什么要讓我們從DP入手呢？確實，DP是很難，其變型之多，覆蓋知識面之廣，確實讓人望而生卻，但是，我想說下如何入門DP題。首先是DP幾個最為基本的模型，LCS(最長公共子序列)，LIS(最長上升子序列)，最大公共子段和，數塔問題，矩陣連乘等幾個最為經典的問題，大家一開始的時候可能難以理解DP中自底向上，重疊子結構等基本思想，對于這幾道問題可以先看一下別人的代碼和書上的講解，然后再自己反復地理解，理解了之后再自己敲一下代碼，如果有地方實在不理解，可以先放一下，去看看其他題，回過頭來再想一下以前的題，也許會有豁然開朗的效果。吃透了DP的幾個經典問題之后，就可以做一下這些經典問題的變型了，比如最大公共子段和的變型——最大子矩陣和最大m子段和，最長公共子序列和最長上升子序列的變型——最長公共上升子序列等等。并且可以嘗試接觸DP的一些重要的應用，最重要的要數背包問題，背包問題是DP一個很大的分支(算是分支吧，我找不到其他更好的詞來形容他了)，同樣也有非常多的變型，如最為基礎的01背包，以及擴充出去的多重背包，完全背包，分組背包，樹型DP(這個知識點我待會會介紹)中應用非常多的泛化背包等等，下面我把最為基本01背包，多重背包和完全背包講一下，首先是最簡單的01背包，偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{ f[v], f[ v-c[i] ] + w[i] }
這里為什么要倒推呢？其實道理很簡單，因為這里其實是利用類似滾動數組的概念，只不過他連2個數組都不用開了，只需要開一個數組就可以了，這是為什么呢？因為傳統的二維數組中f[i][v]的值是由max( f[i-1][v], f[i-1][ v-c[i] ] + w[i] )得來的，所以每次f[v]的值是由上層循環中f[v'](v’<=v)得來的，所以改成了一維數組后，如果從小到大循環的話，在計算完成f[v] 之后，就會在計算f[v'](v' >=v)時發生錯誤，因為原本計算f[v']所需的上層循環中的f[v]的值已經被新的值覆蓋掉了，故必須從大到小循環。其次是多重背包，完全可以化為01背包問題，不過是把相同價值的同種類物品看成多個價值相同的不同種類物品，即比01背包多了一重循環，要注意的是這兩層循環都要從大到小，原理和01背包類似。最后是完全背包問題，偽代碼如下：
for i=1..N
for v=0..V
f[v]=max{ f[v], f[ v-c[i] ] + w[i] }
這個偽代碼與01背包的偽代碼只有v的循環次序不同而已。為什么這樣一改就可行呢？首先想想為什么01背包中要按照v=V..0的逆序來循環。這是因為要保證第i次循環中的狀態f[i][v]是由狀態f[i-1][v-c[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據的是一個絕無已經選入第i件物品的子結果f[i-1][v-c[i]]。而現在完全背包的特點恰是每種物品可選無限件，所以在考慮 “加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結果f[i][v-c[i]]，所以就可以并且必須采用v= 0..V的順序循環。這就是這個簡單的程序為何成立的道理。這里我向大家推薦一下浙江大學的DD牛所寫的《背包九講》，是背包入門及提高的最為經典的資料。現在就要講一下樹型DP了，樹型DP其實就是DP，只不過是建立在樹模型之上的DP罷了，不過樹型DP說起來雖然簡單，確是DP中相當困難的一個知識點，要好好理解，多做些題才行。最后是狀態壓縮DP，這也是一個DP的一個難點，所謂的狀態是指利用二進制或者其他進制的數來表示狀態從而達到空間上壓縮的目的，這一類的狀態設計一般都很巧妙，而且涉及的眾多位運算對于編碼能力也是一個相當大的挑戰，介于狀態壓縮DP是用記憶化搜索(所謂記憶化搜索，是DP的另外一種遞歸的實現形式，即所謂的自頂向下)來實現的，又要牽涉到搜索的知識點，建議等學習了相關的內容之后再回過來頭來學習這個知識點。狀態壓縮的經典題有棋盤覆蓋問題，炮兵陣地等。
(4).搜索(包括DFS, BFS, A*)
搜索也是ACM中相當重要的一個組成部分，涉及范圍也是相當之廣，首先是最為基礎的深度優先搜索DFS，所謂的DFS，其實就是通過遞歸的方式枚舉所有的可能從而得到我們想要的結果，而搜索中相當重要的一個技巧就是剪枝，即人為地刪去一些沒有必要搜索的可能，從而提高我們程序的效率，DFS的經典題有最為著名的八皇后為題，Sticks等等。其實DFS的題實在是太多了，PKU上有很多的題可以供我們練手。另外一個就是廣度優先搜索(BFS)了，廣度優先搜索是基本思想就是建立一個隊列(隊列是一種基本的數據結構，我會在下一部分中說明)，然后每一次都拿出隊列出的一個點擴展出所有的可能，再把我們需要的解放入隊列等著下次再擴展，一直擴展到找到答案或者不能擴展為止，BFS的經典題有跳馬問題，八數碼等。BFS有一個非常常用的技巧或者說是優化，就是雙向BFS，思想是一樣的，就是同時從起點和終點開始擴展，等到出現交點的時候就意味著找到了答案，這樣比起普通的BFS可以節省大量的空間和時間。BFS還有另外一個常見的擴展，就是優先隊列BFS，所謂的優先隊列(優先隊列是隊列的一種實現，我同樣會在下一部分中給出解釋)，就是始終都保持隊列的隊首元素是最小的，這樣每次擴展的就是當前最小的元素了，這里所謂的最小，其實指的是當前看來最優的解，利用這么一種貪心的方法，來加快我們搜到答案的速度，當然了，具體的效率還要看題目的數據。說了這么多的優先隊BFS，其實就是A*的一種特殊情況，A*的中文名是啟發式搜索，是人工智能中常用的一種搜索技術，A*最基礎的應用就是求最短路，通過某個估價函數對當前的點做出一個價值評估，然后將這些擴展出來的點按照其價值放入一個優先隊列中，那么我們每次拿出的隊首元素不就是我們當前最優希望的一個點嗎？如果用STL(C++的標準模板庫，同樣會在下一部分中給出解釋)來實現優先隊列的話，A*比起BFS的代碼量幾乎沒增加，無非多了一個估價函數，但是問題就在于如何更好地設計出一個估價函數，A*的經典題有貪吃蛇，八數碼。
(5).C++應用之STL
STL是C++的標準模板庫，為我們提供了相當多的現成的庫函數和數據結構，STL即可以極大地縮短我們的代碼長度，有可以極大地降低我們出錯的概率。那么你可能就奇怪了，為什么我還會恨STL呢？理由很簡單，我們必須要付出相當大代價，那就是效率。下面我簡要地介紹一下STL在ACM中的簡單應用。首先就是STL中的庫函數了，其中我們有我們最為常用的sort排序函數，有find，lower_bound和upper_bound等一些查找函數用來簡化我們的代碼，另外最常用的就是順序容器和關聯容器了，其實順序容器可以相當相當程度上代替一些常用的基礎數據結構如vector可以代替長度可變的數組(可以簡單地實現鄰接表)，list可以代替鏈表，stack可以代替棧，deque可以代替雙端隊列，priority_queue可以代替我們前面提到的優先隊列，而關聯容器中的map可以實現任意兩種類型的數據之間的索引，而set可以查找某個集合中是否存在某個元素。
(6).數據結構之基礎篇
數據結構在ACM中應用非常廣泛，但單獨考查某個數據結構基礎的題目較少，一般都是起一些輔助的作用，比如我們前面提到的優先隊列，還有一個非常常用的就是哈希，前面我們提到過，在BFS的過程中，我們需要從每次擴展出來的點中篩選出來我們需要的點放入隊列中，哪些是不需要的點，一般來說，指的是和以前某個搜索過的點具有相同的狀態的點，而判別狀態是否相同的方法經常是利用哈希來保存以前搜索過的狀態，并且判斷每次擴展出來的點的狀態是否已經存在，如果不存在，我們再把它放入隊列中。
(7).數據結構之提高篇(包括并查集,樹狀數組,線段樹)
數據結構還有一些相對來說比較高級的應用，這些知識點可能會作為一個知識點單獨考查，首先是并查集，并查集的基本思想是在一個集合中選出一個元素作為一個集合代表元素，通過對這些代表元素的操作來實現集合之間的合并操作，在求最小生成樹的經典算法Kruscal中也會用到并查集來判斷兩個元素是否屬于同一條邊，這在下一部分圖論的總結中會提到。并查集也有很多的題目可以做，經典題有食物鏈，搞同性戀的蟲子，幫派結伙等，并查集還有一個變型就是從一個集合中刪除某一個元素，我們知道，普通的并查集是不包括刪除元素的功能的，而刪除元素的實現其實也很簡單，就是對每個點都建立一個索引，一開始每個點的索引都指向自己，當一個元素被刪除掉的時候，先建立一個新的不屬于任何集合的新點，在把被刪除掉的點索引到那個新點之上即可。第二部分是樹狀數組，他支持在O(nlogn)的復雜度內算出區間內的元素之和，他的思想很是巧妙，就是樹狀數組總結：假設c[]為樹狀數組，a[]為原數組，則兩者之間存在這么一個關系，c[i]代表的意義是從a[i]開始往前2^k個元素的和(k為i化成二進制后尾部包含的0的個數)。由位運算的性質可以得到：對于i來說，i&(-i) = 2^k，那么樹狀數組的基本功能就能明白了。樹狀數組也有比較多的題，PKU_1990，PKU_2828，PKU_2155等等。最后我想說一下線段樹，線段樹是一個非常強大的數據結構，他支持在O(nlogn)的復雜度內對區間范圍內的元素進行修改，刪除等操作，和并查集，樹狀數組不同的是，線段樹的實現非常靈活，一道題一個樣，幾乎沒有什么定式，當然了，最為基本的思想就是每個節點代表一個區間，他的左右子樹分別為左半區間和右半區間，如此這般地遞歸定義，直到為一個點或者包含一個單位為止。線段樹也有幾個基本模型和經典例題，首先我想講的是線段樹的一種相對而言比較簡單但是非常經典的應用來引入線段樹的概念等一系列問題，即染色問題。以PKU_2777為例，題目大意是有一塊長度為L厘米的板，每厘米可以看成一個單位區間，顏色的種類由數字表示，一開始每個區間的顏色都是1，而現在要對這種樹進行O次操作，操作有兩種，第一種是將區間A到B的顏色都染成C顏色，第二種是詢問區間A到B之間一共有幾種顏色。最簡單的想法可能是開個長度為L的數組a[]，而a[i]存的就是第i格的顏色，但是可行嗎？我們來看下數據范圍，L的范圍是十萬，O的范圍也是十萬，那么算法復雜度就是O(LO)，明顯會超時，所以我們選擇用線段樹來幫助我們解決這個問題，其實線段樹這個名詞并不能很好地闡述它強大的功能，我更喜歡他的學術名詞——區間樹，同其他的樹一樣，他可以在O(logL)的時間內對樹進行維護操作，這也就意味著他可以在O(logL)的時間內對一段區間進行一系列的操作。正是線段樹這種高效，讓他在RMQ問題，以及求矩形合并面積，周長等一系列問題中得到了充分的應用。這里我想講一下RMQ問題(即求區間內最大or最下值的問題)，眾所周知，RMQ問題有一種O(NlogN)的預處理以及O(1)時間求出任意區間內最大or最小值的離線算法（所謂離線，即不能在求的過程中動態地改變或者插入區間的值），即ST(Sparse Table)算法，相比之下，線段樹并沒有效率上的優勢，但ST算法有個局限性，就是不支持在線操作，而線段樹則沒有這種限制，由此可知，線段樹的強大。線段樹還有一個高級的應用就是對于區間最值信息的維護，相應的經典題有很多，也有一定的難度，PKU_2482，PKU_1151(求n個矩形合并后的面積)，PKU_1177(求n個矩形合并后的邊界周長)等等。最值的維護要抓住的基本思想就是遞歸地維護每一顆子樹，利用子樹的信息去維護父親。
( 8 ).字符串(包括KMP算法,Trie樹,后綴數組)
字符串處理也是ACM中相當大的一塊知識面，而且也具有相當的實際應用面，其實對于字符串的知識我自己接觸的也比較少，所以只能簡單地談一下幾個最為基礎的算法，KMP算法是兩串匹配最為基礎的線性算法，該算法的核心是對于next數組的理解，該數組是對于一個串進行了預處理得到的，從而成功將兩串匹配的復雜度降到了線性。但KMP算法只能是兩串之間的匹配，如果我們要多串匹配的話該怎么辦呢？Trie幫助我們解決了這個難題，Trie其實是一顆字母樹，樹的每個節點都有26個英文字母，通過對這些節點的進行標記來插入一個字符串，在插入了n個字符串之后，我們就可以同時對這n個字符串之后我們就可以同時對這n個字符串進行匹配了，Trie樹有一個很大的缺點，就是他所需要的空間是指數級別的，所有一般來說字符串的長度超過15的話我們就應該考慮別的方法了。最后是后綴數組，算法的主要精髓在于對于height數組的理解和應用，在國家隊論文中有兩篇文章是專門介紹后綴數組的，我這里就不贅述了。
(9).圖論(包括最短路,最小生成樹,強連通分量等知識點)
之所以把圖論的內容放在最后講完全是因為圖論的知識點實在是太多了，涉及的方面也實在是太廣了，我這里挑幾個我題目做得比較多的方面來簡單總結一下。首先就是最短路了，主要分為多源最短路，用的算法是非常經典的Floyd算法，復雜度為O(n^3)，實現起來相當簡單，主要就是DP的思想。還有單源最短路，最原始的方法是Bellman-Ford，但該算法使用的概率不高，因為他有一個非常好的替代品，就是SPFA，SPFA的實現有點類似廣搜，代碼也非常短，對于Bellman-Ford求一個圖中是否存在負環的問題可以以完全地替代，另外在稀疏圖中求最短路的效率甚至要高于用了優先隊列優化過的Dijkstra，確實是一個實用的好東西。當然了，最為著名的Dijkstra算法是絕對不能不提的，該算法是我們求最短路時最常用的算法，但是由于他利用了貪心準則，所以一定要注意Dijkstra不能處理有負權邊的圖，而Dijkstra也有幾個非常經典的變型，一個是將Dijkstra擴展到二維來求次短路，另一個是利用A*來求次短路，大家是否注意到，學到后面的時候，不同知識塊之間的分界已經越來越不清晰了，因為我們的腦中正在逐步形成一張知識網，將每一個知識點都有機地串聯到了一起。第二個大點是最小生成樹，該類問題也有兩個廣為人知的算法，適用于稠密圖的Prim算法和適用于稀疏圖的Kruscal算法(該算法中要用到并查集的算法)，最小生成樹同樣有一些經典的變型，如次小生成樹，最小限制度生成樹等。再有一類非常重要的問題就是二分匹配問題，該問題涉及的知識點也是相當的多，求無權二分圖的最大匹配有最為經典的匈牙利算法以及求帶權的二分圖的最小/大匹配的KM算法，而由不帶權的二分圖的最大匹配數衍生出去的知識點有最小覆蓋問題，最小路徑覆蓋問題等等，這塊內容概念性比較強，其實說起來，圖論最大的特點就是概念性強，變型極多，如果不深入地理解每一次問題及其經典算法，著實無法應變。最來就是歐拉回路問題，該類問題比較簡單，無非就是兩種，一個是判斷圖中是否存在歐拉回路，再一個就是求出該歐拉回路中的一條，實現起來也很簡單，一個DFS就可以完成了。還有就是強連通分量，該算法的核心就是對一個圖求強連通分量后縮點，從而將一個圖轉化成一個有向無環圖，從而方便我們進行接下去的操作。最后一個大塊就是網絡流了，該內容我涉及也比較少，主要就是幾個求網絡流的經典算法，如HLPP，ISAP，EK等等，網絡流的變型也非常地多，需強加練習。
(10).ACM最終回之比賽篇
我參加過的正式比賽有兩場，一場是大二下的上海邀請賽，另一場是大三上的合肥區域賽，由于水平有限，終究還是只拿了兩塊銅牌，下面我想談一下組隊的個人感受，首先是隊員的構成，至少要有一個編碼能力較強的人主要負責敲代碼以增加出簡單題的速度，另外就是數學基礎較強的人，由于ACM現在越來越喜歡出數學題，而且數學好的往往思路會比較開闊，可以為整個團隊提供想法，再有一個就是算法接觸比較廣的人，這一類的人接觸的算法比較多，切題數也比較多，雖然可能沒有哪個方面特別強，但其豐富的做題經驗保證了他對于一道題的算法嗅覺，可以為整個團隊指明方向。說到這里，我的總結也要結束了，希望大家可以從中可以獲得幫助。