? ? ? ? 現(xiàn)在越來越多的同學(xué)開始對acm競賽感興趣端考，想要去一展身手，拿到一個(gè)不錯(cuò)的獎(jiǎng)項(xiàng)來證明自己揭厚。有這個(gè)想法固然是好的跛梗，不過acm競賽中能夠拿到獎(jiǎng)項(xiàng)的難度還是很大的。需要很多方面做到最好棋弥，下面就針對大家需要努力的方向給大家簡單介紹一下需要注意的點(diǎn)核偿。??
? ? ? ? 一、語言是最重要的基本功? ?
? ? ? ? ?無論側(cè)重于什么方面顽染，只要是通過計(jì)算機(jī)程序去最終實(shí)現(xiàn)的競賽漾岳，語言都是大家要? ?過的第一道關(guān)。亞洲賽區(qū)的比賽支持的語言包括C/C++與JAVA粉寞。今天重點(diǎn)說C和C++尼荆。許多現(xiàn)在參加講座的同學(xué)還在上大一，C的基礎(chǔ)知識(shí)剛剛學(xué)完唧垦，還沒? ?有接觸過C++捅儒，其實(shí)在賽場上使用純C的選手還是大有人在的，它們主要是看重了純C在效? ?率上的優(yōu)勢振亮，所以這部分同學(xué)如果時(shí)間有限巧还，并不需要急著去學(xué)習(xí)新的語言，只要提高? ?了自己在算法設(shè)計(jì)上的造詣坊秸，純C一樣能發(fā)揮巨大的威力麸祷。? ?
? ?? ?? ? 而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)的陷阱创淡。? ?
? ?? ?? ? 通過以上的分析，我們可以看出僅就信息學(xué)競賽而言南吮，對語言的掌握并不要求十分全面琳彩，但是對于經(jīng)常用到的部分，必須十分熟練部凑，不允許有半點(diǎn)不清楚的地方露乏，下面我舉個(gè)真實(shí)的例子來說明這個(gè)道理——即使是一點(diǎn)很細(xì)微的語言障礙，都有可能釀成錯(cuò)誤涂邀。? ?
? ? ? ? ? ?二瘟仿、以數(shù)學(xué)為主的基礎(chǔ)知識(shí)十分重要? ?
? ?? ?? ? 雖然被定性為程序設(shè)計(jì)競賽，但是參賽選手所遇到的問題更多的是沒有解決問題的思路比勉，而不是有了思路卻死活不能實(shí)現(xiàn)劳较，這就是平時(shí)積累的基礎(chǔ)知識(shí)不夠。2013年WorldFinal的總冠軍是波蘭華沙大學(xué)浩聋，其成員出自于數(shù)學(xué)系而非計(jì)算機(jī)系观蜗，這就是一個(gè)鮮活的例子。競賽中對于基礎(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ì)洪鸭。? ?
? ?? ?? ? 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)來鍛煉自己脏榆。? ?
? ? ? ? ? ?acm的比賽固然在很多同學(xué)的心中占有巨大的地位猖毫，但是基礎(chǔ)的c/c++的學(xué)習(xí)依然不能停留，畢竟作為基礎(chǔ)中的基礎(chǔ)姐霍，一定需要打牢鄙麦。想一起學(xué)習(xí)探討C/C++編程的小伙伴可以關(guān)注并私信我“C/C++編程”，一起加油哦镊折！
