算法合集之序的應(yīng)用

算法合集之序的應(yīng)用第一頁(yè)，共二十六頁(yè)，編輯于2023年，星期三基本的序41231244325344122425313443大小序12345671246753DFS序1247536拓?fù)湫蚨植檎疫B通性問(wèn)題動(dòng)態(tài)規(guī)劃序是數(shù)據(jù)之間隱藏的一種基本關(guān)系：第二頁(yè)，共二十六頁(yè)，編輯于2023年，星期三序的應(yīng)用使得一個(gè)問(wèn)題得到直接解決（大多是交互式問(wèn)題）應(yīng)用序，挖掘題目的深層性質(zhì)，使得問(wèn)題得到轉(zhuǎn)化。下面著重通過(guò)兩個(gè)例子來(lái)探討如何應(yīng)用序來(lái)轉(zhuǎn)化問(wèn)題。第三頁(yè)，共二十六頁(yè)，編輯于2023年，星期三樹(shù)的構(gòu)造問(wèn)題描述：一棵含有n個(gè)節(jié)點(diǎn)的樹(shù)，所有的節(jié)點(diǎn)依次編號(hào)為1,2,3,…,n，每個(gè)節(jié)點(diǎn)i有一個(gè)權(quán)值s(i)，也分別是1,2,3,…,n，并且各不相同。對(duì)于編號(hào)為v的節(jié)點(diǎn)，定義t(v)為v的后代中所有權(quán)值小于s(v)的節(jié)點(diǎn)個(gè)數(shù)?，F(xiàn)在給出這棵樹(shù)及t(1),t(2),…,t(n)，請(qǐng)你求出這棵樹(shù)每個(gè)節(jié)點(diǎn)的權(quán)值。第四頁(yè)，共二十六頁(yè)，編輯于2023年，星期三樹(shù)的構(gòu)造已知T構(gòu)造S426578193

S497821356426578193

T313100000為了理解題目我們來(lái)看一個(gè)實(shí)例：第五頁(yè)，共二十六頁(yè)，編輯于2023年，星期三樹(shù)的構(gòu)造我們來(lái)考慮這個(gè)樹(shù)的DFS序列：4265781933310100001(3)2(1)4(0)5(0)7(0)3(3)6(1)8(0)9(0)DFS序列的重要性質(zhì)：所有的子孫都緊跟著該節(jié)點(diǎn)之后出現(xiàn)。第六頁(yè)，共二十六頁(yè)，編輯于2023年，星期三樹(shù)的構(gòu)造由于權(quán)值分別是1,2,3…,n。我們不妨認(rèn)為從左到右有N個(gè)格子，如果從左數(shù)第I個(gè)格子填入了節(jié)點(diǎn)J，則S(j)=i。425178639426578193313100000426578193497821356一組可行解左數(shù)第4個(gè)位置左數(shù)第7個(gè)位置第七頁(yè)，共二十六頁(yè)，編輯于2023年，星期三樹(shù)的構(gòu)造不能漏填，也不能沖突。每個(gè)格子的左邊，都恰好有t(i)個(gè)格子填入了自己的子孫。不能超出1…n的邊界范圍。如果我們按照DFS的順序，依次填寫(xiě)節(jié)點(diǎn)。對(duì)于每個(gè)節(jié)點(diǎn)j的左邊，則必須預(yù)留下至少t(j)個(gè)空格給權(quán)值比他小的子孫。所有的子孫都緊跟著該節(jié)點(diǎn)之后出現(xiàn)?？纯础疤睢钡臅r(shí)候的具體要求第八頁(yè)，共二十六頁(yè)，編輯于2023年，星期三樹(shù)的構(gòu)造依次按DFS序填寫(xiě)每個(gè)節(jié)點(diǎn)時(shí)，對(duì)于節(jié)點(diǎn)J，給他的子孫恰好預(yù)留t(j)個(gè)空位，即j填在第t(j)+1個(gè)空格，就是可行解4251786394265781933131000001(3)2(1)4(0)5(0)7(0)3(3)6(1)8(0)9(0)426578193497821356可以假設(shè)節(jié)點(diǎn)個(gè)數(shù)N較小的情況下滿足條件，并且解只會(huì)占用前N個(gè)空格。然后用數(shù)學(xué)歸納法對(duì)每一顆子樹(shù)進(jìn)行歸納證明。第九頁(yè)，共二十六頁(yè)，編輯于2023年，星期三樹(shù)的構(gòu)造已知一個(gè)一維線形結(jié)構(gòu)最開(kāi)始所有位置為空。根據(jù)DFS序列，每次插入一個(gè)元素j，到第t(j)+1個(gè)空位置求出最終狀態(tài)借助線段樹(shù)或樹(shù)狀數(shù)組等數(shù)據(jù)結(jié)構(gòu)可以將問(wèn)題在O(NlogN)時(shí)間復(fù)雜度內(nèi)解決，空間復(fù)雜度為O(N)看看轉(zhuǎn)化后的問(wèn)題：第十頁(yè)，共二十六頁(yè)，編輯于2023年，星期三小結(jié)通過(guò)對(duì)題目特點(diǎn)的分析，借助DFS序列的性質(zhì)，對(duì)原問(wèn)題進(jìn)行轉(zhuǎn)化。合理的使用數(shù)據(jù)結(jié)構(gòu)，最終完整解決問(wèn)題。第十一頁(yè)，共二十六頁(yè)，編輯于2023年，星期三問(wèn)題描述：N個(gè)士兵在進(jìn)行隊(duì)列訓(xùn)練，從左至右有M個(gè)位置。每次將軍可以下達(dá)一個(gè)命令，表示為Goto(L,S)1.若隊(duì)列L位置上為空，則士兵S站在L上。2.若隊(duì)列L位置上有士兵K，則士兵S站在L上，并執(zhí)行Goto(L+1，K)

