1、序的應(yīng)用,長沙市雅禮中學(xué) 龍凡,基本的序,4 12 31 24 43 25 34,4 12 24 25 31 34 43,大小序,1,2,3,4,5,6,7,1 2 4 6 7 5 3,DFS序,1 2 4 7 5 3 6,拓?fù)湫?二分查找,連通性問題,動態(tài)規(guī)劃,序是數(shù)據(jù)之間隱藏的一種基本關(guān)系：,序的應(yīng)用,使得一個問題得到直接解決（大多是交互式問題） 應(yīng)用序，挖掘題目的深層性質(zhì)，使得問題得到轉(zhuǎn)化。,下面著重通過兩個例子來探討如何應(yīng)用序來轉(zhuǎn)化問題。,樹的構(gòu)造,問題描述：一棵含有n個節(jié)點(diǎn)的樹，所有的節(jié)點(diǎn)依次編號為1, 2, 3, , n，每個節(jié)點(diǎn)i有一個權(quán)值s(i)，也分別是1,2,3,n，并且各

2、不相同。對于編號為v的節(jié)點(diǎn)，定義t(v)為v的后代中所有權(quán)值小于s(v)的節(jié)點(diǎn)個數(shù)。 現(xiàn)在給出這棵樹及t(1),t(2),t(n)，請你求出這棵樹每個節(jié)點(diǎn)的權(quán)值。,樹的構(gòu)造,已知T,構(gòu)造S,為了理解題目我們來看一個實(shí)例：,樹的構(gòu)造,我們來考慮這個樹的DFS序列：,4,2,6,5,7,8,1,9,3,3,3,1,0,1,0,0,0,0,1(3)2(1)4(0)5(0)7(0)3(3)6(1)8(0)9(0),DFS序列的重要性質(zhì)：,所有的子孫都緊跟著該節(jié)點(diǎn)之后出現(xiàn)。,樹的構(gòu)造,由于權(quán)值分別是1,2,3,n。我們不妨認(rèn)為從左到右有N個格子，如果從左數(shù)第I個格子填入了節(jié)點(diǎn)J，則S(j)=i。,一組可

3、行解,左數(shù)第4個位置,左數(shù)第7個位置,樹的構(gòu)造,不能漏填，也不能沖突。 每個格子的左邊，都恰好有t(i)個格子填入了自己的子孫。 不能超出1n的邊界范圍。,如果我們按照DFS的順序，依次填寫節(jié)點(diǎn)。對于每個節(jié)點(diǎn)j的左邊，則必須預(yù)留下至少t(j)個空格給權(quán)值比他小的子孫。,所有的子孫都緊跟著該節(jié)點(diǎn)之后出現(xiàn)。,看看“填”的時候的具體要求,樹的構(gòu)造,依次按DFS序填寫每個節(jié)點(diǎn)時，對于節(jié)點(diǎn)J，給他的子孫恰好預(yù)留t(j)個空位，即j填在第t(j)+1個空格，就是可行解,4,2,5,1,7,8,6,3,9,4,2,6,5,7,8,1,9,3,3,1,3,1,0,0,0,0,0,1(3)2(1)4(0)5(0

4、)7(0)3(3)6(1)8(0)9(0),可以假設(shè)節(jié)點(diǎn)個數(shù)N較小的情況下滿足條件，并且解只會占用前N個空格。然后用數(shù)學(xué)歸納法對每一顆子樹進(jìn)行歸納證明。,樹的構(gòu)造,已知一個一維線形結(jié)構(gòu) 最開始所有位置為空。根據(jù)DFS序列，每次插入一個元素j，到第t(j)+1個空位置 求出最終狀態(tài) 借助線段樹或樹狀數(shù)組等數(shù)據(jù)結(jié)構(gòu)可以將問題在O(N log N)時間復(fù)雜度內(nèi)解決，空間復(fù)雜度為O(N),看看轉(zhuǎn)化后的問題：,小結(jié),通過對題目特點(diǎn)的分析，借助DFS序列的性質(zhì)，對原問題進(jìn)行轉(zhuǎn)化。 合理的使用數(shù)據(jù)結(jié)構(gòu)，最終完整解決問題。,問題描述：N個士兵在進(jìn)行隊(duì)列訓(xùn)練，從左至右有M個位置。每次將軍可以下達(dá)一個命令，表示為

5、Goto(L,S) 1.若隊(duì)列L位置上為空，則士兵S站在L上。 2.若隊(duì)列L位置上有士兵K，則士兵S站在L上，并執(zhí)行Goto(L+1，K) 將軍依次下達(dá)N個命令，每個士兵被下達(dá)命令一次且僅一次。要你求出最后隊(duì)列的狀態(tài)。（有可能在命令執(zhí)行過程中，士兵站的位置標(biāo)號超過M）,士兵排隊(duì),就是把L位置及其右方的一段士兵向右推移一格，為S騰出位置，然后S站在L上。,士兵排隊(duì),Goto(4,1) Goto(4,2) Goto(5,3) Goto(2,4) Goto(4,5) Goto(3,6),1,2,3,4,5,6,N=6 M=5,一個簡單的例子,士兵排隊(duì),直接模擬的最壞時間復(fù)雜度為O(N2)，效率十分低

