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

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

S497821356426578193

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

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