ACM基礎(chǔ)算法入門(mén)教程

1、ACM基礎(chǔ)算法入門(mén).基礎(chǔ)動(dòng)態(tài)規(guī)劃.基礎(chǔ)的“窮竭搜索”.貪心的三種區(qū)間問(wèn)題.數(shù)論那些事.二分的另類(lèi)法引言?算法簡(jiǎn)單但思想及其重要介紹的算法都堪稱(chēng)為經(jīng)典中的經(jīng)典基礎(chǔ)動(dòng)態(tài)規(guī)劃多階段決策過(guò)程最優(yōu)化的數(shù)學(xué)方法三要素：-階段-決策-狀態(tài)?動(dòng)態(tài)規(guī)劃的適用范圍最優(yōu)子結(jié)構(gòu)（最優(yōu)化原理）當(dāng)前狀態(tài)依賴(lài)于前面的狀態(tài)得到，是前面狀態(tài)的完美總結(jié)?無(wú)后效性（不成環(huán)）經(jīng)典模型?數(shù)塔模型背包問(wèn)題區(qū)間最大和模型最長(zhǎng)非降子序列模型最長(zhǎng)公共子序列數(shù)字歸并（區(qū)間dp）旅行商問(wèn)題（狀態(tài)壓縮）?求解從頂?shù)较陆?jīng)過(guò)節(jié)點(diǎn)的最大值是多少解題思路列狀態(tài)v I j 表示走到第i層的第j個(gè)節(jié)點(diǎn)的最大值?分階段每一個(gè)層就是一個(gè)階段?狀態(tài)轉(zhuǎn)移方程（決策）?

2、V i-1 j += V I j v I j + 1 ? V I j : v I j + 1 ;單調(diào)遞增非降子序列?給定一整型數(shù)列a1,a2.,an（0n=100000），找出單調(diào)遞增最長(zhǎng)子序列，并求出其長(zhǎng)度。如：1 9 10 5 11 2 13的最長(zhǎng)單調(diào)遞增子序列是1 9 10 11 13，長(zhǎng)度為5。?解題思路定義狀態(tài)dp【i】以i為結(jié)束節(jié)點(diǎn)最長(zhǎng)單調(diào)子序列長(zhǎng)度?階段每一個(gè)點(diǎn)選擇過(guò)程即階段轉(zhuǎn)移方程：Dp【i】= max（dp【1（i-1）】） + 1想想有沒(méi)有更好的方法？?dp總結(jié)?模型匹配法三要素法先確定階段（數(shù)塔問(wèn)題）先確定狀態(tài)（一般題目都是）先確定決策（背包問(wèn)題）貪心的三種區(qū)間問(wèn)題?選擇

3、不相交區(qū)間區(qū)間選點(diǎn)區(qū)間覆蓋?選擇不相交區(qū)間?數(shù)軸上有數(shù)軸上有n個(gè)開(kāi)區(qū)間（個(gè)開(kāi)區(qū)間（ai,bi），選擇盡量多個(gè)區(qū)間，），選擇盡量多個(gè)區(qū)間，使得這些區(qū)間兩兩沒(méi)有公共點(diǎn)。使得這些區(qū)間兩兩沒(méi)有公共點(diǎn)?！痉治觥渴紫让鞔_一個(gè)問(wèn)題：假設(shè)有兩個(gè)區(qū)間x,y,區(qū)間x完全包含y。那么，選x是不劃算的，因?yàn)閤和y最多只能選一個(gè)，選x不如選y，這樣不僅區(qū)間數(shù)目不會(huì)減少，而且給其他區(qū)間留出了更多的位置。接下來(lái)，按照bi從小到大的順序?qū)λ袇^(qū)間排序。會(huì)場(chǎng)安排問(wèn)題?先對(duì)n個(gè)區(qū)間按照bi從小到大的順序排序，如果bi相同，則ai按照從大到小的順序排序。然后從前往后掃描每個(gè)區(qū)間，找出所有的符合條件的區(qū)間。?注意：排序后第一個(gè)區(qū)間一

4、定會(huì)選，因?yàn)樗淖⒁猓号判蚝蟮谝粋€(gè)區(qū)間一定會(huì)選，因?yàn)樗腷i最小，最小，它不影響后面區(qū)間的選取，而且如果不選此區(qū)間，最它不影響后面區(qū)間的選取，而且如果不選此區(qū)間，最終終求出的區(qū)間數(shù)目會(huì)變少。求出的區(qū)間數(shù)目會(huì)變少。區(qū)間選點(diǎn)問(wèn)題?數(shù)軸上有數(shù)軸上有n個(gè)閉區(qū)間個(gè)閉區(qū)間ai, bi。取盡量少的點(diǎn)，使得每個(gè)。取盡量少的點(diǎn)，使得每個(gè)區(qū)間內(nèi)都至少有一個(gè)點(diǎn)（不同區(qū)間內(nèi)含的點(diǎn)可以是同一個(gè)）。區(qū)間內(nèi)都至少有一個(gè)點(diǎn)（不同區(qū)間內(nèi)含的點(diǎn)可以是同一個(gè)）?！痉治觥咳绻麉^(qū)間i內(nèi)已經(jīng)有一個(gè)點(diǎn)被取到，我們稱(chēng)此區(qū)間已經(jīng)被滿(mǎn)足。受上一題的啟發(fā)，我們先討論區(qū)間包含的情況。由于小區(qū)間被滿(mǎn)足時(shí)大區(qū)間一定也被滿(mǎn)足。所以在區(qū)間包含的情況下，大區(qū)

