Feng.Li's Java See

首先歡迎大家加入NIT_ACM程序設計集訓隊這個大家庭,希望接下來的日子里,大家都喜歡上寫程序,喜歡上ACM/ICPC, enjoy it and love it.

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

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


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

C語言學習推薦:C程序設計(譚浩強編著)
C++學習推薦: C++Prime, C++大學教程.(其實基本上的C++教程都行的…)
STL學習推薦: C++Prime,STL標準庫.(理論聯系實際,邊學就用學的最快)

二、以數學為主的基礎知識十分重要

雖然被定性為程序設計競賽，但是參賽選手所遇到的問題更多的是沒有解決問題的思路，而不是有了思路卻死活不能實現，這就是平時積累的基礎知識不夠。競賽中對于基礎學科的涉及主要集中于數學，此外對于物理、電路等等也可能有一定應用，但是不多。因此，大一的同學也不必為自己還沒學數據結構而感到不知從何入手提高，把數學撿起來吧！下面來談談在競賽中應用的數學的主要分支。

1、離散數學——作為計算機學科的基礎，離散數學是競賽中涉及最多的數學分支，其重中之重又在于圖論和組合數學，尤其是圖論。

圖論之所以運用最多是因為它的變化最多，而且可以輕易地結合基本數據結構和許多算法的基本思想，較多用到的知識包括連通性判斷、DFS和BFS，關節點和關鍵路徑、歐拉回路、最小生成樹、最短路徑、二部圖匹配和網絡流等等。雖然這部分的比重很大，但是往往也是競賽中的難題所在，如果有初學者對于這部分的某些具體內容暫時感到力不從心，也不必著急，可以慢慢積累。

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

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

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

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

5、概率論——競賽是以黑箱來判卷的，這就是說你幾乎不能動使用概率算法的念頭，但這也并不是說概率就沒有用。關于這一點，只有通過一定的練習才能體會。而且近年來概率題出現的次數越來越多了.

6、初等數學與解析幾何——這主要就是中學的知識了，用的不多，但是至少比高等數學多，我覺得熟悉一下數學手冊上的相關內容，至少要知道在哪兒能查到，還是必要的。

7、高等數學——純粹運用高等數學來解決的題目我接觸的只有一道，但是一些題目的敘述背景往往需要和這部分有一定聯系，掌握得牢固一些總歸沒有壞處。

以上就是競賽所涉及的數學領域，可以說范圍是相當廣的。我認識的許多人去搞信息學的競賽就是為了逼著自己多學一點數學，因為數學是一切一切的基礎。

三、數據結構與算法是真正的核心

雖然數學十分十分重要，但是如果讓三個只會數學的人參加比賽，我相信多數情況下會比三個只會數據結構與算法的人得到更為悲慘的結局。

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

接著說說算法。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。這里要說的是，有些初學者在學習這些搜索基本算法是不太注意剪枝，這是十分不可取的，因為所有搜索的題目給你的測試用例都不會有很大的規模，你往往察覺不出程序運行的時間問題，但是真正的測試數據一定能過濾出那些沒有剪枝的算法。實際上參賽選手基本上都會使用常用的搜索算法，題目的區分度往往就是建立在諸如剪枝之類的優化上了。

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

四、團隊配合

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


五、練習、練習、再練習

知識的積累固然重要，但是信息學終究不是看出來的，而是練出來的，這是多少前人最深的一點體會，只有通過具體題目的分析和實踐，才能真正掌握數學的使用和算法的應用，并在不斷的練習中增加編程經驗和技巧，提高對時間復雜度的感性認識，優化時間的分配，加強團隊的配合?？傊?，在這里光有紙上談兵是絕對不行的，必須要通過實戰來鍛煉自己。\

大家平時可以在NOJ,ZOJ或者POJ 多多做些題目,有很多時候是熟能生巧,而且在做題目的過程中會碰到很多以前沒有接觸過的算法與數據結構,是一種很好的學習方法.



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

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


acm.nit.net.cn

關于編程

1. 平時盡量使用VC或者DEVC++進行編譯.
2. 學會DEBUG
3. 要養成良好的代碼風格.變量名不要亂起,盡量用題目中的名詞.推薦用匈牙利命名法.
4. 因為比賽的時候做簡單題目拼的是寫代碼的速度,所以花點時間練習一下打字還是必要的.
5. 平時每份代碼都要有注釋
像這種格式
/*
Name:
Copyright:
Author:
Date: 06-02-06 20:58
Description:
*/
當然你可以寫的更加詳細些,在注釋里簡單描述一下這份代碼所采用的算法.




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