轉(zhuǎn)這篇文章不是說做ACM的有多牛B，只是想說對于每個(gè)ACMer來說切忌浮躁，踏踏實(shí)實(shí)的做好每一步才是成功之道。
做算法和作技術(shù)哪個(gè)難? 都很難, 沒有可比性. 但是算法做得好的可以轉(zhuǎn)行做技術(shù), 技術(shù)做得好的想轉(zhuǎn)行做算法卻很困難.
我是08年下半年將近期末的時(shí)候加入華理ACM隊(duì)的. 我高中的時(shí)候沒有編程經(jīng)驗(yàn), 數(shù)學(xué)也不好, 高考數(shù)學(xué)剛及格. 因?yàn)榈诙I(yè)大學(xué)的網(wǎng)絡(luò)工程專業(yè)的分?jǐn)?shù)是最低的, 所以就比較巧合地步入了計(jì)算機(jī)行業(yè). 大一有一門C++課程, 當(dāng)時(shí)我在第一次上機(jī)的時(shí)候就深深的被C++迷住了. C++是一門極其優(yōu)美的語言, 相比于高中計(jì)算機(jī)課上一筆帶過的VB, 我最喜歡C++的花括號(hào). 因?yàn)閷W(xué)校比較差, 周圍的學(xué)生沒幾個(gè)專心讀書的, 所以對于一個(gè)稍微想要學(xué)點(diǎn)東西的學(xué)生來說, 這樣的學(xué)校里的硬件資源就顯得異常豐富了, 圖書館里很多計(jì)算機(jī)經(jīng)典書都是新的, 而且自修室人也很少, 整個(gè)大一除了談?wù)剳賽劢饨鈵炓约芭闶矣汛虼蚰ЙF以外, 我大多數(shù)時(shí)間都在圖書館或者自修室, 雖然在那里的時(shí)候不總是做些學(xué)習(xí)方面的事情...我也會(huì)經(jīng)常無聊的在網(wǎng)上亂逛或者到處下載資料做收藏家. 但正是這個(gè)時(shí)候我接觸到了C++的圣經(jīng)[The C++ Programming Language], 當(dāng)時(shí)我看了一段時(shí)間的電子版, 因?yàn)椴环奖阕鞴P記, 很不爽, 于是在08年1月的時(shí)候買了中譯本. 之后的大一下學(xué)期我又陸陸續(xù)續(xù)看了部分[Effective C++], [More Effective C++], 還有一些數(shù)據(jù)結(jié)構(gòu)方面的東西. 然后學(xué)期中期的時(shí)候我集中精力做了一段時(shí)間的數(shù)學(xué)建模競賽. 大一結(jié)束的時(shí)候我通過插班生考試從第二工業(yè)大學(xué)轉(zhuǎn)來華理, 很不巧, 插班生考試數(shù)學(xué)又是剛及格. 在暑假期間我去上了CCNA和CCNP的部分課程, 因?yàn)楦杏X這種純操作工一樣的"背誦"活很不適合我, 于是半途而廢了, 暑假在家的時(shí)候做了很多windows下的網(wǎng)絡(luò)編程, 自己寫發(fā)包程序, 寫SYN攻擊很有意思.
大二剛來到華理的時(shí)候自我感覺很牛B, 因?yàn)槲易詫W(xué)過的東西幾乎都沒有人能來跟我做做討論. 于是我自以為很了不起, 也沒怎么在意學(xué)校的課程, 除了上課, 平時(shí)我?guī)缀醵荚趫D書館或者自修室. 這期間我接觸了設(shè)計(jì)模式, 以及.NET開發(fā). 大約在開學(xué)不久, 08年的Regional還沒有開始的時(shí)候, 我聽說了ACM這種東西. 當(dāng)時(shí)對這個(gè)東西我是完全沒概念的, 在某個(gè)晚上我去奉賢311找了羅老師, 當(dāng)時(shí)詠天也在, 是ACM隊(duì)準(zhǔn)備召新的時(shí)候, 羅老師跟每個(gè)同學(xué)談了話, 我是最后一個(gè), 跟他嘩啦啦地說了很多以前我看過的書, 做過的東西. 被羅老師贊賞了一番之后我更加自以為是了, 并以非正式的身份進(jìn)了ACM隊(duì).
但是直到學(xué)期結(jié)束, 我也沒做什么題. 學(xué)期將盡的時(shí)候我跟室友展開了一個(gè)舊書交 易網(wǎng)站的建設(shè), 然后我就一股腦地完全投入進(jìn)去了, 用了將近五個(gè)月的時(shí)間, 其中占用了我整個(gè)寒假, 我用ASP.NET+Spring.NET框架寫了一個(gè)自以為有很高技術(shù)含量的簡單的舊書信息發(fā)布平臺(tái), 全站單頁面, 無刷新, 所有操作都用AJAX技術(shù)完成, 并且我自己設(shè)計(jì)了一個(gè)貌似很牛B的內(nèi)存數(shù)據(jù)庫. 結(jié)果在09年的上海市計(jì)算機(jī)應(yīng)用能力大賽中, 我的作品只獲了一個(gè)優(yōu)勝獎(jiǎng). 貌似還有很多同學(xué)沉迷于這些, 以為這就是編程. 備受打擊的我在迷茫了一陣子之后想起來ACM, 于是在大概3月底的時(shí)候開始在PKU切題.
以上都是之前的一些學(xué)習(xí)經(jīng)歷, 關(guān)于ACM的部分從這里開始.
ACM是個(gè)很有意思的東西. 起初, 我有點(diǎn)看不起這個(gè)東西, 相信很多過早接觸技術(shù)開發(fā)方面的同學(xué)都有這樣類似的想法, 于是就有了諸如"做算法和做技術(shù)哪個(gè)難"的問題. 今天再讓我來回答這個(gè)問題的話, 我只能說, 都很難, 并且沒有可比性. 但是我要補(bǔ)充一點(diǎn), 大學(xué)生可以做技術(shù), 不上大學(xué)同樣可以做技術(shù). 再要我說得明白一點(diǎn)的話就是, 一年前我用了將近一個(gè)星期的時(shí)間, 看著MSDN和CSDN寫了一個(gè)windows下的掃雷程序, 并且在之前我用了若干個(gè)星期積累了SDK編程的一些知識(shí), 而今天雖然我已經(jīng)忘記了幾乎所有SDK編程的細(xì)節(jié), 不知道怎么去畫一個(gè)自定義的按鈕, 但是給我一臺(tái)能上網(wǎng)的電腦和一天的時(shí)間, 我能把當(dāng)時(shí)的那個(gè)掃雷程序?qū)懗鰜? 并且讓它的代碼量精簡掉一半以上.
另外一個(gè)事實(shí)就是, 絕大多數(shù)的ACMer以及幾乎所有成功的ACMer的數(shù)學(xué)都非常好, 不論他們是原來就很好還是后來變得很好.
以下說一些實(shí)質(zhì)性的東西.
編碼能力
在ACM的世界里, 編碼能力和數(shù)學(xué)功底是絕對的王道, 硬要分個(gè)先后的話, 編碼能力就是王道中的王道. ben在學(xué)校的時(shí)候幾乎不看算法類書籍, 最多也就是看看網(wǎng)上零散的知識(shí)點(diǎn), 但是他的成績是大家有目共睹的, 其中最重要的一點(diǎn)就是他的編碼能力至少在華理, 那是令人發(fā)指的強(qiáng). 寫一個(gè)容斥原理你要多久? 或者給你入射光和球的相關(guān)參數(shù), 要你編碼求出反射光的運(yùn)動(dòng)參數(shù), 你又要寫多久? 更有甚者, 在今年暑期的個(gè)人賽第一場最后一題, 給你一個(gè)掃雷過程中的狀態(tài), 要你計(jì)算出所有能夠確定的雷, 這題ben用了不到半個(gè)小時(shí)就AC了.
今年的上海賽區(qū)同樣對編碼能力要求很高, 其中我們沒有過的I題, 當(dāng)時(shí)ben打印出來的代碼有4張紙, 也正是因?yàn)檫@么長的代碼, 我跟sky連去糾錯(cuò)的信心都沒有, 結(jié)果ben自己也沒有能夠在賽場上把錯(cuò)誤找出來.
編碼能力的培養(yǎng)的捷徑就是做題, 尤其是搜索, 模擬, 計(jì)算幾何等類型的題目尤其鍛煉編碼能力. 我能夠很快適應(yīng)ACM, 很大程度上也是得益于大一期間積累的編碼能力和C++語言基礎(chǔ).
在鍛煉編碼能力時(shí), 特別要注意做題要限制時(shí)間, 這點(diǎn)跟自己做一些小項(xiàng)目, 小程序完全不同, 不能拖拖拉拉一做就是幾天. 最好的方法是在寫代碼的同時(shí)把自己做這題的開始和結(jié)束時(shí)間都標(biāo)注上去, 這點(diǎn)在后面關(guān)于解題報(bào)告的部分我還會(huì)說到. 如果覺得有時(shí)自己會(huì)記不住記錄開始時(shí)間, 那就養(yǎng)成一個(gè)習(xí)慣, 每看到一題就先隨便submit幾個(gè)字母, 讓它CE一次, 這樣以后再回過頭來看歷史記錄就可以知道自己做這題用了多少時(shí)間了. 限制做題時(shí)間又一個(gè)很明顯的作用就是可以自我認(rèn)識(shí), 即了解自己對于某一方面的知識(shí)掌握程度, 如果平時(shí)遇到某一類型的一般題目(沒有特別惡心的trick, 沒有特別惡心的輸入), 自己需要花超過2個(gè)小時(shí)去AC, 那么就幾乎可以肯定你在賽場上是不太可能把這題做出來的, 換句話說, 如果你在賽場上遇到這種類型的題目就可以暫時(shí)先放一放了.
編碼能力的一個(gè)很關(guān)鍵的地方就是編碼風(fēng)格問題, 一些普遍適應(yīng)的原則諸如"不要把復(fù)雜的語句寫在[]里", "不要在if里寫復(fù)雜的語句", "把if里復(fù)雜的邏輯拆分開", "全局變量要特殊命名"等等, 這里不可能一一列舉, 唯一的辦法就是每次自己在這里吃到苦頭的時(shí)候把它記錄下來. 具體的可以參考ben的方法, 例如把PKU的每次提交情況都粘貼進(jìn)一個(gè)文本文件里, 然后在每次提交記錄后面都加上一些注釋, 比如"++i寫成i++", 或者"dis數(shù)組忘記初始化"之類的東西, 這樣即使不能保證此類錯(cuò)誤以后不會(huì)再犯, 也至少可以降低你犯此類錯(cuò)誤的概率. 關(guān)于降低犯錯(cuò)的概率還有一個(gè)生理學(xué)上的解釋, 即記憶的編碼并不是純粹的把東西原封不動(dòng)地放進(jìn)腦子里, 而是會(huì)被我們的神經(jīng)系統(tǒng)先分解, 儲(chǔ)存在大腦各處, 并且其中夾雜了大量記憶的場景, 即記憶發(fā)生時(shí)的環(huán)境. 當(dāng)我們再次處于類似的環(huán)境時(shí)就有更大的概率把相關(guān)的事情回憶起來, 所謂的聯(lián)想記憶也是這么一回事. 所以當(dāng)我們犯錯(cuò)誤時(shí)就應(yīng)該盡可能地增加可以勾起我們回憶的材料, 比如寫下一些箴言形式的語句加深記憶.
解題報(bào)告
上面說到錯(cuò)誤記錄可以降低我們犯錯(cuò)的概率, 同樣的, 解題報(bào)告也是基于這一原理, 并且它往往比錯(cuò)誤記錄更加有效.
我們常?？梢钥匆娨恍┐笈log上的學(xué)術(shù)類文章寫得非常風(fēng)趣, 有時(shí)里面會(huì)參雜一些很搞笑的例子, 于是他們的文章較之純理論的文章更容易被我們記住. 這仍然是基于上述的生理學(xué)原理, 我們用來會(huì)議的材料越豐富, 或者這些材料越投我們所好, 我們就越容易聯(lián)想起來與這些材料相關(guān)的東西. 這個(gè)原理應(yīng)該用到些解題報(bào)告上來, 那就是盡量把自己關(guān)于這題的, 一些有意思的想法記錄下來. 另外, 記錄自己在解決這題時(shí)的思維過程也是非常有益的. 如果你還不知道思維過程的重要性, 那么請去看看波利亞的[How To Solve It](中文譯名"怎樣解題"), 這是每一個(gè)理工科學(xué)生的必讀讀物之一, 甚至你可能會(huì)在看完此書的若干年以后才會(huì)突然體會(huì)到其中的一些條款的極端正確性, 所以, 越早看這本書越好.
關(guān)于思維過程, 并不是十分容易被記錄下來, 并且, 在你能夠明明白白把你對于某題的思維過程敘述出來之前, 你對于這題的解決始終都是不完整的, 即下次遇到此類題目的變種, 十有八九還是無從下手(某些大?？赡芤?yàn)檎Z文水平不足而無法很好用語言表達(dá), 這是特例...).
寫解題報(bào)告的另一個(gè)好處當(dāng)然是有助于自己復(fù)習(xí). 尤其是在比賽之前看看解題報(bào)告是非常有益的, 一般情況下, 就拿我來說, 在兩個(gè)月內(nèi)做過的題目, 只要掃一眼解題報(bào)告, 一般我能馬上把它原樣地用代碼實(shí)現(xiàn)出來.
如果不是很確定自己能堅(jiān)持寫解題報(bào)告, 或者擔(dān)心自己的解法的正確性(很多時(shí)候AC了的代碼不一定是正確的), 那么就去寫blog吧, 把解題報(bào)告貼到blog上吧, 也許會(huì)有人用很尖銳的言語指出你的錯(cuò)誤, 但, 那不正是你想要的嗎? 另外貼到blog上也方便了自己日后的搜索.
關(guān)于圖論
論資格, 我絕對在ACM隊(duì)是派不上號(hào)的, 切題數(shù)也十分寒酸, 于是當(dāng)你處于這種情況的時(shí)候就應(yīng)該考慮主攻某一方面, 畢竟ACM是一項(xiàng)團(tuán)隊(duì)比賽, 一把瑞士軍刀總也沒有幾把專業(yè)的刀具功能強(qiáng)大. 我在隊(duì)里主要負(fù)責(zé)的是圖論, 所以我在這里著重說一下圖論方面的東西.
ACM題目類型主要分為DP, 圖論, 搜索, 數(shù)據(jù)結(jié)構(gòu), 模擬, 計(jì)算幾何, 字符串, 組合數(shù)學(xué), 數(shù)論等, 其中前兩個(gè)是重頭戲, 我做過的每場比賽里, 前兩種題目都是必然會(huì)出現(xiàn)的, DP很大程度上需要依靠YY, 即它與IQ的關(guān)系很大, 這幾乎是一個(gè)毋庸置疑的事實(shí)...并且DP的某些思想貫穿大部分ACM題目, 很容易于其它類型題目融合起來, 想要掌握它非一朝一夕之事. 而圖論相對來說并沒有DP那么可怕, 比較容易入門, 并且很多圖論類題目可以套模板, 但是相對的, 圖論題目也可以出得令人發(fā)指的難, 并且其數(shù)學(xué)模型往往隱藏在搜索, 計(jì)算幾何, 字符串等類型的題目后面, 即表面上看起來不是圖論, 但實(shí)際上這題考的卻是圖論原理.
圖論的變形繁多, ACM題目中尤以Dijkstra最多, 看似簡單的Dijkstra, 其變形程度是相當(dāng)可怕的, 比如會(huì)消耗汽油的車的最短路問題, 這就是一個(gè)相對簡單的二維Dijkstra, 而更加復(fù)雜的, 例如08年哈爾濱賽區(qū)的H, 一道隱藏在搜索背后的三維Dijkstra, 全場沒有隊(duì)伍出. 解決這類問題的一個(gè)根本性方法就是充分理解Dijkstra的定標(biāo)技術(shù), 以及規(guī)范的狀態(tài)表示. 何為規(guī)范? 即當(dāng)狀態(tài)維數(shù)增高時(shí), 需要對應(yīng)的結(jié)構(gòu)定義其狀態(tài), 并且此結(jié)構(gòu)體切不可與存入堆的結(jié)構(gòu)相混淆, 只要明確了Dijkstra的狀態(tài)表示以及在某些限制條件下的狀態(tài)轉(zhuǎn)移(即圖中的"邊"), 則高維Dijkstra就不再是無法攻克的攔路虎了.
圖論的另一個(gè)大頭就是網(wǎng)絡(luò)流, 這是圖論中最容易套模板的一部分, 也是極其困難的一部分. 說容易套模板是因?yàn)橥@類題目在賽場上本身就是中等題或難題, 如果再不能套模板, 八成就變成了無人能出的大自然題了...網(wǎng)絡(luò)流的變形數(shù)量幾乎可以趕的上Dijkstra了, 如果算上匹配類的題目則就是有過之而無不及.網(wǎng)絡(luò)流基本可以分為最大流, 限制流, 費(fèi)用流三種, 其中最大流可以變形為二分匹配, 費(fèi)用流可以變形為帶權(quán)匹配. 其中最大流的算法是其它幾種流算法的基礎(chǔ), 主流算法可以分類增廣路類和預(yù)流推進(jìn)類, 這兩類算法幾乎沒有聯(lián)系, 對于ACM, 只要學(xué)習(xí)前一種就足夠了.
網(wǎng)絡(luò)流類題目, 包括匹配類題目的核心思想就是增廣路, 在匹配類題目中特化為交錯(cuò)軌, 這也是增廣路類算法的核心. 各種增廣路類算法的區(qū)別大都在于如何快速找到一條增廣路, 其中比較簡單的EK就是每次BFS找到一條增廣路, 我就不多說了, 而高級(jí)一點(diǎn)的ISAP和Dinic都屬于SAP, 兩者都是基于分層圖的思想, 實(shí)現(xiàn)分層圖的方法只要為每個(gè)頂點(diǎn)標(biāo)記所在層號(hào)即可, 其中Dinic是通過一次BFS建立分層圖, 然后按照建立好的分層圖進(jìn)行多次DFS找到多條增廣路, 從而不用像EK那樣每條增廣路都做一次BFS. 而ISAP則是在DFS的同時(shí)建立分層圖, 即遇到DFS前進(jìn)不了的時(shí)候?qū)ο乱豁旤c(diǎn)重新標(biāo)號(hào), 于是這張分層圖是逐步建立的, 建立后可以被后面的DFS所利用, 從而降低尋找增廣路的消耗. Dinic和ISAP都可以用"當(dāng)前弧"技術(shù)進(jìn)行優(yōu)化, 而ISAP還有一個(gè)進(jìn)需要添加一行代碼的GAP優(yōu)化, 具體實(shí)現(xiàn)很容易在網(wǎng)上搜到. 這里要特別說一下Dinic和ISAP的適用范圍, ISAP是萬金油, 幾乎可以應(yīng)付絕大部分最大流和限制流的題目, 而Dinic特別適用于有向無環(huán)圖, 即畫在紙上可以分層的題目, 此時(shí)Dinic往往只總共需要做一次BFS(因?yàn)闆]有可以回退的邊), 這時(shí)Dinic往往會(huì)比ISAP快很多. 要知道網(wǎng)絡(luò)流是一個(gè)極度悲觀的世界, 任何已知的算法都沒有能突破O(n^3), 所以最大流算法寫得不好很容易超時(shí). 至于費(fèi)用流, 可以基于EK算法, 只要將BFS改為SPFA就可以應(yīng)付幾乎所有的費(fèi)用流問題了, 少量需要用到消負(fù)環(huán)算法的題目只要用SPFA找負(fù)環(huán)即可. 而限制流則只是一個(gè)定式的建圖, 沒什么特別的地方. 最后還有一種限制費(fèi)用流, 如果遇到, 幾乎肯定就是大自然題, 可以直接無視之. 關(guān)于而分圖匹配的算法, 網(wǎng)上資料很多, 核心思想還是基于最大流, 只是可能不用最大流來解釋也是可以的. 其中用于帶權(quán)匹配的KM算法只要準(zhǔn)備好模板即可, 一般不會(huì)有太大變形.
上面一段說的是既有的算法, 大部分都可以模板化, 其中要注意準(zhǔn)備模板的時(shí)候最要準(zhǔn)備針對整數(shù)和浮點(diǎn)數(shù)的兩種, 對于C++程序員來說, 相應(yīng)的只要寫成函數(shù)模板, 然后傳入比較函數(shù)對象即可, 代碼量幾乎不會(huì)有什么增加.
下面要說說網(wǎng)絡(luò)流類題目真正的難點(diǎn)之一, 建圖. 網(wǎng)絡(luò)流類題目難在它往往伴隨著一個(gè)不太直觀的建圖, 其中有些利用到最大流最小割定理的建圖已經(jīng)有了套路, 比如說限制流的建圖, 最大權(quán)閉合圖等, 具體可以參見國家IO集訓(xùn)隊(duì)2007年胡伯濤的論文. 另外一些建圖則很有技巧性. 比如"比賽"類題目, 有很多場比賽, 要你求得分能否達(dá)到某種條件等, 這時(shí)需要把每場比賽看成頂點(diǎn), 然后兩條流進(jìn)來, 只有一條可以出去, 這種題目的特色是存在大量容量1的邊. 還有拆點(diǎn)建圖, 這類題目往往一個(gè)頂點(diǎn)上包含了2種"屬性", 而網(wǎng)絡(luò)流算法中, 屬性是體現(xiàn)在連在邊上的, 盡量要使每個(gè)頂點(diǎn)表示的屬性單一化, 于是就把一個(gè)點(diǎn)拆分成兩個(gè)點(diǎn), 然后把屬性分配出去, 比如PKU有一題說企鵝在冰塊上跳來跳去, 冰塊就有兩個(gè)屬性, 一個(gè)是冰上的企鵝數(shù)量, 另一個(gè)是冰塊再被起跳多少次后會(huì)碎掉, 這時(shí)就需要把兩個(gè)屬性拆分開來, 拆點(diǎn)的另一個(gè)應(yīng)用就是求最小點(diǎn)隔集, 其中的思想就是像這題冰上企鵝一樣, 把出度和入度兩個(gè)屬性分離開. 另外一些更加巧妙的建圖可能涉及逆向思維等技高技巧性的思維方法, 這里就不一一列舉了.
網(wǎng)絡(luò)流的難點(diǎn)之二是算法變形, 特別是有的題目在增廣路上做文章. 有一種叫做"連續(xù)增廣路"的技術(shù), 需要深入理解增廣路的原理, 今年的上海賽區(qū)F題就是基于連續(xù)增廣路的二分匹配加搜索, 雖然之前做過一個(gè)基于最大流算法的連續(xù)增廣路, 但是很遺憾, 當(dāng)時(shí)沒有能想到這個(gè)算法. 另外, 與字典序相關(guān)的最大流題目往往需要枚舉刪邊, 如字典序最小邊割集. 與其它類型題目相結(jié)合的算法變形就多不勝數(shù)了, 最常見的當(dāng)屬二分答案判可行性, 很多貌似運(yùn)輸類的問題很多都可以歸結(jié)到這種方法上.
剛才說道了二分答案, 這也是所有圖論類(應(yīng)該說不僅僅是圖論)題目最常見的變形, "最(大)小值最大(小)"是這類題目的最一般特征. 這類題目常常跟分?jǐn)?shù)規(guī)劃聯(lián)系在一起, 比如最優(yōu)比率生成樹, 最優(yōu)比率環(huán)等.
另外圖論的一些經(jīng)典算法可以衍生出很多強(qiáng)大的應(yīng)用, 比如差分約束就是Bellman-Ford或SPFA的一個(gè)最好的應(yīng)用, 這類題目的建圖關(guān)鍵是找出差分式子. 一個(gè)需要特別注意的地方是[算法導(dǎo)論]上對于不連通圖上添加頂點(diǎn)的討論, 最好的方法是不用添加頂點(diǎn), 開始時(shí)直接將dis數(shù)組清0, 然后所有頂點(diǎn)入隊(duì)即可.
生成樹類的題目也有很多變形, 如歐幾里得生成樹, 往往需要利用平面圖上的一些幾何性質(zhì)建圖, 如曼哈頓距離生成樹, 限制度生成樹等等, 此類題目套路不多, 且知識(shí)點(diǎn)比較散亂, 需要多做題來熟練.
圖的連通性也是一個(gè)常見的考點(diǎn). 割點(diǎn), 橋, 強(qiáng)連通, 雙連通問題的求解不僅要準(zhǔn)備模板, 還要充分理解模板. 一些地圖上的題目(二維的方格陣), 往往有些特殊的性質(zhì), 不僅需要你一些建圖的敏感度, 偶爾需要在模板中添加一些巧妙的代碼.
圖論還可以與組合數(shù)學(xué)和計(jì)算幾何等產(chǎn)生緊密的聯(lián)系, 比如生成樹和圖的計(jì)數(shù), 最簡單的諸如n個(gè)頂點(diǎn)可以產(chǎn)生多少個(gè)不同的無向連通圖, 這時(shí)一些組合數(shù)學(xué)中的基礎(chǔ)原理往往十分有用, 最典型的就是容斥原理.
圖論中還有茫茫多的定理, 性質(zhì)等. 我所知道的最雷人要數(shù)08年哈爾濱賽區(qū)那道赤裸裸的Havel定理了. 這些定理和性質(zhì)可能會(huì)在一些意想不到的地方發(fā)揮作用.
最后圖論中的一些NP問題或非NP但是代碼不好寫的問題, 如旅行商, 同構(gòu), 支配集, 最大團(tuán), 以及由樹所引申出的一大堆樹形DP問題不好準(zhǔn)備模板, 但可以考慮準(zhǔn)備一些具有代表性的解題報(bào)告的紙版材料. 其中樹形DP是一個(gè)很容易寫錯(cuò)的重頭戲, 它往往還和背包問題聯(lián)系在一起, 尤其是泛化物品的背包, 關(guān)于泛化物品, 請參見DD牛的[背包九講].
關(guān)于工具
ACM的學(xué)習(xí), 對于我們一個(gè)弱校來說, 沒有牛B的教練, 沒有嚴(yán)格的教學(xué), 最主要的學(xué)習(xí)方式莫過于收集和記錄, 不論是外部知識(shí)的搜索收集, 還是內(nèi)部知識(shí)的記錄整理, 最離不開的當(dāng)屬Google.
搜索我就不用說了, 這里關(guān)于知識(shí)的記錄和整理, 我要推薦如下幾個(gè)工具: Google Docs, Google Desktop, Google Calender, Everything.
前兩個(gè)都是輔助你記錄和復(fù)習(xí)你的解題報(bào)告, 第三個(gè)用于時(shí)間管理以及任務(wù)計(jì)劃, 詳情請自己去用Google搜索去.
最后一個(gè)Everything是windows平臺(tái)下特別針對NTFS文件系統(tǒng)的一個(gè)神奇的搜索工具, 它可以僅僅使用約5MB的內(nèi)存在1秒內(nèi)搜索出你的所有NTFS盤上任何一個(gè)文件名跟輸入關(guān)鍵字匹配的文件, 其原理據(jù)說是基于NTFS文件系統(tǒng)的一個(gè)特殊的記錄表的.
這個(gè)東西的一個(gè)最有趣的應(yīng)用可以是這樣: 把你硬盤上的所有文件和文件夾都加上標(biāo)簽吧, 用"[]"括起來, 然后用","隔開, 然后任何時(shí)候你都可以通過標(biāo)簽搜索到你想要的東西, 一切圖片, 論文, 軟件等等, 比如PKU的1001題我就可以加上"[java,BigDecimal,浮點(diǎn)數(shù),高精度]"之類的字樣.
甚至更精細(xì)一點(diǎn), 定義一些特殊的tag, 比如"tag.r"表示"需要review", "tag.h"表示"我是在別人的help下做出的題目", "tag.p"表示"這題我還有未解決的problem"等等.
關(guān)于學(xué)習(xí)
我所知道的關(guān)于學(xué)習(xí), 90%來自于[www.xiaolai.net](李笑來的blog), 和[www.mindhacks.cn](劉未鵬的blog), 把里面關(guān)于學(xué)習(xí)方法的文章看完, 你就升華了. 在此特別感謝上海第二工業(yè)大學(xué)的王學(xué)長告訴我Google Reader的存在, 大二開始的時(shí)候我因?yàn)檫@個(gè)接觸到blog這種東西, 讓我對學(xué)習(xí)方法有了一個(gè)相對清醒的認(rèn)識(shí). 也許很多所謂的方法我們早就知道了, 可就是"很多道理我們其實(shí)我們老早就知道, 只是需要一個(gè)權(quán)威人士告訴我們它確實(shí)是正確的".
這里特別要說一些關(guān)于學(xué)習(xí)效率和順序的問題.
大二就去看什么人工智能, 自然語言處理, 對于絕大多數(shù)人來說, 那就是低效, 甚至你在看這些書的時(shí)候連筆記都不知道該怎么記, 更何況還有那么多人看書都沒有記筆記的習(xí)慣. 但是即使你用心做了筆記, 也不一定能學(xué)到什么東西, 比如我當(dāng)時(shí)就將近記了一大本的關(guān)于人工智能, 心理學(xué)之類的東西, 可現(xiàn)在回頭看看一恰的筆記幾乎已經(jīng)不敢相信那是我自己寫的了, 完全不認(rèn)識(shí). 究其原因有二, 一是先導(dǎo)知識(shí)儲(chǔ)備不足, 二是沒有及時(shí)回顧筆記. 這兩點(diǎn)在很多人的學(xué)習(xí)過程中都在不斷重復(fù)上演著, 其結(jié)果就是浪費(fèi)了大量時(shí)間卻學(xué)不到什么東西. 所謂的"做開發(fā)"也是如此, 連關(guān)系數(shù)據(jù)庫的幾個(gè)范式都不知道是什么就去弄什么SQL Server, 搞什么ORM, 全都是空談, 充其量也就是會(huì)用用工具而已.
就我目前的經(jīng)歷來看, 我認(rèn)為作為一個(gè)軟件方向的CS學(xué)生, 相對高效的學(xué)習(xí)方案應(yīng)該是學(xué)基礎(chǔ)課時(shí)學(xué)好高數(shù)和英語(我現(xiàn)在就特別想再去重學(xué)高數(shù)), 閑暇時(shí)間搞搞C++, Java, 等各種語言, 至少做到一個(gè)了解的程度, 個(gè)別的要熟練, 與計(jì)算機(jī)軟件關(guān)系不是很大的理科課程成績搞到90+就行, 比如物理, 比如電路, 線性代數(shù)很簡單, 概率論要特別認(rèn)真學(xué), 特別是經(jīng)常要拿起來復(fù)習(xí)復(fù)習(xí), 這是一門終身受用的學(xué)科. 然后其余的時(shí)間可以用來啃算法導(dǎo)論, 相信我, 這本書普通人大學(xué)四年根本不可能啃完. 總之?dāng)?shù)學(xué)類的書看的再多都嫌少. 另外可以擴(kuò)展出去接觸一些人文類書籍, 特別是傳記類, 勵(lì)志類的東西.
關(guān)于修養(yǎng)
我剛上大學(xué)的時(shí)候有這么一個(gè)習(xí)慣, 拿一些自己心中已經(jīng)知道答案的問題去請教老師, 以顯得自己很好學(xué), 很牛B. 記得我有過在軟件工程選修課上跑去問我們學(xué)校有沒有關(guān)于"設(shè)計(jì)模式"的課程, 或者問ben一些明顯Google一下就能知道答案的問題...等等等等都是內(nèi)心浮躁的表現(xiàn).
自我修養(yǎng)是一種很要緊的東西, 對于一個(gè)性格內(nèi)向的ACMer來說, 這往往不會(huì)有什么問題, 這是由性格決定的, 但不是每個(gè)人都性格內(nèi)向, 不是每個(gè)人都能保持內(nèi)斂. 一旦你有裝B(一切驕傲, 或者因?yàn)樽约旱哪撤矫娌拍芏凑醋韵? 或者想要顯露自己, 不管和不合適, 暫且用"裝B"來代替吧)的行為或者想法, 或者僅僅是潛意識(shí), 那就預(yù)示著你會(huì)被大多數(shù)人看不起, 會(huì)大量浪費(fèi)自己的時(shí)間, 會(huì)降低自己的學(xué)習(xí)效率, 會(huì)使自己成為井底之蛙. 不過完全不裝B倒也不太好做到, 比如我以為自己寫blog多少有些顯露自己的意思, 自我分析一下, 動(dòng)機(jī)大概有如下幾條: 想讓日后身邊的某人突然發(fā)現(xiàn)我說:"啊, 你就是Answeror啊!", 想讓我以前女朋友在若干年后突然發(fā)現(xiàn)我的blog說:"原來我以前男朋友這么好學(xué), 這么有修養(yǎng)有文化!", 想讓我被某些大學(xué)教授或者公司里的人認(rèn)識(shí), 想結(jié)交志同道合朋友, 想讓別人給我的解題報(bào)告挑錯(cuò)...
寫blog這件事情也就算了, 畢竟是件利人利己的好事, 偶爾裝裝B也就算了. 但是像我在本文開頭說的那樣, 剛進(jìn)華理僅僅因?yàn)樽约河悬c(diǎn)C++和網(wǎng)絡(luò)工程知識(shí)的皮毛就裝出一副很牛B的樣子, 那種裝任誰都無法忍受. 尤其是第一次跟羅老師的談話, 簡直就是裝到了極點(diǎn), 以至于我后來就有這么一個(gè)想法: 反正我可以做技術(shù)活, 干嘛非要搞ACM, 我可以自由地去學(xué)心理學(xué), 學(xué)人工智能, 學(xué).NET, 我牛B著呢, ACM算個(gè)屁. 然后我就傻BB地搞了5個(gè)月的.NET, 然后到大三上數(shù)據(jù)庫原理的時(shí)候發(fā)現(xiàn)當(dāng)時(shí)花了一個(gè)星期學(xué)的種種東西現(xiàn)在只是一節(jié)課的事情, 直到那時(shí)我還在裝B, 跟旁邊的同學(xué)說我上述的體會(huì), 仿彿就是在告訴他說:"你看我牛B吧, 我老早就知道這是什么東西了, 還做過它的開發(fā)", 時(shí)至今日, 我仍然有時(shí)會(huì)忍不住在同學(xué)討論C++種種語言特性時(shí)上去插插嘴, 裝裝B. 高中的一個(gè)好友曾這樣形容我: "他這個(gè)人啊, 只要看了什么書或者電影之類的, 就要馬上在他的文章里體現(xiàn)出來".
聽起來很好笑吧, 請正在看這些文字的你不妨停下來反思一下自己最近一個(gè)星期有沒有類似的行為?
作為一個(gè)ACMer, 改掉這些吧.
我們做ACM的, 本來在這個(gè)學(xué)風(fēng)不正的計(jì)算機(jī)學(xué)院里就是一群特殊人群, 我們需要做的僅僅是不停地補(bǔ)充知識(shí), 完善自己, 沒必要費(fèi)盡心機(jī)去博得他人的一兩句贊美之辭. 我是誰? 我就是華理的一個(gè)ACMer. 我每天窩在機(jī)房里為的不是哪天去比賽有小MM來找我們簽名, 而是讓自己精通各種算法, 提升自己的數(shù)學(xué)修養(yǎng), 增強(qiáng)自己解決問題的能力, 培養(yǎng)自己內(nèi)斂的人格, 然后在某日某公司的面試時(shí)讓面試官打心地里認(rèn)為我是個(gè)人才, 然后用我以前長期積累的知識(shí)寫出卓越的軟件.
希望你我都能早日問心無愧地說出上面的話.
