Feng.Li's Java See

首先歡迎大家加入NIT_ACM程序設(shè)計(jì)集訓(xùn)隊(duì)這個(gè)大家庭,希望接下來的日子里,大家都喜歡上寫程序,喜歡上ACM/ICPC, enjoy it and love it.

沒有規(guī)矩,不成方圓.我們NIT_ACM經(jīng)過風(fēng)風(fēng)雨雨的兩年,有了自己獨(dú)特的文化也有自己一定的紀(jì)律,當(dāng)然所有一切只是希望大家能夠自覺遵守,如果違反了,我們也沒治懲之意.一切都建立于大家自覺的基礎(chǔ)上.

l 關(guān)于紀(jì)律.
1. 不要破壞公共財(cái)物. ^_^
2. 集訓(xùn)期間準(zhǔn)時(shí)參加訓(xùn)練.一般時(shí)間為早上9:30 – 23:30, 有小事自己安排^_^,有事晚上可以提早回去,早上可以提早來.
3. 不要在SE312玩游戲.
4. 不要偷懶.一分付出,一分收獲.^_^
5. 集訓(xùn)期間回家的時(shí)候一定先告知一下隊(duì)長或者蔡老師.
6. 上課期間不要逃課.^_^
7. 大家要團(tuán)結(jié)友愛
8. 一般的節(jié)假日都為集訓(xùn)日.


大家都是抱著對算法與數(shù)據(jù)結(jié)構(gòu)極大的興趣才參加集訓(xùn)的,我們也希望大家學(xué)有所成,但是剛剛接觸信息學(xué)領(lǐng)域的同學(xué)往往存在很多困惑，不知道從何入手學(xué)習(xí)，在這篇向?qū)Ю?，我希望能將自己不多的?jīng)驗(yàn)與大家分享，希望對各位有所幫助.
一、語言是最重要的基本功
無論側(cè)重于什么方面，只要是通過計(jì)算機(jī)程序去最終實(shí)現(xiàn)的競賽，語言都是大家要過的第一道關(guān).亞洲賽區(qū)的比賽支持的語言包括C/C++與JAVA.雖然JAVA在應(yīng)用極為廣泛,但是其運(yùn)行速度不可恭維.而且在以往的比賽中來看,大多數(shù)隊(duì)伍還是采用了C或者C++.而且C語言是大家接觸的第一門編程語言,所以我們集訓(xùn)隊(duì)都采用C和C++混編的方式寫代碼.
新來的同學(xué)可能C的基礎(chǔ)知識(shí)剛剛學(xué)完，還沒有接觸過C++，其實(shí)在賽場上使用純C的選手還是大有人在的，它們主要是看重了純C在效率上的優(yōu)勢，所以這部分同學(xué)如果時(shí)間有限，并不需要急著去學(xué)習(xí)新的語言，只要提高了自己在算法設(shè)計(jì)上的造詣，純C一樣能發(fā)揮巨大的威力.但是我還是希望大家都能夠?qū)W點(diǎn)C++.
C++相對于C，在輸入輸出流上的封裝大大方便了我們的操作，同時(shí)降低了出錯(cuò)的可能性，并且能夠很好地實(shí)現(xiàn)標(biāo)準(zhǔn)流與文件流的切換，方便了調(diào)試的工作。如果有些同學(xué)比較在意這點(diǎn)，可以嘗試C和C++的混編，畢竟僅僅學(xué)習(xí)C++的流操作還是不花什么時(shí)間的。
C++的另一個(gè)支持來源于標(biāo)準(zhǔn)模版庫（STL），庫中提供的對于基本數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一接口操作和基本算法的實(shí)現(xiàn)可以縮減我們編寫代碼的長度，這可以節(jié)省一些時(shí)間。但是，與此相對的，使用STL要在效率上做出一些犧牲，對于輸入規(guī)模很大的題目，有時(shí)候必須放棄STL，這意味著我們不能存在“有了STL就可以不去管基本算法的實(shí)現(xiàn)”的想法；另外，熟練和恰當(dāng)?shù)厥褂肧TL必須經(jīng)過一定時(shí)間的積累，準(zhǔn)確地了解各種操作的時(shí)間復(fù)雜度，切忌對STL中不熟悉的部分濫用，因?yàn)檫@其中蘊(yùn)涵著許多初學(xué)者不易發(fā)現(xiàn)的陷阱。像STL中的很多容器, vector,queue,stack,map,set等一定要比較熟悉,STL中的sort是必需要掌握的.掌握這些STL知識(shí)后寫代碼的時(shí)候想對于純C會(huì)節(jié)省不少時(shí)間.

