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