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