算法合集之《淺析信息學(xué)中的“分”與“合”》.doc

淺析信息學(xué)中的“分”與“合”福建省福州第三中學(xué) 楊沐目錄【摘要】3【關(guān)鍵字】3【正文】3一、引言3二、例題分析3例一牛奶模版4例二樹的重建6例三最優(yōu)序列9三、總結(jié)12【感謝】12【參考文獻(xiàn)】13【附錄】13【摘要】本文就“分”與“合”的思想在信息學(xué)中的應(yīng)用進(jìn)行討論與研究?！胺帧迸c“合”思想的精髓在于通過在“分”與“合”之間的轉(zhuǎn)化中找到問題的本質(zhì)從而解決問題，該思想的應(yīng)用并非僅限于傳統(tǒng)意義上的“分治法”。本文通過分析例題牛奶模版、樹的重建與最優(yōu)序列來介紹“分”與“合”思想在解題中的具體應(yīng)用。【關(guān)鍵字】“分”與“合”、轉(zhuǎn)化、辨證關(guān)系【正文】一、引言“話說天下大勢，合久必分，分久必合”，這富有辨證意味的第一句話可以說是三國演義的精髓。浩浩中華幾千年的歷史，充分說明了“合久必分，分久必合”這一觀點(diǎn)的正確性?！昂暇帽胤?，分久必合”是從低級到高級，螺旋式發(fā)展的過程， 縱觀天下事，無不是在“分”與“合”之間互相轉(zhuǎn)化下發(fā)展的?！胺帧迸c“合”的規(guī)律不僅在社會發(fā)展上得到應(yīng)驗(yàn)，在信息學(xué)中的許多題目的解題過程中也有著充分的體現(xiàn)?！胺帧钡乃枷胧菍⒁粋€(gè)難以直接解決的大問題，分成一些規(guī)模較小或限制某些條件的子問題來思考，以求將問題解決。“合”的思想與“分”相對，是將“分”出的一些零碎的小問題合并成一個(gè)大問題，從而理清關(guān)系，得出解法。在當(dāng)今信息學(xué)競賽中，我們常常會碰到各種問題，由于規(guī)模過大而難以思考，無從入手，又或情況過于紛繁復(fù)雜導(dǎo)致思考難度驟增，這時(shí)不妨嘗試使用“分”與“合”的思考方式來幫助分析問題。二、例題分析下面，作者通過介紹三個(gè)例題牛奶模版、樹的重建和最優(yōu)序列，結(jié)合各題自身特性利用“分”與“合”的思想解題，希望能起到拋磚引玉的作用。例一牛奶模版選自usaco contest DEC06 GOLD Milk Patterns問題簡述由于奶牛們的產(chǎn)奶品質(zhì)波動(dòng)不定， FJ決定找出奶牛產(chǎn)奶品質(zhì)波動(dòng)的規(guī)律。FJ用一個(gè)由到的整數(shù)組成的長度為的序列記錄了各天奶牛們的產(chǎn)奶品質(zhì)，F(xiàn)J希望從中找出最長的一段模版串，使得該模版串在序列中出現(xiàn)至少次，請輸出最長模版串的長度。（例如，12323231中2323出現(xiàn)了2次，最長的模版長度為4。）問題分析本題是一道與串匹配有關(guān)的問題，我們很自然的想到使用解決字符串問題的利器后綴樹，事實(shí)上，使用后綴樹確實(shí)可以在線性時(shí)間內(nèi)解決本題，但后綴樹的高編程復(fù)雜度使我們很難在限定時(shí)間內(nèi)完成解題任務(wù)。那么，是否存在簡單而又行之有效的算法呢？普通枚舉法解決此題最簡單的方法莫過于枚舉法了，我們可以枚舉出原串的所有子串，互相比對并統(tǒng)計(jì)出它們各自出現(xiàn)的次數(shù)，從中選出出現(xiàn)次數(shù)不少于次的最長子串。由于原串的子串?dāng)?shù)達(dá)到的級別，而字符串比較的時(shí)間復(fù)雜度為因此該枚舉法的時(shí)間復(fù)雜度高達(dá)，完全無法在限定時(shí)間內(nèi)出解。上述枚舉法之所以低效，很重要的一個(gè)原因是重復(fù)比較過多。這時(shí)我們又想到了高效的串匹配算法KMP算法。在枚舉原串的子串后，我們可以使用KMP算法在的時(shí)間內(nèi)算出該串在原串中的出現(xiàn)次數(shù)，因而將總算法復(fù)雜度降為。但是，當(dāng)我們試圖使用串匹配算法繼續(xù)優(yōu)化算法時(shí)間復(fù)雜度的時(shí)候遇到了重重困難，在多次嘗試無果后，不得不回到問題的起點(diǎn)，換一角度思考問題。枚舉法改進(jìn)觀察普通的枚舉法，我們發(fā)現(xiàn)其實(shí)枚舉所有子串的做法存在許多冗余，因?yàn)閷τ谌我鈨蓚€(gè)子串，相等的先決條件是它們的長度必須相同，這提示我們可以枚舉子串的長度。而題目中存在著一個(gè)很明顯的單調(diào)性，即在原串中若存在一個(gè)長度為的子串出現(xiàn)了至少次，則對于任意長度，必然能找到一個(gè)長度為的子串在原串中出現(xiàn)至少次（只需取為的子串即可）。根據(jù)此單調(diào)性，我們可以二分枚舉答案，之后只判斷相同長度的子串是否相等，效率大大提升，時(shí)間復(fù)雜度優(yōu)化為。轉(zhuǎn)換枚舉方式后，低效的子串判等方法成為了算法新的瓶頸。但我們發(fā)現(xiàn)，確定了子串的長度后，符合要求的子串只有個(gè)，可以使用hash表來存儲各串，并用以判等。根據(jù)題目特點(diǎn)，我們設(shè)計(jì)如下hash函數(shù)：對于子串可以取任意素?cái)?shù)，為大素?cái)?shù)，表示在hash表中的位置，使用代替的內(nèi)容（使得沖突時(shí)的比較時(shí)間復(fù)雜度降為）。若二子串的與值分別相同，則認(rèn)為這兩個(gè)子串相同（由于設(shè)置了兩個(gè)函數(shù)，誤判的概率大約僅為，可以忽略）。由于與只有個(gè)元素不同，因此，同理。這樣就能在的時(shí)間內(nèi)算出所有長度為的子串所對應(yīng)的與值，因此在理想情況下本方法的時(shí)間復(fù)雜度已經(jīng)優(yōu)化為了，并且正確率極高，足以通過所有數(shù)據(jù)。小結(jié)“分”的思想在很多場合都有應(yīng)用，在本題的求解過程中，先后嘗試了多種方法，最終利用“分”的思想二分答案，巧妙地將限制下的最優(yōu)化問題轉(zhuǎn)化成限制下的存在性問題，從而得出了一個(gè)十分簡便而有效的可行算法。例二樹的重建選自ZOJ2701的Restore the tree問題簡述給出一棵樹的葉子節(jié)點(diǎn)數(shù)，以及任意兩個(gè)葉子間的樹中距離（不超過），樹中任意邊邊權(quán)均為，要求還原原樹，對于未知節(jié)點(diǎn)可任意標(biāo)號，若無解輸出。問題分析本題與樹有關(guān)，題目給出的條件僅為各葉子間的距離關(guān)系，對于樹中其他節(jié)點(diǎn)沒有任何描述，這使得直接構(gòu)樹困難重重。既然直接考慮原問題過于復(fù)雜，就從簡單情況入手?？紤]若只有個(gè)葉節(jié)點(diǎn)，則答案顯而易見，即一條鏈的情況。12若有個(gè)葉節(jié)點(diǎn)，情況略顯復(fù)雜，設(shè)表示葉節(jié)點(diǎn)與葉節(jié)點(diǎn)的距離。為了簡單起見，不妨指定樹的根為。當(dāng)時(shí)根據(jù)樹的性質(zhì)，此情況必定無解。同理，當(dāng)或時(shí)也是無解的。當(dāng)時(shí)根據(jù)樹的性質(zhì)，節(jié)點(diǎn)必然存在于節(jié)點(diǎn)至節(jié)點(diǎn)的路徑之中，則節(jié)點(diǎn)必然不是葉節(jié)點(diǎn)，這與題意矛盾，因此依然無解。同理，當(dāng)或時(shí)也無解。當(dāng)時(shí)當(dāng)時(shí)與類似，此時(shí)節(jié)點(diǎn)處于節(jié)點(diǎn)至節(jié)點(diǎn)的路徑上，無解。若不滿足，則樹的形態(tài)可描繪如下。123分裂點(diǎn)因?yàn)?，所以?dāng)時(shí)不可能是非整數(shù)，因此無解當(dāng)時(shí)得出了葉節(jié)點(diǎn)的關(guān)系，即節(jié)點(diǎn)位于節(jié)點(diǎn)至節(jié)點(diǎn)的路徑上第個(gè)點(diǎn)（分裂點(diǎn)）分出的另一條長度為的子鏈的尾部。進(jìn)一步分析上述簡單情況的分析討論得出：任意兩個(gè)葉節(jié)點(diǎn)必然被一條由非葉節(jié)點(diǎn)組成的鏈所連接，而剩下的所有葉節(jié)點(diǎn)與該兩點(diǎn)之間的位置關(guān)系，都可由上述的討論確定！在這一發(fā)現(xiàn)的啟發(fā)下，我們想到了利用“分”與“合”的思想解決該題。設(shè)包含個(gè)葉節(jié)點(diǎn)的原問題為，若能將一個(gè)新葉節(jié)點(diǎn)并入一棵已知的樹上，則就可以轉(zhuǎn)化為，下面介紹具體做法：假設(shè)當(dāng)前樹已包含了個(gè)葉節(jié)點(diǎn)（不妨設(shè)其標(biāo)號為），指定樹的根為葉節(jié)點(diǎn)，當(dāng)前需要新加入一個(gè)葉節(jié)點(diǎn)。枚舉已在樹中的葉節(jié)點(diǎn)，由上述對個(gè)葉節(jié)點(diǎn)的情況討論可得葉節(jié)點(diǎn)關(guān)于鏈的分裂點(diǎn)及其深度。23k1分裂點(diǎn)分裂點(diǎn)sp2sp3 觀察樹中各分裂點(diǎn)的位置關(guān)系。我們發(fā)現(xiàn)所有分裂點(diǎn)都處于同一條鏈上，事實(shí)上這是顯然的它們必然在的路徑上。而對于每次并入新葉節(jié)點(diǎn)，在樹中出現(xiàn)的新鏈僅為深度最深的分裂點(diǎn)葉節(jié)點(diǎn)這一段。因此，我們只需從所有分裂點(diǎn)中深度最深的分裂點(diǎn)上分裂出一條長度為新鏈，鏈尾即為葉節(jié)點(diǎn)，這樣一來就將葉節(jié)點(diǎn)并入了樹。同時(shí)，在合并新點(diǎn)的過程中，我們發(fā)現(xiàn)無解情況實(shí)在太多了！這使得思維復(fù)雜度與編程復(fù)雜度大大提高。但我們發(fā)現(xiàn)，若原題存在一組可行解，則上述做法必能將新點(diǎn)并入。因此，我們大可拋棄繁雜的討論，只在算法結(jié)束時(shí)判斷解的可行性。算法框架至此可以確定算法如下：建立基樹，初始時(shí)只包含葉節(jié)點(diǎn)與若干用于連接葉節(jié)點(diǎn)與的非葉節(jié)點(diǎn)。取一未被包含的葉節(jié)點(diǎn)按上述合并方法將其并入。若未包含所有葉節(jié)點(diǎn)，則跳轉(zhuǎn)；否則則得到了一組未檢查解，轉(zhuǎn)。檢查解中各葉節(jié)點(diǎn)是否滿足題意。即若葉節(jié)點(diǎn)個(gè)數(shù)與原題給出條件不等，或存在某對葉節(jié)點(diǎn)距離與原題給定距離不同，則無解；否則得到一組可行解。該算法時(shí)空復(fù)雜度均為，都達(dá)到了理論下界，是個(gè)十分優(yōu)秀的算法。小結(jié)在解決本題的過程中，從簡單情況開始討論，進(jìn)而發(fā)現(xiàn)了題目的重要性質(zhì)，使用“分”與“合”的方法，將規(guī)模為的問題轉(zhuǎn)化為規(guī)模為的問題，從而得出解法。例三最優(yōu)序列問題簡述給出一個(gè)長度為的正整數(shù)序列，求一個(gè)子序列，使得原序列中任意長度為的子串中被選出的元素不超過個(gè)，并且選出的元素之和最大。問題分析初看此題，我們首先考慮動(dòng)態(tài)規(guī)劃，它是解決這類最優(yōu)化問題的一把利刃，然而，由于題目條件過于苛刻，使得普通動(dòng)態(tài)規(guī)劃完全無法勝任，而狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃時(shí)間復(fù)雜度甚至高達(dá)，根本無法在時(shí)限內(nèi)出解。既然動(dòng)態(tài)規(guī)劃無法解決此題，我們又很自然的想到了對于一維區(qū)間操作十分適用的線段樹，可是，經(jīng)過多次嘗試最終發(fā)現(xiàn)這種思路也是行不通的。初步分析在嘗試不同方法解決此題的過程中，我們發(fā)現(xiàn)本題的主要困難在于和的范圍過大，使得情況過于復(fù)雜，難以下手。這時(shí)，我們就想到了使用“分”的方法來限制問題的規(guī)模，并試圖了解問題的本質(zhì)?！胺帧狈睘楹啲F(xiàn)在面對的主要問題是和的范圍過大，先拋開這個(gè)困擾，讓我們來看看這題的一個(gè)子問題：給出一個(gè)長度為的序列，求一個(gè)子序列，使得原序列中任意長度為的子串中被選出的元素不超過1個(gè)，并且選出的元素之和最大。對于這個(gè)子問題，由于沒有了的阻礙，思路豁然開朗，我們可以很輕松的列出動(dòng)態(tài)轉(zhuǎn)移方程來解決這個(gè)問題設(shè)表示區(qū)間所能取到的最大和，則狀態(tài)轉(zhuǎn)移方程為： 那么，這個(gè)子問題與原問題究竟有什么關(guān)聯(lián)呢？進(jìn)一步分析隨著上述子問題的解決，一個(gè)很誘人的想法隨之產(chǎn)生：若原問題的解等價(jià)于個(gè)子問題的解的并，我們就可以通過解決子問題從而將原問題解決。在這一思路的啟發(fā)下，我們嘗試證明如下命題。命題：原問題的解集等價(jià)于由組互不相交的子問題的解組成的解集。定理一 原問題的任意一組解都可以由組不相交的子問題的解組成。證明：對于原問題的任意一解，設(shè)表示該解在區(qū)間內(nèi)取出的元素個(gè)數(shù)，則根據(jù)題意滿足不等式： 以下，我們給出一種構(gòu)造法使之能產(chǎn)生一組與該解等價(jià)的個(gè)子問題的解。設(shè)個(gè)子問題的解分別為，令均為合法的子問題的解又因?yàn)?，因此我們成功的?gòu)造出了子問題的解。定理二 任意組不相交的子問題的解的并均為原問題的解。證明： 設(shè)個(gè)子問題的解分別為，對于任意長度為的區(qū)間，至多只有一個(gè)元素在其內(nèi)部設(shè)，則對于任意長度為的區(qū)間，在其內(nèi)部選出的元素個(gè)數(shù)不超過個(gè)任意組互不相交的子問題的解的并都是原問題的合法解定理一與定理二分別證明了該命題的充要性，因此該命題成立。整體分析隨著命題的證明，我們已經(jīng)成功地將“一個(gè)最優(yōu)解”轉(zhuǎn)化為“K個(gè)子問題的最優(yōu)并”，接下來的任務(wù)就是找到一種方法，使之能產(chǎn)生出最優(yōu)的不重疊的子問題解的并。首先嘗試之前所述的樸素動(dòng)態(tài)規(guī)劃，可惜事與愿違，由于子問題間有重疊，若直接套用次動(dòng)態(tài)規(guī)劃來求解，有可能導(dǎo)致某個(gè)元素被取多次。動(dòng)態(tài)規(guī)劃無法解決，那么貪心是否能解決這個(gè)問題呢？不能。我們注意到取K次局部最優(yōu)解，它們的并，不一定是全局的最優(yōu)解。既然從局部分析已經(jīng)走入了一個(gè)死胡同，我們不妨使用“合”的思想從整體入手，提升自己的思想高度?？紤]動(dòng)態(tài)規(guī)劃之所以不能得到正確解，其原因在于題目中每個(gè)元素只能被取一次的限制，而對于這種限制各點(diǎn)被選取次數(shù)的題目，我們通常使用網(wǎng)絡(luò)流來解決，那么這道題是否也能通過轉(zhuǎn)化圖論模型來使用網(wǎng)絡(luò)流解決呢？答案是肯定的。構(gòu)造帶權(quán)網(wǎng)絡(luò)序列中的每個(gè)元素用頂點(diǎn)與表示，連邊，容量為1，費(fèi)用為該元素的數(shù)值，圖中還包含源與匯。所有點(diǎn)向點(diǎn)連邊，容量為，費(fèi)用為0源點(diǎn)向所有點(diǎn)各連一條邊，容量為，費(fèi)用為0所有點(diǎn)向匯點(diǎn)連各連一條邊，容量為，費(fèi)用為0所有點(diǎn)向點(diǎn)連邊，容量為，費(fèi)用為0321n123nTS構(gòu)圖完畢之后，網(wǎng)絡(luò)流量每增加一表示多完成了一個(gè)子問題，因此，我們只需要在網(wǎng)絡(luò)中尋找次最大費(fèi)用增廣路即可得到答案。由于這張圖的邊數(shù)與頂點(diǎn)數(shù)同階，若使用SPFA算法求增廣軌，則期望時(shí)間復(fù)雜度僅為，是個(gè)十分優(yōu)秀的算法。小結(jié)本題在難以入手的情況下通過“分”的思想簡化題目，從而理清思路，發(fā)現(xiàn)題目本質(zhì)并轉(zhuǎn)化目標(biāo)，而后通過“合”的思想采用網(wǎng)絡(luò)流將所有子問題綜合考慮，從而解決了問題。本題充分說明了“分”與“合”的思想在幫助解題時(shí)的巨大作用。三、總結(jié)本文簡要介紹了“分”與“合”的幾個(gè)應(yīng)用在題目滿足一些單調(diào)性時(shí)采取二分的做法以優(yōu)化算法，在發(fā)現(xiàn)題目可化歸的性質(zhì)之后從解決小范圍問題開始逐步擴(kuò)大求得正解以及在題目無從下手的情況下利用該思想化簡題目并找出算法。前兩個(gè)例題皆使用了基于“分”與“合”思想的算法。對于例題一，其實(shí)存在著許多其他精彩的解法，但與其相比，利用“分”的思想入手的思維復(fù)雜度極低，易于上手，且總結(jié)出的算法編程復(fù)雜度亦極低，在爭分奪秒的競賽賽場上可以說是不二的選擇。而在例題二中，化歸的方法則成了解題的唯一出路。在前兩個(gè)例題中，我們發(fā)現(xiàn)“分”與“合”雖然對立，卻沒有明顯的分界。一道問題若使用“分”的方法，則必然有“合”的操作，正所謂“分中有合，合中有分”，這兩者相互對立，各有優(yōu)勢，卻又相互補(bǔ)充，“分”的思想幫助我們迅速地切入問題核心，但在若過分細(xì)化則會使問題太過凌亂，失去求解的方向；而“合”的思想則以線串珠，使各種紛雜無序的問題具有了整體性，這正體現(xiàn)了兩者之間的辨證關(guān)系。事實(shí)上，本文所介紹到的應(yīng)用僅僅是“分”與“合”思想的皮毛，目的只是希望能起到拋磚引玉的作用?！胺帧迸c“合”的思想有著更十分廣泛的應(yīng)用。分治、補(bǔ)集轉(zhuǎn)化等方法就是“分”與“合”思想的經(jīng)典應(yīng)用，并已經(jīng)有了深入地研究，而各類高級數(shù)據(jù)結(jié)構(gòu)也大量的采用了“分”的方式來提升自身各種操作的效率，其思想的無窮魅力可見一斑?！胺帧迸c“合”不僅僅在算法實(shí)現(xiàn)上有著重要的效用，更在思維過程中起著舉足輕重的作用，例題三恰好體現(xiàn)了這一點(diǎn)。運(yùn)用“分”與“合”的思想，對于不同的題目需要不同的分析，其精髓就在于“轉(zhuǎn)化”。無論是“分”還是“合”都是朝著將問題轉(zhuǎn)化為更加便于思考的方向前進(jìn)，而在這路途中，又需要我們善于歸納總結(jié)。只有將已有的知識與“分合”思想有機(jī)地結(jié)合起來，同時(shí)勇于創(chuàng)新，不斷積累經(jīng)驗(yàn)，我們才能從千變?nèi)f化的題目找尋出本質(zhì)，從而更快更有效地解決實(shí)際問題?！靖兄x】感謝魏麗真老師在我寫這篇論文時(shí)對我的指導(dǎo)和幫助。感謝王知昆前輩仔細(xì)閱讀本文并提出寶貴的修改意見。感謝袁昕顥同學(xué)給我提供例題三。感謝王航同學(xué)在我寫論文時(shí)的無私幫助?！緟⒖嘉墨I(xiàn)】A算法藝術(shù)與信息學(xué)競賽（劉汝佳黃亮著）B 最短路算法及其應(yīng)用余遠(yuǎn)銘同學(xué)2006年冬令營論文【附錄】例一原題：Problem 3: Milk Patterns Coaches, 2004Farmer John has noticed that the quality of milk given by his cowsvaries from day to day. On further investigation, he discoveredthat although he cant predict the quality of milk from one day tothe next, there are some regular patterns in the daily milk quality.To perform a rigorous study, he has invented a complex classificationscheme by which each milk sample is recorded as an integer between0 and 1,000,000 inclusive, and has recorded data from a single cowover N (1 = N = 20,000) days. He wishes to find the longestpattern of samples which repeats identically at least K (2 = K = N) times.This may include overlapping patterns - 1 2 3 2 3 2 3 1 repeats 23 2 3 twice, for example.Help Farmer John by finding the longest repeating subsequence inthe sequence of samples. It is guaranteed that at least one subsequenceis repeated at least K times.PROBLEM NAME: patternsINPUT FORMAT:* Line 1: Two space-separated integers: N and K* Lines 2.N+1: N integers, one per line, the quality of the milk on day i appears on the ith line.SAMPLE INPUT (file patterns.in):8 212323231OUTPUT FORMAT:* Line 1: One integer, the length of the longest pattern which occurs at least K timesSAMPLE OUTPUT (file patterns.out):4例二原題：Restore the TreeTime limit: 10 Seconds Memory limit: 32768K Special JudgeTotal Submit: 206 Accepted Submit: 26 An undirected connected graph with no cycles is called a tree. A vertex with degree equal to one in a tree is called a leaf. Consider a tree. For each pair of leaves one can determine the distance between these leaves - the number of edges one needs to walk to get from one leaf to another. Given these distances for all pairs of leaves, you need to restore the tree. InputThere are mutilple cases in the input file. The first line of each case contains l - the number of leaves in the tree (2 = l = 200 ). Next l lines contain l integer numbers each - distances between leaves. It is guaranteed that no di