ACM程序設計大賽概況

砌程序設計大賽概兄一、ACM大賽簡介ACM國際大學生程序設計競賽（ACM/ICPC：ACMInternationalCollegiateProgrammingContest）是由國際計算機界歷史悠久、頗具權(quán)威性的組織ACM學會（AssociationforComputingMachinery,美國計算機協(xié)會）主辦，是世界上公認的規(guī)模最大、水平最高的國際大學生程序設計競賽，其目的旨在使大學生運用計算機來充分展示自已分析問題和解決問題的能力。該項競賽從1970年舉辦至今已歷27屆，因歷屆競賽都薈萃了世界各大洲的精英，云集了計算機界的“希望之星”，而受到國際各知名大學的重視，并受到全世界各著名計算機公司的高度關(guān)注，成為世界各國大學生最具影響力的國際級計算機類的賽事。該項競賽分區(qū)域預賽和國際決賽兩個階段進行，各預賽區(qū)第一名自動獲得參加世界決賽的資格，世界決賽安排在每年的3-4月舉行，而區(qū)域預賽安排在上一年的9-12月在各大洲舉行。這項比賽是以大學為單位組隊（每支隊伍由教練、3名正式隊員，一名后備隊員組成）參賽。ACM/ICPC的區(qū)域預賽是規(guī)模很大、范圍很廣的賽事。中國內(nèi)地從1996年開始參加ACM/ICPC亞洲區(qū)預賽，至今已歷九屆。在賽事的早期，冠軍多為美國和加拿大的大學獲得。而進入1990年代后期以來，俄羅斯和其它一些東歐國家的大學連奪數(shù)次冠軍。來自中國大陸的上海交通大學代表隊則在2002年美國夏威夷第26屆和2005年上海舉行的第29屆全球總決賽上兩奪冠軍。這也是目前為止亞洲大學在該競賽上取得的最好成績。二、比賽形式經(jīng)過校級和地區(qū)級選拔的參賽組，于指定的時間、地點參加世界級的決賽，由3個成員組成的小組應用一臺計算機解決6到8個生活中的實際問題。參賽隊員必須在5小時內(nèi)編完程序并進行測試和調(diào)試。ACM/ICPC以團隊的形式代表各學校參賽，每隊由3名隊員組成。每位隊員必須是入校5年內(nèi)的在校學生，最多可以參加2次全球總決賽和4次區(qū)域選拔賽。比賽期間，每隊使用1臺電腦需要在5個小時內(nèi)使用C、C++、Pascal或Java中的一種編寫程序解決8或10個問題（通常是區(qū)域選拔賽8題，全球總決賽10題）。程序完成之后提交裁判運精品word文檔值得下載值得擁有行，運行的結(jié)果會判定為正確或錯誤兩種并及時通知參賽隊。每隊在正確完成一題后，組織者將在其位置上升起一只代表該題顏色的氣球。最后的獲勝者為正確解答題目最多且總用時最少的隊伍。每道試題用時將從競賽開始到試題解答被判定為正確為止，其間每一次提交運行結(jié)果被判錯誤的話將被加罰20分鐘時間，未正確解答的試題不記時。例如：A、B兩隊都正確完成兩道題目，其中A隊提交這兩題的時間分別是比賽開始后1:00和2:45,B隊為1:20和2:00，但B隊有一題提交了2次。這樣A隊的總用時為1:00+2:45=3:45而B隊為1:20+2:00+0:20=3:40，所以B隊以總時少而獲勝。三、基礎(chǔ)知識儲備編程語言亞洲賽區(qū)的比賽支持的語言包括C/C++與JAVA。JAVA對于輸入輸出流的操作相比于C++要繁雜很多，更為重要的是JAVA程序的運行速度要比C++慢10倍以上，而競賽中對于JAVA程序的運行時限卻往往得不到同等比例的放寬，這無疑對算法設計提出了更高的要求，是相當不利的。許多參賽同學C的基礎(chǔ)知識剛剛學完，還沒有接觸過C++，其實在賽場上使用純C的選手還是大有人在的，它們主要是看重了純C在效率上的優(yōu)勢，只要提高了自己在算法設計上的造詣，純C一樣能發(fā)揮巨大的威力。而C++相對于C，在輸入輸出流上的封裝大大方便了我們的操作，同時降低了出錯的可能性，并且能夠很好地實現(xiàn)標準流與文件流的切換，方便了調(diào)試工作。C++的另一個支持來源于標準模版庫（STL），庫中提供的對于基本數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一接口操作和基本算法的實現(xiàn)可以縮減我們編寫代碼的長度，這可以節(jié)省一些時間。但是熟練和恰當?shù)厥褂肧TL必須經(jīng)過一定時間的積累，準確地了解各種操作的時間復雜度。數(shù)學雖然被定性為程序設計競賽，但是參賽選手所遇到的問題更多的是沒有解決問題的思路，而不是有了思路卻死活不能實現(xiàn)，這就是平時積累的數(shù)學基礎(chǔ)知識不夠。2007年WorldFinal的總冠軍是波蘭華沙大學，其成員出自于數(shù)學系而非計算機系，這就是一個鮮活的例子。A離散數(shù)學一一作為計算機學科的基礎(chǔ)，離散數(shù)學是競賽中涉及最多的數(shù)學分支，重中之重又在于圖論和組合數(shù)學，尤其是圖論。圖論之所以運用最多是因為它的變化最多，而且可以輕易地結(jié)合基本數(shù)據(jù)結(jié)構(gòu)和許多算法的基本思想，較多用到的知識包括連通性判斷、DFS和BFS，關(guān)節(jié)點和關(guān)鍵路徑、歐拉回路、最小生成樹、最短路徑、二部圖匹配和網(wǎng)絡流等等。＞組合數(shù)學一一組合數(shù)學中的知識相比于圖論要簡單一些，但是也有一些部分需要先對代數(shù)結(jié)構(gòu)中的群論有初步了解才能進行學習。組合數(shù)學在競賽中很少以難題的形式出現(xiàn)，但是如果積累不夠，任何這方面的題目都有可能成為難題。＞數(shù)論一一以素數(shù)判斷和同余為模型構(gòu)造出來的題目往往需要較多的數(shù)論知識來解決，素數(shù)判斷和同余最常見的是在以密碼學為背景的題目中出現(xiàn)，在運用密碼學常識確定大概的過程之后，核心、算法往往要涉及數(shù)論的內(nèi)容。＞計算幾何一一計算幾何相比于其它部分來說是比較獨立的，較常用到的部分包括線段相交的判斷、多邊形面積的計算、內(nèi)點外點的判斷、凸包等等。＞線性代數(shù)一一對線性代數(shù)的應用都是圍繞矩陣展開的，一些表面上是模擬的題目往往可以借助于矩陣來找到更好的算法。＞概率論一一競賽是以黑箱來判卷的，幾乎很少用到概率算法，但這并不意味著概率就沒有用。＞高等數(shù)學一一純粹運用高等數(shù)學求解的題目比較少，但高等數(shù)學是很多算法的基礎(chǔ)，需要掌握牢固。四、核心知識1.數(shù)據(jù)結(jié)構(gòu)掌握隊列、堆棧和圖的基本表達與操作是必需的，排序和查找并不需要對所有方式都能很熟練的掌握，但必須保證對于各種情況都有一個在時間復雜度上滿足最低要求的解決方案。競賽時對時精品word文檔值得下載值得擁有精品word文檔值得下載值得擁有間的限制遠遠多于對空間的限制，這要求大家盡快掌握“以空間換時間”的策略，對哈希表、二叉查找樹等算法及其復雜度有比較全面的理性和感性認識。.算法算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。常用算法中的另一類是以“相似或相同子問題”為核心的，包括遞推、遞歸、貪心、法和動態(tài)規(guī)劃。五、團隊配合信息學競賽對于知識面覆蓋的非常廣，憑一己之力全部消化這些東西實在是相當困難的，這就要求盡可能地發(fā)揮團隊協(xié)作的精神。同組成員之間的熟練配合和默契的形成需要時間，具體的情況因成員的組成不同而不同。六、勤加練習通過具體題目的分析和實踐，才能真正掌握數(shù)學的使用和算法的應用，并在不斷的練習中增加編程經(jīng)驗和技巧，提高對時間復雜度的感性認識，優(yōu)化時間的分配，加強團隊的配合?？傊?，光有紙上談兵是絕對不行的，必須要通過實戰(zhàn)來鍛煉自己。七、參考網(wǎng)站現(xiàn)在已經(jīng)有了很多網(wǎng)上做題的站點，這些站點提供了大量的題庫并支持在線判卷，只需要把程序源碼提交上去，馬上就可以知道程序是否正確，運行所使用的時間以及消耗的內(nèi)存等等狀況。下面推薦幾個站點，每個站點的題都有一定的難易比例，系統(tǒng)地做一套題庫可以對各種難度、各種類型的題都有所認識。1、Ural:Ural是中國學生對俄羅斯的Ural州立大學的簡稱，那里設立了一個UralOnlineProblemSet，并且支持OnlineJudgeoUral的不少題目算法性和趣聞性都很強。2、UVA：UVA代表西班牙Valladolid大學。該大學有一個那里設立了一個PROBLEMSETARCHIVEwithONLINEJUDGE，并且支持ONLINEJUDGE，形式和Ural大學的題庫類似。不過和Ural不同的是，UVA題目多的多，而且比較雜，而且有些題目的測試數(shù)據(jù)比較刁鉆。如果說做Ural題目主要是為了訓練算法，那么UVA題目可以訓練全方位的基本功和一些必要的編程素質(zhì)。3、ZOJ浙江大學建立的ONLINE