ACM程序設(shè)計(jì)大賽概況

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