5、間不需要考慮。因此，我們把所有區(qū)間按b從小到大排序（b相同時(shí)a從大到小排序），則如果出現(xiàn)區(qū)間包含的情況，小區(qū)間一定排在前面。第一個(gè)區(qū)間應(yīng)該選取哪一個(gè)點(diǎn)呢？正確的貪心策略是：取最后一個(gè)點(diǎn)。如下圖。解題思路?根據(jù)剛才的討論，所有需要考慮的區(qū)間的a也是遞增的，我們把它畫(huà)成上圖的形式。如果第一個(gè)區(qū)間不選最后一個(gè)點(diǎn)，而是去中間的，如灰色點(diǎn)，那么把它移動(dòng)到最后一個(gè)點(diǎn)后，被滿(mǎn)足的區(qū)間增加了，而且原先被滿(mǎn)足的區(qū)間現(xiàn)在一定被滿(mǎn)足。這樣才能保證選取的點(diǎn)最少。區(qū)間覆蓋問(wèn)題?數(shù)軸上有數(shù)軸上有n個(gè)閉區(qū)間個(gè)閉區(qū)間ai, bi，選擇盡量少的區(qū)間覆蓋，選擇盡量少的區(qū)間覆蓋一條指定線(xiàn)段一條指定線(xiàn)段 s, t?！痉治觥勘绢}的突破

6、口仍然是區(qū)間包含和排序掃描，不過(guò)要先進(jìn)行一次預(yù)處理。每個(gè)區(qū)間在s,t外的部分都應(yīng)該預(yù)先被切掉，因?yàn)樗鼈兊拇嬖谑呛翢o(wú)意義的。例如要覆蓋線(xiàn)段3,5，閉區(qū)間0,1的存在無(wú)意義。在預(yù)處理后，在相互包含的情況下，小區(qū)間顯然不應(yīng)該被考慮。解題思路?把各區(qū)間按照 a從小到大順序。如果區(qū)間 1的起點(diǎn)不是 s，則無(wú)解，即s,t無(wú)法被完全覆蓋（因?yàn)槠渌麉^(qū)間的起點(diǎn)更大，不可能覆蓋到 s點(diǎn)），否則選擇起點(diǎn)在 s的最長(zhǎng)區(qū)間。選擇此區(qū)間ai,bi后，新的起點(diǎn)應(yīng)該被設(shè)置為 bi,并且忽略所有區(qū)間在bi之前的部分，就像預(yù)處理一樣。雖然貪心策略比上面的題復(fù)雜，但是仍然只需要一次掃描。如下圖 5所示。s為當(dāng)前有效起點(diǎn)（此前部分已

7、被覆蓋），則應(yīng)該選擇區(qū)間2。s基礎(chǔ)的“窮竭搜索”概念：窮竭搜索是指將所有的可能性羅列出來(lái)，在其中尋找答案的方法。這里，我們主要介紹：深度優(yōu)先搜索寬度優(yōu)先搜索深度優(yōu)先搜索?深度優(yōu)先搜索（DFS，Depth-First Search）是搜索的手段之一。它從某個(gè)狀態(tài)開(kāi)始，不斷地轉(zhuǎn)移狀態(tài)直到無(wú)法轉(zhuǎn)移，然后回退到前一步的狀態(tài)，繼續(xù)轉(zhuǎn)移到其他狀態(tài)，如此不斷重復(fù)，直至找到最終的解。根據(jù)深度優(yōu)先搜索的特點(diǎn)，采用遞歸函數(shù)實(shí)現(xiàn)比較簡(jiǎn)單。例題?給定整數(shù)他們的和恰好為a1,a2,a3,.,an, k。判斷是否可以從中選出若干個(gè)數(shù)，使?限制條件：?1=n20?-108=ai=108?-108=k只需1次轉(zhuǎn)移就可到達(dá)的所