將軍依次下達(dá)N個(gè)命令，每個(gè)士兵被下達(dá)命令一次且僅一次。要你求出最后隊(duì)列的狀態(tài)。（有可能在命令執(zhí)行過(guò)程中，士兵站的位置標(biāo)號(hào)超過(guò)M）士兵排隊(duì)就是把L位置及其右方的一段士兵向右推移一格，為S騰出位置，然后S站在L上。第十二頁(yè)，共二十六頁(yè)，編輯于2023年，星期三士兵排隊(duì)Goto(4,1)Goto(4,2)Goto(5,3)Goto(2,4)Goto(4,5)Goto(3,6)123456N=6M=5一個(gè)簡(jiǎn)單的例子第十三頁(yè)，共二十六頁(yè)，編輯于2023年，星期三士兵排隊(duì)直接模擬的最壞時(shí)間復(fù)雜度為O(N2)，效率十分低下。使用平衡二叉樹(shù)，可以得到一個(gè)O(Nlog(N+M))的算法。但平衡二叉樹(shù)時(shí)間復(fù)雜度常數(shù)系數(shù)比較大，而且較難實(shí)現(xiàn)。不妨拋開(kāi)純粹模擬的思路，另辟蹊徑。我們來(lái)進(jìn)行一下初步分析：第十四頁(yè)，共二十六頁(yè)，編輯于2023年，星期三士兵排隊(duì)先來(lái)看最基本的情況：Goto(2,1)Goto(2,2)12可見(jiàn)：如何高效處理插入帶來(lái)的連鎖移動(dòng)是本題的關(guān)鍵！能不能通過(guò)特殊的處理來(lái)避免連鎖移動(dòng)呢？第十五頁(yè)，共二十六頁(yè)，編輯于2023年，星期三NewGoto(2,2)NewGoto(2,1)士兵排隊(duì)注意到上面的例子中1因?yàn)?的插入而向右移動(dòng)了一格。我們要避免連鎖移動(dòng)，就是希望通過(guò)一個(gè)規(guī)則，使得士兵1能夠直接插入到3號(hào)位置。我們可以先插入士兵2而不是士兵1，然后再將士兵1插入到第2個(gè)空位置中。具體地說(shuō)，定義：newgoto(L,S)命令，將S士兵插入到第L個(gè)空位置中。12Goto(2,1)Goto(2,2)這就是上一題我們最后要實(shí)現(xiàn)的操作！第十六頁(yè)，共二十六頁(yè)，編輯于2023年，星期三事實(shí)上原Goto序列只要把(L,S)數(shù)對(duì)合理交換位置，就和NewGoto序列等價(jià)士兵排隊(duì)12NewGoto(2,2)NewGoto(2,1)Goto(2,1)Goto(2,2)第十七頁(yè)，共二十六頁(yè)，編輯于2023年，星期三士兵排隊(duì)復(fù)雜一點(diǎn)的情況：Goto(4,1)Goto(4,2)Goto(5,3)Goto(2,4)Goto(4,5)Goto(3,6)NewGoto(4,5)NewGoto(5,3)NewGoto(4,2)NewGoto(4,1)NewGoto(3,6)NewGoto(2,4)123456第十八頁(yè)，共二十六頁(yè)，編輯于2023年，星期三B如果我們可以將Goto序列的(L,S)數(shù)對(duì)，高效合理的改變順序，轉(zhuǎn)化為NewGoto序列，則模擬NewGoto命令就是上題最后轉(zhuǎn)化成的一維線性填數(shù)問(wèn)題。士兵排隊(duì)有兩條根本性的原則：如果A因B插入而被連鎖移動(dòng)。則和A,B有關(guān)的兩條NewGoto命令，B要在A之前。如果A,B沒(méi)有關(guān)聯(lián)，而A最終位置在B之前，則NewGoto序列中，B要在A之前。B......AGoto(LA,A)……Goto(LB,B)第LA個(gè)空位置......A第LA個(gè)空位置NewGoto(LB,B)……NewGoto(LA,A)第LA個(gè)空位置的具體位置被推移！...第十九頁(yè)，共二十六頁(yè)，編輯于2023年，星期三士兵排隊(duì)123456532164我們需要知道最終位置。我們需要知道誰(shuí)被誰(shuí)造成連鎖移動(dòng)。我們無(wú)法直接構(gòu)圖。一組等價(jià)的NewGoto序列如果構(gòu)造一個(gè)圖，與A相關(guān)的NewGoto命令要在與B相關(guān)的之前，則A,B之間連一條邊A->B，那么我們就是要獲得這個(gè)圖拓?fù)湫?。第二十?yè)，共二十六頁(yè)，編輯于2023年，星期三3,4考慮利用兩條基本性質(zhì)，直接構(gòu)造拓?fù)湫颉Ｓ貌⒉榧鎯?chǔ)每個(gè)不相干的部分及單獨(dú)構(gòu)造(假設(shè)每個(gè)塊互相不影響)的NewGoto序列。當(dāng)兩個(gè)塊因?yàn)椴迦攵喜r(shí)，順便將兩個(gè)塊的NewGoto序列合并。最后將所有未合并的部分的序列，根據(jù)位置在后的塊序列上靠前的原則，合并完整的NewGoto序列。2634156士兵排隊(duì)3214521,52,6,3,4并查集并不需要，也無(wú)法存儲(chǔ)每個(gè)部分內(nèi)元素之間的相對(duì)位置！NewGoto(L1,1)NewGoto(L5,5)第二十一頁(yè)，共二十六頁(yè)，編輯于2023年，星期三士兵排隊(duì)當(dāng)士兵A直接插入到一個(gè)已經(jīng)屬于某一個(gè)塊B的位置中時(shí)，就將與A相關(guān)的NewGoto命令插入B塊的NewGoto命令序列首。當(dāng)士兵A的插入引起了一個(gè)或者多個(gè)塊相連時(shí)，則根據(jù)位置在后的塊序列上靠前的原則來(lái)對(duì)他們進(jìn)行合并。用一個(gè)鏈表來(lái)存儲(chǔ)單個(gè)部分的NewGoto序列，因?yàn)樗簧婕安迦氲叫蛄惺?，和首尾相接合并兩個(gè)操作我們來(lái)具體討論如何合并：.........b1biABa1…BakA,Ba1…BakA63214521,53,42,6,3,4第二十二頁(yè)，共二十六頁(yè)，編輯于2023年，星期三士兵排隊(duì)Goto(4,1)Goto(4,2)Goto(5,3)Goto(2,4)Goto(4,5)Goto(3,6)123456具體實(shí)現(xiàn)的例子：12,13,2,145,3,2,15,3,2,1,6,4第二十三頁(yè)，共二十六頁(yè)，編輯于2023年，星期三士兵排隊(duì)根據(jù)Goto序列構(gòu)造NewGoto序列。轉(zhuǎn)化成前一題最終轉(zhuǎn)化成的一維線性填數(shù)問(wèn)題。使用線段樹(shù)等工具在O(