6、下。 使用平衡二叉樹，可以得到一個O(N log (N+M)的算法。但平衡二叉樹時間復(fù)雜度常數(shù)系數(shù)比較大，而且較難實(shí)現(xiàn)。 不妨拋開純粹模擬的思路，另辟蹊徑。,我們來進(jìn)行一下初步分析：,士兵排隊(duì),先來看最基本的情況：,Goto(2,1) Goto(2,2),1,2,可見：如何高效處理插入帶來的連鎖移動是本題的關(guān)鍵！,能不能通過特殊的處理來避免連鎖移動呢？,NewGoto(2,2) NewGoto(2,1),士兵排隊(duì),注意到上面的例子中1因?yàn)?的插入而向右移動了一格。 我們要避免連鎖移動，就是希望通過一個規(guī)則，使得士兵1能夠直接插入到3號位置。我們可以先插入士兵2而不是士兵1，然后再將士兵1插入到

7、第2個空位置中。 具體地說，定義：newgoto(L,S)命令，將S士兵插入到第L個空位置中。,Goto(2,1) Goto(2,2),這就是上一題我們最后要實(shí)現(xiàn)的操作！,事實(shí)上原Goto序列只要把(L,S)數(shù)對合理交換位置，就和NewGoto序列等價,士兵排隊(duì),1,2,NewGoto(2,2) NewGoto(2,1),Goto(2,1) Goto(2,2),士兵排隊(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) NewGo

8、to(4,1) NewGoto(3,6) NewGoto(2,4),1,2,3,4,5,6,B,如果我們可以將Goto序列的(L,S)數(shù)對，高效合理的改變順序，轉(zhuǎn)化為NewGoto序列，則模擬NewGoto命令就是上題最后轉(zhuǎn)化成的一維線性填數(shù)問題。,士兵排隊(duì),有兩條根本性的原則：,如果A因B插入而被連鎖移動。則和A,B有關(guān)的兩條NewGoto命令，B要在A之前。 如果A,B沒有關(guān)聯(lián)，而A最終位置在B之前，則NewGoto序列中，B要在A之前。,B,.,.,A,Goto(LA,A) Goto(LB,B),第LA個空位置,.,.,A,第LA個空位置,NewGoto(LB,B) NewGoto(LA

9、,A),第LA個空位置的具體位置被推移！,.,士兵排隊(duì),1,2,3,4,5,6,5 3 2 1 6 4,我們需要知道最終位置。 我們需要知道誰被誰造成連鎖移動。 我們無法直接構(gòu)圖。,一組等價的NewGoto序列,如果構(gòu)造一個圖，與A相關(guān)的NewGoto命令要在與B相關(guān)的之前，則A,B之間連一條邊A-B，那么我們就是要獲得這個圖拓?fù)湫颉?3,4,考慮利用兩條基本性質(zhì)，直接構(gòu)造拓?fù)湫颉?用并查集存儲每個不相干的部分及單獨(dú)構(gòu)造(假設(shè)每個塊互相不影響)的NewGoto序列。 當(dāng)兩個塊因?yàn)椴迦攵喜r，順便將兩個塊的NewGoto序列合并。 最后將所有未合并的部分的序列，根據(jù)位置在后的塊序列上靠前的原

10、則，合并完整的NewGoto序列。,2 6 3 4 1 5,6,士兵排隊(duì),3,2,1,4,5,2,1,5,2,6,3,4,并查集并不需要，也無法存儲每個部分內(nèi)元素之間的相對位置！,NewGoto(L1,1) NewGoto(L5,5),士兵排隊(duì),當(dāng)士兵A直接插入到一個已經(jīng)屬于某一個塊B的位置中時，就將與A相關(guān)的NewGoto命令插入B塊的NewGoto命令序列首。 當(dāng)士兵A的插入引起了一個或者多個塊相連時，則根據(jù)位置在后的塊序列上靠前的原則來對他們進(jìn)行合并。 用一個鏈表來存儲單個部分的NewGoto序列，因?yàn)樗簧婕安迦氲叫蛄惺祝褪孜蚕嘟雍喜蓚€操作,我們來具體討論如何合并：,b1,bi,A,Ba1Bak,A,Ba1Bak,A,6,3,2,1,4,5,2,1,5,3,4,2,6,3,4,士兵排隊(duì),Goto(4,1) Goto(4,2) Goto(5,3) Goto(2,4) Goto(4,5) Goto(3,6),1,2,3,4,5,6,具體實(shí)現(xiàn)的例子：,1,2,1,3,2,1,4,5,3,2,1,5,3,2,1,6,4,士兵排隊(duì),根據(jù)Goto序列構(gòu)造NewGoto序列。轉(zhuǎn)化成前一題最終轉(zhuǎn)化成的一維線性