8、有狀態(tài)-只需2次轉(zhuǎn)移就可到達(dá)的狀態(tài)-.，這樣的順序進(jìn)行搜索。對(duì)于同一狀態(tài)，寬度優(yōu)先搜索只經(jīng)過(guò)一次，因此復(fù)雜度為O（狀態(tài)數(shù)*轉(zhuǎn)移的方式）。根據(jù)寬度優(yōu)先搜索的特點(diǎn)，采用隊(duì)列進(jìn)行實(shí)現(xiàn)。例題：?水池?cái)?shù)目南陽(yáng)理工學(xué)院校園里有一些小河和一些湖泊，現(xiàn)在，我們把它們通一看成水池，假設(shè)有一張我們學(xué)校的某處的地圖，這個(gè)地圖上僅標(biāo)識(shí)了此處是否是水池，現(xiàn)在，你的任務(wù)來(lái)了，請(qǐng)用計(jì)算機(jī)算出該地圖中共有幾個(gè)水池。輸入m行每行輸入n個(gè)數(shù)，表示此處有水還是沒(méi)水（1表示此處是水池， 0表示此處是地面）0m1000n100輸入：3 41 0 0 0 0 0 1 11 1 1 0輸出：2輸入：5 51 1 1 1 00 0 1 0

9、10 0 0 0 01 1 1 0 00 0 1 1 1輸出：3?解題過(guò)程?本題是簡(jiǎn)單的搜索問(wèn)題，采用深度優(yōu)先遍歷可以解決，根據(jù)題目要求，假設(shè)從任意一點(diǎn)值為1的出發(fā)，將這點(diǎn)的坐標(biāo)上下左右全部用0替換，1次DFS后與初始動(dòng)這個(gè)1連接的1全部被替換成0，因此，直到圖中不再存在1為至，總共進(jìn)行的DFS的次數(shù)就是最后的結(jié)果咯！那么，根據(jù)題目要求，有4個(gè)方向，時(shí)間復(fù)雜度為O(4*n*m)。數(shù)論那些事?數(shù)學(xué)，特別是數(shù)論與計(jì)算機(jī)科學(xué)有著密切的聯(lián)系，所以也常被選作題材。雖然數(shù)學(xué)問(wèn)題大多需要使用特定方法求解，但其中有幾個(gè)基礎(chǔ)算法扮演著重要的角色。數(shù)論基礎(chǔ)?輾轉(zhuǎn)相除法1、求最大公約數(shù)2、擴(kuò)展歐幾里得3、ax+by

10、=gcd(a,b)1、埃氏篩法2、區(qū)間篩法?有關(guān)素?cái)?shù)的基礎(chǔ)算法快速冪?輾轉(zhuǎn)相除法?擴(kuò)展歐幾里得雙六一個(gè)雙六上面有向前向后無(wú)限延續(xù)的格子，每個(gè)格子都寫(xiě)有整數(shù)。其中0號(hào)格子是起點(diǎn)，1號(hào)格子是終點(diǎn)。而骰子上只有a , b , -a , -b 四個(gè)整數(shù)，所以根據(jù) a 和 b 的值的不同，有可能無(wú)法到達(dá)終點(diǎn)。格子如下：-4 -3 -2 -1 0 1 2 3 4 擲出四個(gè)整數(shù)各多少次可以到達(dá)終點(diǎn)？輸出任意一組解。1= a , b b。1，顯然當(dāng) b=0，gcd（a，b）=a。此時(shí) x=1，y=0；2，ab!=0 時(shí)設(shè) ax1+by1=gcd(a,b);bx2+(a mod b)y2=gcd(b,a mod

11、 b);根據(jù)樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b);則:ax1+by1=bx2+(a mod b)y2;即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;根據(jù)恒等定理得：x1=y2; y1=x2-(a/b)*y2;這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.上面的思想是以遞歸定義的，因?yàn)?gcd 不斷的遞歸求解一定會(huì)有個(gè)時(shí)候b=0，所以遞歸可以結(jié)束。埃氏篩法?給定整數(shù)n，請(qǐng)問(wèn)n以?xún)?nèi)多少個(gè)素?cái)?shù)n=106輸入25輸出9解題思路?要枚舉n以?xún)?nèi)素?cái)?shù)，可以用埃氏篩法列出2以后的所有序列：2 3 4 5

12、 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25標(biāo)出序列中的第一個(gè)素?cái)?shù)，也就是2，序列變成：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 252將剩下序列中，劃摽2的倍數(shù)，序列變成：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 254 6 8 10 12 14 16 18 20 22 24 （劃出的數(shù)）如果現(xiàn)在這個(gè)序列中最大數(shù)小于最后一個(gè)標(biāo)出的素?cái)?shù)的平方，那么剩下的序列中所有的數(shù)都

13、是素?cái)?shù)，否則回到第二步。本例中，因?yàn)?5大于2的平方，我們返回第二步：剩下的序列中第一個(gè)素?cái)?shù)是3，將主序列中3的倍數(shù)劃出，主序列變成：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 254 6 8 9 10 12 14 15 16 18 20 21 22 24 （劃出的數(shù)）我們得到的素?cái)?shù)有：2，325仍然大于3的平方，所以我們還要返回第二步：現(xiàn)在序列中第一個(gè)素?cái)?shù)是5，同樣將序列中5的倍數(shù)劃出，主序列成了：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24