C語言學(xué)習(xí)推薦:C程序設(shè)計(jì)(譚浩強(qiáng)編著)
C++學(xué)習(xí)推薦: C++Prime, C++大學(xué)教程.(其實(shí)基本上的C++教程都行的…)
STL學(xué)習(xí)推薦: C++Prime,STL標(biāo)準(zhǔn)庫.(理論聯(lián)系實(shí)際,邊學(xué)就用學(xué)的最快)

二、以數(shù)學(xué)為主的基礎(chǔ)知識(shí)十分重要

雖然被定性為程序設(shè)計(jì)競賽，但是參賽選手所遇到的問題更多的是沒有解決問題的思路，而不是有了思路卻死活不能實(shí)現(xiàn)，這就是平時(shí)積累的基礎(chǔ)知識(shí)不夠。競賽中對于基礎(chǔ)學(xué)科的涉及主要集中于數(shù)學(xué)，此外對于物理、電路等等也可能有一定應(yīng)用，但是不多。因此，大一的同學(xué)也不必為自己還沒學(xué)數(shù)據(jù)結(jié)構(gòu)而感到不知從何入手提高，把數(shù)學(xué)撿起來吧！下面來談?wù)勗诟傎愔袘?yīng)用的數(shù)學(xué)的主要分支。

1、離散數(shù)學(xué)——作為計(jì)算機(jī)學(xué)科的基礎(chǔ)，離散數(shù)學(xué)是競賽中涉及最多的數(shù)學(xué)分支，其重中之重又在于圖論和組合數(shù)學(xué)，尤其是圖論。

圖論之所以運(yùn)用最多是因?yàn)樗淖兓疃啵铱梢暂p易地結(jié)合基本數(shù)據(jù)結(jié)構(gòu)和許多算法的基本思想，較多用到的知識(shí)包括連通性判斷、DFS和BFS，關(guān)節(jié)點(diǎn)和關(guān)鍵路徑、歐拉回路、最小生成樹、最短路徑、二部圖匹配和網(wǎng)絡(luò)流等等。雖然這部分的比重很大，但是往往也是競賽中的難題所在，如果有初學(xué)者對于這部分的某些具體內(nèi)容暫時(shí)感到力不從心，也不必著急，可以慢慢積累。

競賽中設(shè)計(jì)的組合計(jì)數(shù)問題大都需要用組合數(shù)學(xué)來解決，組合數(shù)學(xué)中的知識(shí)相比于圖論要簡單一些，很多知識(shí)對于小學(xué)上過奧校的同學(xué)來說已經(jīng)十分熟悉，但是也有一些部分需要先對代數(shù)結(jié)構(gòu)中的群論有初步了解才能進(jìn)行學(xué)習(xí)。組合數(shù)學(xué)在競賽中很少以難題的形式出現(xiàn)，但是如果積累不夠，任何一道這方面的題目卻都有可能成為難題。

2、數(shù)論——以素?cái)?shù)判斷和同余為模型構(gòu)造出來的題目往往需要較多的數(shù)論知識(shí)來解決，這部分在競賽中的比重并不大，但只要來上一道，也足以使知識(shí)不足的人冥思苦想上一陣時(shí)間。素?cái)?shù)判斷和同余最常見的是在以密碼學(xué)為背景的題目中出現(xiàn)，在運(yùn)用密碼學(xué)常識(shí)確定大概的過程之后，核心算法往往要涉及數(shù)論的內(nèi)容。

3、計(jì)算幾何——計(jì)算幾何相比于其它部分來說是比較獨(dú)立的，就是說它和其它的知識(shí)點(diǎn)很少有過多的結(jié)合，較常用到的部分包括——線段相交的判斷、多邊形面積的計(jì)算、內(nèi)點(diǎn)外點(diǎn)的判斷、凸包等等。計(jì)算幾何的題目難度不會(huì)很大，但也永遠(yuǎn)不會(huì)成為最弱的題。

