Posted on 2006-08-13 17:58
oyjpart 閱讀(819)
評(píng)論(4) 編輯 收藏 引用
首先是理論學(xué)習(xí) 對(duì)ACM拿到概要性的把握
1、離散數(shù)學(xué)——作為計(jì)算機(jī)學(xué)科的基礎(chǔ)，離散數(shù)學(xué)是競(jìng)賽中涉及最多的數(shù)學(xué)分支，其重中之重又在于圖論和組合數(shù)學(xué)，尤其是圖論。
2、數(shù)論——以素?cái)?shù)判斷和同余為模型構(gòu)造出來(lái)的題目往往需要較多的數(shù)論知識(shí)來(lái)解決，這部分在競(jìng)賽中的比重并不大，但只要來(lái)上一道，也足以使知識(shí)不足的人冥思苦想上一陣時(shí)間。素?cái)?shù)判斷和同余最常見(jiàn)的是在以密碼學(xué)為背景的題目中出現(xiàn)，在運(yùn)用密碼學(xué)常識(shí)確定大概的過(guò)程之后，核心算法往往要涉及數(shù)論的內(nèi)容。
3、計(jì)算幾何——較常用到的部分包括——線段相交的判斷、多邊形面積的計(jì)算、內(nèi)點(diǎn)外點(diǎn)的判斷、凸包等等。計(jì)算幾何的題目難度不會(huì)很大，但也永遠(yuǎn)不會(huì)成為最弱的題。
4、線性代數(shù)——對(duì)線性代數(shù)的應(yīng)用都是圍繞矩陣展開(kāi)的，一些表面上是模擬的題目往往可以借助于矩陣來(lái)找到更好的算法。
先說(shuō)說(shuō)數(shù)據(jù)結(jié)構(gòu)。掌握隊(duì)列、堆棧和圖的基本表達(dá)與操作是必需的，至于樹(shù)，我個(gè)人覺(jué)得需要建樹(shù)的問(wèn)題有但是并不多。（但是樹(shù)往往是很重要的分析工具）除此之外，排序和查找并不需要對(duì)所有方式都能很熟練的掌握，但你必須保證自己對(duì)于各種情況都有一個(gè)在時(shí)間復(fù)雜度上滿足最低要求的解決方案。說(shuō)到時(shí)間復(fù)雜度，就又該說(shuō)說(shuō)哈希表了，競(jìng)賽時(shí)對(duì)時(shí)間的限制遠(yuǎn)遠(yuǎn)多于對(duì)空間的限制，這要求大家盡快掌握“以空間換時(shí)間”的原則策略，能用哈希表來(lái)存儲(chǔ)的數(shù)據(jù)一定不要到時(shí)候再去查找，如果實(shí)在不能建哈希表，再看看能否建二叉查找樹(shù)等等——這都是爭(zhēng)取時(shí)間的策略，掌握這些技巧需要大家對(duì)數(shù)據(jù)結(jié)構(gòu)尤其是算法復(fù)雜度有比較全面的理性和感性認(rèn)識(shí)。
接著說(shuō)說(shuō)算法。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。這里要說(shuō)的是，有些初學(xué)者在學(xué)習(xí)這些搜索基本算法是不太注意剪枝，這是十分不可取的，因?yàn)樗兴阉鞯念}目給你的測(cè)試用例都不會(huì)有很大的規(guī)模，你往往察覺(jué)不出程序運(yùn)行的時(shí)間問(wèn)題，但是真正的測(cè)試數(shù)據(jù)一定能過(guò)濾出那些沒(méi)有剪枝的算法。實(shí)際上參賽選手基本上都會(huì)使用常用的搜索算法，題目的區(qū)分度往往就是建立在諸如剪枝之類(lèi)的優(yōu)化上了。
?常用算法中的另一類(lèi)是以“相似或相同子問(wèn)題”為核心的，包括遞推、遞歸、貪心法和動(dòng)態(tài)規(guī)劃。這其中比較難于掌握的就是動(dòng)態(tài)規(guī)劃，如何抽象出重復(fù)的子問(wèn)題是很多題目的難點(diǎn)所在，筆者建議初學(xué)者仔細(xì)理解圖論中一些以動(dòng)態(tài)規(guī)劃為基本思想所建立起來(lái)的基本算法（比如Floyd-Warshall算法），并且多閱讀一些定理的證明，這雖然不能有什么直接的幫助，但是長(zhǎng)期堅(jiān)持就會(huì)對(duì)思維很有幫助。
學(xué)到的最經(jīng)典的話：
OI是好學(xué)生的游戲。
我對(duì)DP的提煉：
動(dòng)態(tài)規(guī)劃的性質(zhì)：1。最優(yōu)子結(jié)構(gòu)--設(shè)計(jì)狀態(tài) 2。無(wú)后效性--狀態(tài)轉(zhuǎn)移
動(dòng)態(tài)規(guī)劃的動(dòng)機(jī)：1。利用遞歸的重疊子問(wèn)題，進(jìn)行記憶化求解。
????????????????????????? ????? 2。把問(wèn)題看作是多階段決策過(guò)程，是動(dòng)態(tài)規(guī)劃的第二種情形。
個(gè)人對(duì)于DP中的階段理解：
對(duì)于DP中的階段 不僅僅存在與多階段決策問(wèn)題中， 比如矩陣鏈乘問(wèn)題中 我們可以把d[i][j]中的j-i長(zhǎng)度看成是階段 這樣就符合了階段的存在性
如：
function matrix_chain_order(p)
{
?for(i=1 to n) m[i,i]=0;
?for(l=2 to n)?? //長(zhǎng)度！
? for(i=1 to n-l+1) //該長(zhǎng)度下的首個(gè)matrix
? {
?? j=i+l-1;?????? //該長(zhǎng)度下的末matrix
?? m[i,j]=無(wú)窮大;? //求最小值設(shè)最大
?? for(k=i to j-1)? //根據(jù)狀態(tài)轉(zhuǎn)移方程中的k來(lái)決定的
?? {
??? q=m[i,k]+m[k+1,j]+Pi-1PkPj? //等與兩子鏈的耗費(fèi)加上此2子鏈乘之耗費(fèi)
??? if(q<m[i,j])
???? {m[i,j]=q; s[i,k]=k;}
?? }
? }
}
學(xué)習(xí)離散數(shù)學(xué)的理解
哈密頓回路:在圖中找出一條包含所有結(jié)點(diǎn)的閉路，并且，出來(lái)起點(diǎn)和重點(diǎn)重合外，這條閉路所含結(jié)點(diǎn)是互不相同的 可以在多項(xiàng)式時(shí)間類(lèi)判斷一個(gè)回路是否是哈密頓回路 但目前沒(méi)有算法直接解出哈密頓回路
歐拉回路，歐拉圖：圖G中包含其所有邊的簡(jiǎn)單開(kāi)路稱為G的歐拉路徑。圖G中包含其所有邊的簡(jiǎn)單閉路徑稱為歐拉有向圖。這個(gè)其實(shí)就是我小學(xué)學(xué)的一筆劃問(wèn)題！我暈 ~
哈密頓回路,貨郎擔(dān)問(wèn)題，集團(tuán)問(wèn)題，最小邊覆蓋問(wèn)題（注意和路徑覆蓋的區(qū)別），等等很多問(wèn)題都是NPC問(wèn)題，NP完全問(wèn)題（NPC問(wèn)題，C代表complete）。NPC問(wèn)題存在著一個(gè)令人驚訝的性質(zhì)，即如果一個(gè)NPC 問(wèn)題存在多項(xiàng)式時(shí)間的算法，則所有的NP問(wèn)題都可以在多項(xiàng)式時(shí)間內(nèi)求解，即P=NP成立！！
呵呵 記的起的就這么多啦~