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