4、線性代數(shù)——對線性代數(shù)的應(yīng)用都是圍繞矩陣展開的，一些表面上是模擬的題目往往可以借助于矩陣來找到更好的算法。

5、概率論——競賽是以黑箱來判卷的，這就是說你幾乎不能動(dòng)使用概率算法的念頭，但這也并不是說概率就沒有用。關(guān)于這一點(diǎn)，只有通過一定的練習(xí)才能體會(huì)。而且近年來概率題出現(xiàn)的次數(shù)越來越多了.

6、初等數(shù)學(xué)與解析幾何——這主要就是中學(xué)的知識(shí)了，用的不多，但是至少比高等數(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)識(shí)的許多人去搞信息學(xué)的競賽就是為了逼著自己多學(xué)一點(diǎn)數(shù)學(xué)，因?yàn)閿?shù)學(xué)是一切一切的基礎(chǔ)。

三、數(shù)據(jù)結(jié)構(gòu)與算法是真正的核心

雖然數(shù)學(xué)十分十分重要，但是如果讓三個(gè)只會(huì)數(shù)學(xué)的人參加比賽，我相信多數(shù)情況下會(huì)比三個(gè)只會(huì)數(shù)據(jù)結(jié)構(gòu)與算法的人得到更為悲慘的結(jié)局。

先說說數(shù)據(jù)結(jié)構(gòu)。掌握隊(duì)列、堆棧和圖的基本表達(dá)與操作是必需的，至于樹，我個(gè)人覺得需要建樹的問題有但是并不多。（但是樹往往是很重要的分析工具）除此之外，排序和查找并不需要對所有方式都能很熟練的掌握，但你必須保證自己對于各種情況都有一個(gè)在時(shí)間復(fù)雜度上滿足最低要求的解決方案。說到時(shí)間復(fù)雜度，就又該說說哈希表了，競賽時(shí)對時(shí)間的限制遠(yuǎn)遠(yuǎn)多于對空間的限制，這要求大家盡快掌握“以空間換時(shí)間”的原則策略，能用哈希表來存儲(chǔ)的數(shù)據(jù)一定不要到時(shí)候再去查找，如果實(shí)在不能建哈希表，再看看能否建二叉查找樹等等——這都是爭取時(shí)間的策略，掌握這些技巧需要大家對數(shù)據(jù)結(jié)構(gòu)尤其是算法復(fù)雜度有比較全面的理性和感性認(rèn)識(shí)。

接著說說算法。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。這里要說的是，有些初學(xué)者在學(xué)習(xí)這些搜索基本算法是不太注意剪枝，這是十分不可取的，因?yàn)樗兴阉鞯念}目給你的測試用例都不會(huì)有很大的規(guī)模，你往往察覺不出程序運(yùn)行的時(shí)間問題，但是真正的測試數(shù)據(jù)一定能過濾出那些沒有剪枝的算法。實(shí)際上參賽選手基本上都會(huì)使用常用的搜索算法，題目的區(qū)分度往往就是建立在諸如剪枝之類的優(yōu)化上了。

常用算法中的另一類是以“相似或相同子問題”為核心的，包括遞推、遞歸、貪心法和動(dòng)態(tài)規(guī)劃。這其中比較難于掌握的就是動(dòng)態(tài)規(guī)劃，如何抽象出重復(fù)的子問題是很多題目的難點(diǎn)所在，筆者建議初學(xué)者仔細(xì)理解圖論中一些以動(dòng)態(tài)規(guī)劃為基本思想所建立起來的基本算法（比如Floyd-Warshall算法），并且多閱讀一些定理的證明，這雖然不能有什么直接的幫助，但是長期堅(jiān)持就會(huì)對思維很有幫助。

四、團(tuán)隊(duì)配合

通過以上的介紹大家也可以看出，信息學(xué)競賽對于知識(shí)面覆蓋的非常廣，想憑一己之力全部消化這些東西實(shí)在是相當(dāng)困難的，這就要求我們盡可能地發(fā)揮團(tuán)隊(duì)協(xié)作的精神。同組成員之間的熟練配合和默契的形成需要時(shí)間，具體的情況因成員的組成不同而不同，這里我就不再多說了。


