我們學(xué)校的計算機(jī)學(xué)院從去年起開始組織學(xué)生參加世界上最具權(quán)威性的大學(xué)生程序設(shè)計競賽——ACM/ICPC。從這學(xué)期開始，學(xué)院計劃有組織地進(jìn)行訓(xùn)練和講座，以幫助大家在有限的時間內(nèi)盡可能多地提高自己的能力，這對有興趣投入數(shù)據(jù)結(jié)構(gòu)與算法研究的同學(xué)來說無疑是一件好事。但是，剛剛接觸信息學(xué)領(lǐng)域的同學(xué)往往存在很多困惑，不知道從何入手學(xué)習(xí)，在這篇文章里，我希望能將自己不多的經(jīng)驗與大家分享，希望對各位有所幫助。
一、語言是最重要的基本功
無論側(cè)重于什么方面，只要是通過計算機(jī)程序去最終實現(xiàn)的競賽，語言都是大家要過的第一道關(guān)。亞洲賽區(qū)的比賽支持的語言包括C/C++與JAVA。筆者首先說說JAVA，眾所周知，作為面向?qū)ο蟮耐跖普Z言，JAVA在大型工程的組織與安全性方面有著自己獨特的優(yōu)勢，但是對于信息學(xué)比賽的具體場合，JAVA則顯得不那么合適，它對于輸入輸出流的操作相比于C++要繁雜很多，更為重要的是JAVA程序的運(yùn)行速度要比C++慢10倍以上，而競賽中對于JAVA程序的運(yùn)行時限卻往往得不到同等比例的放寬，這無疑對算法設(shè)計提出了更高的要求，是相當(dāng)不利的。其實，筆者并不主張大家在這種場合過多地運(yùn)用面向?qū)ο蟮某绦蛟O(shè)計思維，因為對于小程序來說這不但需要花費(fèi)更多的時間去編寫代碼，也會降低程序的執(zhí)行效率。
接著說C和C++。許多現(xiàn)在參加講座的同學(xué)還在上大一，C的基礎(chǔ)知識剛剛學(xué)完，還沒有接觸過C++，其實在賽場上使用純C的選手還是大有人在的，它們主要是看重了純C在效率上的優(yōu)勢，所以這部分同學(xué)如果時間有限，并不需要急著去學(xué)習(xí)新的語言，只要提高了自己在算法設(shè)計上的造詣，純C一樣能發(fā)揮巨大的威力。
而C++相對于C，在輸入輸出流上的封裝大大方便了我們的操作，同時降低了出錯的可能性，并且能夠很好地實現(xiàn)標(biāo)準(zhǔn)流與文件流的切換，方便了調(diào)試的工作。如果有些同學(xué)比較在意這點，可以嘗試C和C++的混編，畢竟僅僅學(xué)習(xí)C++的流操作還是不花什么時間的。
C++的另一個支持來源于標(biāo)準(zhǔn)模版庫（STL），庫中提供的對于基本數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一接口操作和基本算法的實現(xiàn)可以縮減我們編寫代碼的長度，這可以節(jié)省一些時間。但是，與此相對的，使用STL要在效率上做出一些犧牲，對于輸入規(guī)模很大的題目，有時候必須放棄STL，這意味著我們不能存在“有了STL就可以不去管基本算法的實現(xiàn)”的想法；另外，熟練和恰當(dāng)?shù)厥褂肧TL必須經(jīng)過一定時間的積累，準(zhǔn)確地了解各種操作的時間復(fù)雜度，切忌對STL中不熟悉的部分濫用，因為這其中蘊(yùn)涵著許多初學(xué)者不易發(fā)現(xiàn)的陷阱。
通過以上的分析，我們可以看出僅就信息學(xué)競賽而言，對語言的掌握并不要求十分全面，但是對于經(jīng)常用到的部分，必須十分熟練，不允許有半點不清楚的地方，下面我舉個真實的例子來說明這個道理——即使是一點很細(xì)微的語言障礙，都有可能釀成錯誤：
在去年清華的賽區(qū)上，有一個隊在做F題的時候使用了cout和printf的混合輸出，由于一個帶緩沖一個不帶，所以輸出一長就混亂了。只是因為當(dāng)時 judge team中負(fù)責(zé)F題的人眼睛尖，看出答案沒錯只是順序不對（答案有一頁多，是所有題目中最長的一個輸出），又看了看程序發(fā)現(xiàn)只是輸出問題就給了個 Presentation error（格式錯）。如果審題的人不是這樣而是直接給一個 Wrong Answer，相信這個隊是很難查到自己錯在什么地方的。
現(xiàn)在我們轉(zhuǎn)入第二個方面的討論，基礎(chǔ)學(xué)科知識的積累。
二、以數(shù)學(xué)為主的基礎(chǔ)知識十分重要
雖然被定性為程序設(shè)計競賽，但是參賽選手所遇到的問題更多的是沒有解決問題的思路，而不是有了思路卻死活不能實現(xiàn)，這就是平時積累的基礎(chǔ)知識不夠。今年 World Final的總冠軍是波蘭華沙大學(xué)，其成員出自于數(shù)學(xué)系而非計算機(jī)系，這就是一個鮮活的例子。競賽中對于基礎(chǔ)學(xué)科的涉及主要集中于數(shù)學(xué)，此外對于物理、電路等等也可能有一定應(yīng)用，但是不多。因此，大一的同學(xué)也不必為自己還沒學(xué)數(shù)據(jù)結(jié)構(gòu)而感到不知從何入手提高，把數(shù)學(xué)撿起來吧！下面我來談?wù)勗诟傎愔袘?yīng)用的數(shù)學(xué)的主要分支。
1、離散數(shù)學(xué)——作為計算機(jī)學(xué)科的基礎(chǔ)，離散數(shù)學(xué)是競賽中涉及最多的數(shù)學(xué)分支，其重中之重又在于圖論和組合數(shù)學(xué)，尤其是圖論。
圖論之所以運(yùn)用最多是因為它的變化最多，而且可以輕易地結(jié)合基本數(shù)據(jù)結(jié)構(gòu)和許多算法的基本思想，較多用到的知識包括連通性判斷、DFS和BFS，關(guān)節(jié)點和關(guān)鍵路徑、歐拉回路、最小生成樹、最短路徑、二部圖匹配和網(wǎng)絡(luò)流等等。雖然這部分的比重很大，但是往往也是競賽中的難題所在，如果有初學(xué)者對于這部分的某些具體內(nèi)容暫時感到力不從心，也不必著急，可以慢慢積累。
競賽中設(shè)計的組合計數(shù)問題大都需要用組合數(shù)學(xué)來解決，組合數(shù)學(xué)中的知識相比于圖論要簡單一些，很多知識對于小學(xué)上過奧校的同學(xué)來說已經(jīng)十分熟悉，但是也有一些部分需要先對代數(shù)結(jié)構(gòu)中的群論有初步了解才能進(jìn)行學(xué)習(xí)。組合數(shù)學(xué)在競賽中很少以難題的形式出現(xiàn)，但是如果積累不夠，任何一道這方面的題目卻都有可能成為難題。
2、數(shù)論——以素數(shù)判斷和同余為模型構(gòu)造出來的題目往往需要較多的數(shù)論知識來解決，這部分在競賽中的比重并不大，但只要來上一道，也足以使知識不足的人冥思苦想上一陣時間。素數(shù)判斷和同余最常見的是在以密碼學(xué)為背景的題目中出現(xiàn)，在運(yùn)用密碼學(xué)常識確定大概的過程之后，核心算法往往要涉及數(shù)論的內(nèi)容。
3、計算幾何——計算幾何相比于其它部分來說是比較獨立的，就是說它和其它的知識點很少有過多的結(jié)合，較常用到的部分包括——線段相交的判斷、多邊形面積的計算、內(nèi)點外點的判斷、凸包等等。計算幾何的題目難度不會很大，但也永遠(yuǎn)不會成為最弱的題。
4、線性代數(shù)——對線性代數(shù)的應(yīng)用都是圍繞矩陣展開的，一些表面上是模擬的題目往往可以借助于矩陣來找到更好的算法。
5、概率論——競賽是以黑箱來判卷的，這就是說你幾乎不能動使用概率算法的念頭，但這也并不是說概率就沒有用。關(guān)于這一點，只有通過一定的練習(xí)才能體會。
6、初等數(shù)學(xué)與解析幾何——這主要就是中學(xué)的知識了，用的不多，但是至少比高等數(shù)學(xué)多，我覺得熟悉一下數(shù)學(xué)手冊上的相關(guān)內(nèi)容，至少要知道在哪兒能查到，還是必要的。
7、高等數(shù)學(xué)——純粹運(yùn)用高等數(shù)學(xué)來解決的題目我接觸的只有一道，但是一些題目的敘述背景往往需要和這部分有一定聯(lián)系，掌握得牢固一些總歸沒有壞處。
以上就是競賽所涉及的數(shù)學(xué)領(lǐng)域，可以說范圍是相當(dāng)廣的。我認(rèn)識的許多人去搞信息學(xué)的競賽就是為了逼著自己多學(xué)一點數(shù)學(xué)，因為數(shù)學(xué)是一切一切的基礎(chǔ)。
三、數(shù)據(jù)結(jié)構(gòu)與算法是真正的核心
雖然數(shù)學(xué)十分十分重要，但是如果讓三個只會數(shù)學(xué)的人參加比賽，我相信多數(shù)情況下會比三個只會數(shù)據(jù)結(jié)構(gòu)與算法的人得到更為悲慘的結(jié)局。
先說說數(shù)據(jù)結(jié)構(gòu)。掌握隊列、堆棧和圖的基本表達(dá)與操作是必需的，至于樹，我個人覺得需要建樹的問題有但是并不多。（但是樹往往是很重要的分析工具）除此之外，排序和查找并不需要對所有方式都能很熟練的掌握，但你必須保證自己對于各種情況都有一個在時間復(fù)雜度上滿足最低要求的解決方案。說到時間復(fù)雜度，就又該說說哈希表了，競賽時對時間的限制遠(yuǎn)遠(yuǎn)多于對空間的限制，這要求大家盡快掌握“以空間換時間”的原則策略，能用哈希表來存儲的數(shù)據(jù)一定不要到時候再去查找，如果實在不能建哈希表，再看看能否建二叉查找樹等等——這都是爭取時間的策略，掌握這些技巧需要大家對數(shù)據(jù)結(jié)構(gòu)尤其是算法復(fù)雜度有比較全面的理性和感性認(rèn)識。
接著說說算法。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。這里要說的是，有些初學(xué)者在學(xué)習(xí)這些搜索基本算法是不太注意剪枝，這是十分不可取的，因為所有搜索的題目給你的測試用例都不會有很大的規(guī)模，你往往察覺不出程序運(yùn)行的時間問題，但是真正的測試數(shù)據(jù)一定能過濾出那些沒有剪枝的算法。實際上參賽選手基本上都會使用常用的搜索算法，題目的區(qū)分度往往就是建立在諸如剪枝之類的優(yōu)化上了。
常用算法中的另一類是以“相似或相同子問題”為核心的，包括遞推、遞歸、貪心法和動態(tài)規(guī)劃。這其中比較難于掌握的就是動態(tài)規(guī)劃，如何抽象出重復(fù)的子問題是很多題目的難點所在，筆者建議初學(xué)者仔細(xì)理解圖論中一些以動態(tài)規(guī)劃為基本思想所建立起來的基本算法（比如Floyd-Warshall算法），并且多閱讀一些定理的證明，這雖然不能有什么直接的幫助，但是長期堅持就會對思維很有幫助。
四、團(tuán)隊配合
通過以上的介紹大家也可以看出，信息學(xué)競賽對于知識面覆蓋的非常廣，想憑一己之力全部消化這些東西實在是相當(dāng)困難的，這就要求我們盡可能地發(fā)揮團(tuán)隊協(xié)作的精神。同組成員之間的熟練配合和默契的形成需要時間，具體的情況因成員的組成不同而不同，這里我就不再多說了。
五、練習(xí)、練習(xí)、再練習(xí)
知識的積累固然重要，但是信息學(xué)終究不是看出來的，而是練出來的，這是多少前人最深的一點體會，只有通過具體題目的分析和實踐，才能真正掌握數(shù)學(xué)的使用和算法的應(yīng)用，并在不斷的練習(xí)中增加編程經(jīng)驗和技巧，提高對時間復(fù)雜度的感性認(rèn)識，優(yōu)化時間的分配，加強(qiáng)團(tuán)隊的配合?？傊?，在這里光有紙上談兵是絕對不行的，必須要通過實戰(zhàn)來鍛煉自己。
大家一定要問，我們?nèi)ツ睦镎翌}做，又如何檢驗程序是否正確呢？這大可不必?fù)?dān)心，現(xiàn)在已經(jīng)有了很多網(wǎng)上做題的站點，這些站點提供了大量的題庫并支持在線判卷，你只需要把程序源碼提交上去，馬上就可以知道自己的程序是否正確，運(yùn)行所使用的時間以及消耗的內(nèi)存等等狀況。下面我給大家推薦幾個站點，筆者不建議大家在所有這些站點上做題，選擇一個就可以了，因為每個站點的題都有一定的難易比例，系統(tǒng)地做一套題庫可以使你對各種難度、各種類型的題都有所認(rèn)識。
1、Ural：
Ural是中國學(xué)生對俄羅斯的Ural州立大學(xué)的簡稱 ，那里設(shè)立了一個Ural Online Problem Set，并且支持Online Judge。Ural的不少題目算法性和趣聞性都很強(qiáng)，得到了國內(nèi)廣大學(xué)生的厚愛。根據(jù)“信息學(xué)初學(xué)者之家”網(wǎng)站的統(tǒng)計，Ural的題目類型大概呈如下的分布：
題型 搜索 動態(tài)規(guī)劃 貪心 構(gòu)造 圖論 計算幾何 純數(shù)學(xué)問題 數(shù)據(jù)結(jié)構(gòu) 其它
所占比例 約10% 約15% 約5% 約5% 約10% 約5% 約20% 約5% 約25%
這和實際比賽中的題型分布也是大體相當(dāng)?shù)?。有興趣的朋友可以去看看。
2、UVA：
UVA代表西班牙Valladolid大學(xué)(University de Valladolid)。該大學(xué)有一個那里設(shè)立了一個PROBLEM SET ARCHIVE with ONLINE JUDGE ，并且支持ONLINE JUDGE，形式和Ural大學(xué)的題庫類似。不過和Ural不同的是，UVA題目多的多，而且比較雜，而且有些題目的測試數(shù)據(jù)比較刁鉆。這使得剛到那里做題的朋友往往感覺到無所適從，要么難以找到合適的題目，要么Wrong Answer了很多次以后仍然不知道錯在那里。如果說做Ural題目主要是為了訓(xùn)練算法，那么UVA題目可以訓(xùn)練全方位的基本功和一些必要的編程素質(zhì)。UVA和許多世界知名大學(xué)聯(lián)合辦有同步網(wǎng)上比賽，因此那里強(qiáng)人無數(shù)，不過你先要使自己具有聽懂他們在說什么的素質(zhì)：）
3、ZOJ：
ZOJ是浙江大學(xué)建立的ONLINE JUDGE，是中國大學(xué)建立的第一個同類站點，也是最好和人氣最高的一個，筆者和許多班里的同學(xué)就是在這里練習(xí)。ZOJ雖然也定位為一個英文網(wǎng)站，但是這里的中國學(xué)生比較多，因此讓人覺得很親切。這里目前有500多道題目，難易分配適中，且涵蓋了各大洲的題目類型并配有索引，除此之外，ZOJ的JUDGE 系統(tǒng)是幾個網(wǎng)站中表現(xiàn)得比較好的一個，很少出現(xiàn)Wrong Answer和Presentation error混淆的情況。這里每月也辦有一次網(wǎng)上比賽，只要是注冊的用戶都可以參加。
說起中國的ONLINE JUDGE，去年才開始參加ACM競賽的北京大學(xué)現(xiàn)在也建立了自己的提交系統(tǒng)；而我們學(xué)校也是去年開始參加比賽，現(xiàn)在也有可能推出自己的提交系統(tǒng)，如果能夠做成，到時候大家就可以去上面做題了。同類網(wǎng)站的飛速發(fā)展標(biāo)志著有越來越多的同學(xué)有興趣進(jìn)入信息學(xué)的領(lǐng)域探索，這是一件好事，同時也意味著更激烈的競爭，希望大家都能通過競爭鍛煉自己、提高自己，并爭取成為勝利者?！?
版權(quán)聲明：編程愛好者網(wǎng)站為此BLOG服務(wù)提供商，如本文牽涉到版權(quán)問題，編程愛好者網(wǎng)站不承擔(dān)相關(guān)責(zé)任，如有版權(quán)問題請直接與本文作者聯(lián)系解決。謝謝！
===========================================================================
學(xué)習(xí)網(wǎng)站：
===========================================================================
以下轉(zhuǎn)自Myheimu's Blog
==========================================================
雜項
