acm基礎(chǔ)算法入門講述-預(yù)覽頁
【正文】 經(jīng)典,第二頁，共三十五頁。,求解從頂?shù)较陆?jīng)過節(jié)點的最大值是多少,第六頁，共三十五頁。 如：1 9 10 5 11 2 13的最長單調(diào)遞增子序列是1 9 10 11 13，長度為5。,貪心的三種區(qū)間問題,選擇不相交區(qū)間 區(qū)間選點 區(qū)間覆蓋,第十一頁，共三十五頁。接下來，按照bi從小到大的順序?qū)?所有區(qū)間排序。 注意：排序后第一個區(qū)間一定會選，因為它的bi最小， 它不影響后面區(qū)間的選取，而且如果不選此區(qū)間，最終 求出的區(qū)間數(shù)目會變少。,【分析】 如果區(qū)間i內(nèi)已經(jīng)有一個點被取到，我們稱此區(qū)間已經(jīng)被 滿足。 因此，我們把所有區(qū)間按b從小到大排序（b相同時a從 大到小排序），則如果出現(xiàn)區(qū)間包含的情況，小區(qū)間一定排 在前面。,解題思路,根據(jù)剛才的討論，所有需要考慮的區(qū)間的a也是遞增的， 我們把它畫成上圖的形式。,區(qū)間覆蓋問題,數(shù)軸上有n個閉區(qū)間[ai, bi]，選擇盡量少的區(qū)間覆蓋 一條指定線段[s, t]。在預(yù)處理后，在相互包含的情況 下，小區(qū)間顯然不應(yīng)該被考慮。選擇此 區(qū)間[ai,bi]后，新的起點應(yīng)該被設(shè)置為bi,并且忽略所有區(qū)間在 bi之前的部分，就像預(yù)處理一樣。,s,第十七頁，共三十五頁。 它從某個狀態(tài)開始，不斷地轉(zhuǎn)移狀態(tài)直到無法轉(zhuǎn)移，然后回退到前一步的狀態(tài)，繼續(xù)轉(zhuǎn)移到其他狀態(tài)，如此不斷重復(fù)，直至找到最終的解。 限制條件： 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,第二十頁，共三十五頁。與深度優(yōu)先搜索類似，從某個狀態(tài)出發(fā)探索所有可以到達(dá)的狀態(tài)。,第二十二頁，共三十五頁。139。139。039。,第二十四頁，共三十五頁。,數(shù)論基礎(chǔ),輾轉(zhuǎn)相除法 有關(guān)素數(shù)的基礎(chǔ)算法 快速冪,求最大公約數(shù) 擴(kuò)展歐幾里得 ax+by=gcd(a,b),埃氏篩法 區(qū)間篩法,第二十六頁，共三十五頁。 格子如下： …… 4 3 2 1 0 1 2 3 4 …… 擲出四個整數(shù)各多少次可以到達(dá)終點？輸出任意一組解。反之，則可以通過擴(kuò)展輾轉(zhuǎn)相除法來求解。 bx2+(a mod b)y2=gcd(b,a mod b)。 根據(jù)恒等定理得：x1=y2。,埃氏篩法,給定整數(shù)n，請問n以內(nèi)多少個素數(shù) n=10^6 輸入 25 輸出 9,第二十九頁，共三十五頁。,第三十頁，共三十五頁。,人有了知識，就會具備各種分析能力， 明辨是非的能力。,第三十三頁，共三十五頁。dp【i】以i為結(jié)束節(jié)點最長單調(diào)子序列長度。從a1開始按順序決定每個數(shù)加或不加，在全部n個數(shù)決定后在判斷他們的和是不是k
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1