五、練習(xí)、練習(xí)、再練習(xí)

知識(shí)的積累固然重要，但是信息學(xué)終究不是看出來的，而是練出來的，這是多少前人最深的一點(diǎn)體會(huì)，只有通過具體題目的分析和實(shí)踐，才能真正掌握數(shù)學(xué)的使用和算法的應(yīng)用，并在不斷的練習(xí)中增加編程經(jīng)驗(yàn)和技巧，提高對時(shí)間復(fù)雜度的感性認(rèn)識(shí)，優(yōu)化時(shí)間的分配，加強(qiáng)團(tuán)隊(duì)的配合?？傊谶@里光有紙上談兵是絕對不行的，必須要通過實(shí)戰(zhàn)來鍛煉自己。\

大家平時(shí)可以在NOJ,ZOJ或者POJ 多多做些題目,有很多時(shí)候是熟能生巧,而且在做題目的過程中會(huì)碰到很多以前沒有接觸過的算法與數(shù)據(jù)結(jié)構(gòu),是一種很好的學(xué)習(xí)方法.



看到這里我估計(jì)大家有些地方也是看的云里來霧里去了,^_^,不過相信幾年后,大家對此會(huì)深有體會(huì)的.針對于我們學(xué)校的情況,下面是我的一些建議.

1. 盡快掌握C語言,并且自學(xué)C++.
2. 沒學(xué)過數(shù)據(jù)結(jié)構(gòu)的找本數(shù)據(jù)結(jié)構(gòu)的書仔細(xì)的從頭看到尾.
3. 找一個(gè)算法書.比如C算法第一卷(集訓(xùn)隊(duì)里有這本書的),也從頭看到尾.
4. 對于算法問題,一定要花時(shí)間去理解,不要輕易放過.
5. 學(xué)會(huì)用google和百度來解決你所碰到的問題.在隊(duì)里我們沒有像高中那樣有上課的形式,我們推崇培養(yǎng)大家自己動(dòng)力解決實(shí)際問題的能力,每次比賽完后我們都會(huì)有一次討論,讓大家彼此交流,需要大家到時(shí)在積極發(fā)言.
6. 不懂就問.
7. 剛剛開始的時(shí)候先多做些模擬題或者簡單題目.所謂模擬題是指基本是沒啥算法的題目,題目里已經(jīng)清楚告訴怎么做的.一般來說NOJ上的中文題目是比較簡單的.
8. 對于各種算法的學(xué)習(xí),可以看個(gè)人興趣,推薦先學(xué)計(jì)算幾何,然后圖論,搜索,DFS,BFS,然后動(dòng)態(tài)規(guī)劃,


acm.nit.net.cn

關(guān)于編程

1. 平時(shí)盡量使用VC或者DEVC++進(jìn)行編譯.
2. 學(xué)會(huì)DEBUG
3. 要養(yǎng)成良好的代碼風(fēng)格.變量名不要亂起,盡量用題目中的名詞.推薦用匈牙利命名法.
4. 因?yàn)楸荣惖臅r(shí)候做簡單題目拼的是寫代碼的速度,所以花點(diǎn)時(shí)間練習(xí)一下打字還是必要的.
5. 平時(shí)每份代碼都要有注釋
像這種格式
/*
Name:
Copyright:
Author:
Date: 06-02-06 20:58
Description:
*/
當(dāng)然你可以寫的更加詳細(xì)些,在注釋里簡單描述一下這份代碼所采用的算法.




我代表大四那些將要離開ACM的隊(duì)員祝愿大家在以后的日子里能夠青出于藍(lán),為理工創(chuàng)造輝煌,有新的突破.也希望大家在以后的日子里,還是努力一點(diǎn),少玩一點(diǎn),刻苦一點(diǎn),將來的成就也多一點(diǎn),遺憾也會(huì)少一點(diǎn).或許只有你們到了我們這個(gè)年級(jí)的時(shí)候,才會(huì)深刻理解前面短短一句話的感慨.