acm基礎(chǔ)算法入門講述(更新版)
【正文】 能力的競賽。 y1=x2(a/b)*y2。 設(shè) ab。,輾轉(zhuǎn)相除法,擴(kuò)展歐幾里得 雙六 一個(gè)雙六上面有向前向后無限延續(xù)的格子，每個(gè)格子都寫有整數(shù)。因此，直到圖中不再存在39。的出發(fā)，將這點(diǎn)的坐標(biāo)上下左右全部用39。 與深度優(yōu)先搜索的不同在于搜索的順序，寬度優(yōu)先搜索總是先搜索距離初始狀態(tài)近的狀態(tài)，也就是說它是按照開始狀態(tài)只需1次轉(zhuǎn)移就可到達(dá)的所有狀態(tài)只需2次轉(zhuǎn)移就可到達(dá)的狀態(tài)，這樣的順序進(jìn)行搜索。 根據(jù)深度優(yōu)先搜索的特點(diǎn)，采用遞歸函數(shù)實(shí)現(xiàn)比較簡單。雖然貪心策略比上面的題 復(fù)雜，但是仍然只需要一次掃描。,【分析】 本題的突破口仍然是區(qū)間包含和排序掃描，不過要先 進(jìn)行一次預(yù)處理。第一個(gè)區(qū)間應(yīng)該選取哪一個(gè)點(diǎn)呢？正確的貪心策略 是：取最后一個(gè)點(diǎn)。,第十三頁，共三十五頁。,選擇不相交區(qū)間,數(shù)軸上有n個(gè)開區(qū)間（ai,bi），選擇盡量多個(gè)區(qū)間， 使得這些區(qū)間兩兩沒有公共點(diǎn)。,解題思路,列狀態(tài) v [ I ] [ j ]表示走到第i層的第j個(gè)節(jié)點(diǎn)的最大值 分階段 每一個(gè)層就是一個(gè)階段 狀態(tài)轉(zhuǎn)移方程（決策） V [ i1 ] [ j ] += V [ I ] [ j ] v [ I ] [ j + 1 ] ? V [ I ] [ j ] : v [ I ] [ j + 1 ]。,引言,算法簡單但思想及其重要 介紹的算法都堪稱為經(jīng)典中的經(jīng)典,第二頁，共三十五頁。 如：1 9 10 5 11 2 13的最長單調(diào)遞增子序列是1 9 10 11 13，長度為5。接下來，按照bi從小到大的順序?qū)?所有區(qū)間排序。,【分析】 如果區(qū)間i內(nèi)已經(jīng)有一個(gè)點(diǎn)被取到，我們稱此區(qū)間已經(jīng)被 滿足。,解題思路,根據(jù)剛才的討論，所有需要考慮的區(qū)間的a也是遞增的， 我們把它畫成上圖的形式。在預(yù)處理后，在相互包含的情況 下，小區(qū)間顯然不應(yīng)該被考慮。,s,第十七頁，共三十五頁。 限制條件： 1=n20 10^8=ai=10^8 10^8=k=10^8 輸入： 4 1,2,4,7 13 輸出： Yes,輸入： 4 1,2,4,7 15 輸出： No,第二十頁，共三十五頁。,第二十二頁，共三十五頁。139。,第二十四頁，共三十五頁。 格子如下： …… 4 3 2 1 0 1 2 3 4 …… 擲出四個(gè)整數(shù)各多少次可以到達(dá)終點(diǎn)？輸出任意一組解。 bx2+(a mod b)y2=gcd(b,a mod b)。,埃氏篩法,給定整數(shù)n，請(qǐng)問n以內(nèi)多少個(gè)素?cái)?shù) n=10^6 輸入 25 輸出 9,第二十九頁，共三十五頁。,人有了知識(shí)，就會(huì)具備各種分析能力， 明辨是非的能力。dp【i】以i為結(jié)束節(jié)點(diǎn)最長單調(diào)子序列
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1