數(shù)據(jù)結構的提煉與壓縮

1、數(shù)據(jù)結構的提煉與壓縮數(shù)據(jù)結構的提煉與壓縮上海市上海中學 曹欽翔指導教師：上海市上海中學 毛黎莉數(shù)據(jù)結構的數(shù)據(jù)結構的“化繁為簡化繁為簡” 減少存儲規(guī)模減少存儲規(guī)模 化簡存儲結構化簡存儲結構 時空復雜度降低時空復雜度降低 處理方式多樣處理方式多樣“化繁為簡化繁為簡”的三種手段的三種手段提煉：忽略無效信息，減少存儲規(guī)模提煉：忽略無效信息，減少存儲規(guī)模壓壓 ：調(diào)整存儲方式，化簡存儲結構：調(diào)整存儲方式，化簡存儲結構縮縮 ：合并重復信息，減少存儲規(guī)模：合并重復信息，減少存儲規(guī)模 1.二維結構的化簡二維結構的化簡 問題一：問題一：Ural 1568 Train car sortingUral 1568 Tr

2、ain car sorting 問題描述：對于一個序列問題描述：對于一個序列aan n ，定義一種操作，將，定義一種操作，將aan n 分分成兩個子列，把其中一個置于另一個前面，得到一個新的成兩個子列，把其中一個置于另一個前面，得到一個新的序列?，F(xiàn)給出一個序列（這個序列是序列?，F(xiàn)給出一個序列（這個序列是1 1到到n n的一個排列），的一個排列），求一種方案，通過最少的操作次數(shù)是它變成升序序列。求一種方案，通過最少的操作次數(shù)是它變成升序序列。一個操作的例子一個操作的例子5 4 3 2 15 3 2 4 15 3 2 4 1算法算法（5 5，3 3，2 2，4 4，1 1）5 5 0 03 3 4

3、 42 2 0 00 0 1 1偶數(shù)行偶數(shù)行3 3，4 4，1 1奇數(shù)行奇數(shù)行5 5，2 2（3 3，4 4，1 1，5 5，2 2）合并合并優(yōu)化數(shù)據(jù)結構優(yōu)化數(shù)據(jù)結構樸素實現(xiàn)，單次操作復雜度樸素實現(xiàn)，單次操作復雜度O(nO(n2 2) )。需要優(yōu)化。需要優(yōu)化零元素過多，形成冗余零元素過多，形成冗余提煉：忽略零元素提煉：忽略零元素問題二：問題二：CEOI 2007 Day 2 Necklace CEOI 2007 Day 2 Necklace 問題描述：要求編譯一個庫，能夠對若干已知的整數(shù)串問題描述：要求編譯一個庫，能夠對若干已知的整數(shù)串進行兩個操作：進行兩個操作：（1 1）在某個已知串的左端或

4、右端增加或減少一個元素，）在某個已知串的左端或右端增加或減少一個元素，得到一個新的已知的串。得到一個新的已知的串。（2 2）輸出某個已知串的最左端或最右端的數(shù)。）輸出某個已知串的最左端或最右端的數(shù)。在問題的一開始，只有一個已知的串：空串。在問題的一開始，只有一個已知的串：空串。分析分析樸素方法：每個串分別儲存樸素方法：每個串分別儲存復雜度過高，難以承受復雜度過高，難以承受大量重復信息，空間嚴重浪費大量重復信息，空間嚴重浪費縮：合并重復信息縮：合并重復信息兩個特例兩個特例BAACADACBCABCABABCDABC星形星形 鏈形鏈形 特特例例存存儲儲方方式式數(shù)據(jù)結構數(shù)據(jù)結構:Left-Right

5、 Tree123456789left treeright treeleft_leave left_root right_root right_leave添加新結點添加新結點1234567912345678912345679123456789刪除結點刪除結點123456791234567891234567912345678912345679123456789轉化結論轉化結論已知樹中某鏈的兩端點，求底部端點的父親已知樹中某鏈的兩端點，求底部端點的父親已知樹中某鏈的兩端點，求頂部端點在鏈中的已知樹中某鏈的兩端點，求頂部端點在鏈中的兒子兒子 2.樹形結構的化簡樹形結構的化簡問題五：問題二的遺留問題問題

6、五：問題二的遺留問題問題描述：給定一棵有根樹，在線回答兩種詢問：問題描述：給定一棵有根樹，在線回答兩種詢問：（1）已知樹中某鏈的兩端點，求底部端點的父親）已知樹中某鏈的兩端點，求底部端點的父親（2）已知樹中某鏈的兩端點，求頂部端點在鏈中的兒）已知樹中某鏈的兩端點，求頂部端點在鏈中的兒子子分析分析提煉：后代信息成為冗余，不再儲存提煉：后代信息成為冗余，不再儲存樸素方法：左兒子右兄弟樸素方法：左兒子右兄弟最壞情況下時間效率差最壞情況下時間效率差轉化：頂結點的兒子轉化：頂結點的兒子底結點的超級祖先底結點的超級祖先數(shù)據(jù)結構數(shù)據(jù)結構:Supper FatherxSu(x,0)Su(x,0)Su(x,2)

7、Su(x,2)Su(x,1)Su(x,1)用用Su(x,k)Su(x,k)表示結點表示結點x x的第的第2 2k k代祖先代祖先3.圖結構的化簡圖結構的化簡 問題六：問題六：ural 1557 Network Attackural 1557 Network Attack 問題描述：給定一個無向連通圖，若從中刪去兩條邊能使問題描述：給定一個無向連通圖，若從中刪去兩條邊能使它不連通，求所有這樣的方案的總數(shù)。圖點數(shù)它不連通，求所有這樣的方案的總數(shù)。圖點數(shù)n n邊數(shù)邊數(shù)m m。 分析分析核心問題：圖結構復雜不易處理核心問題：圖結構復雜不易處理關鍵信息：連通性關鍵信息：連通性壓：以圖的壓：以圖的DFSD

8、FS樹為解題突破口樹為解題突破口兩種情況兩種情況小結小結謝謝謝謝算法算法 原序列的最簡母矩陣中偶數(shù)行的非零元素，形成一個子列，原序列的最簡母矩陣中偶數(shù)行的非零元素，形成一個子列，前置。前置。 原序列的最簡母矩陣中奇數(shù)行的非零元素，形成一個子列，原序列的最簡母矩陣中奇數(shù)行的非零元素，形成一個子列，后置。后置。 形成新序列。形成新序列。 不斷重復，直到的到升序列。不斷重復，直到的到升序列。2.樹形結構的化簡樹形結構的化簡 問題三：浙江問題三：浙江20072007年省選年省選 捉迷藏捉迷藏 問題描述：給定一棵樹，每個節(jié)點要么是黑色，要么是白問題描述：給定一棵樹，每個節(jié)點要么是黑色，要么是白色，能執(zhí)行

9、一個操作：把某一個點取反色。動態(tài)維護并返色，能執(zhí)行一個操作：把某一個點取反色。動態(tài)維護并返回樹中距離最遠的黑色點對?；貥渲芯嚯x最遠的黑色點對。 分析分析問題類型：局部參數(shù)調(diào)整問題類型：局部參數(shù)調(diào)整+ +整體屬性返回整體屬性返回解題障礙：樹形結構不易整體處理解題障礙：樹形結構不易整體處理壓：線性結構存儲壓：線性結構存儲“點對距離點對距離”數(shù)據(jù)結構數(shù)據(jù)結構:括號編碼括號編碼ABECDABCDEABCDE 數(shù)據(jù)結構數(shù)據(jù)結構:括號編碼括號編碼存儲方式：存儲方式：（）（） （2 2，1 1）結論：對于兩個點結論：對于兩個點PQPQ，如果介于某兩點，如果介于某兩點PQPQ之間編之間編碼碼S S可表示為可表

10、示為(a,b)(a,b)，PQPQ之間的距離就是之間的距離就是a+ba+b。數(shù)據(jù)結構數(shù)據(jù)結構:括號編碼括號編碼合并方式：合并方式：+ = () = + = () = + = () = + = () = 當當a2=b1a2=b1a2=b1時時(a1,b1)+(a2,b2)=(a1,b1-a2+b2)(a1,b1)+(a2,b2)=(a1,b1-a2+b2)對于（對于（a,b)=(a1,b1)+(a2,b2)a,b)=(a1,b1)+(a2,b2)a+b=a1+b2+|a2-b1|=a1+b2+Maxa2-b1,b1-a2a+b=a1+b2+|a2-b1|=a1+b2+Maxa2-b1,b1-a2

11、 =Max(a1+a2)+(b2-b1),(a1-a2)+(b1+b2) =Max(a1+a2)+(b2-b1),(a1-a2)+(b1+b2)數(shù)據(jù)結構數(shù)據(jù)結構:括號編碼括號編碼+線段樹線段樹 維護以下變量維護以下變量dis(s) dis(s) ：a+b|S(a,b)a+b|S(a,b)是是S S的一個子串，且的一個子串，且SS介于兩個黑點之間介于兩個黑點之間 right_plusright_plus：maxa+b|S(a,b)maxa+b|S(a,b)是是S S的一個后綴，且的一個后綴，且SS緊接在一個黑點之后緊接在一個黑點之后 right_minusright_minus：maxa-b|S

12、(a,b)maxa-b|S(a,b)是是S S的一個后綴，且的一個后綴，且SS緊接在一個黑點之后緊接在一個黑點之后 left_plusleft_plus：maxa+b|S(a,b)maxa+b|S(a,b)是是S S的一個前綴，且有一個黑點緊接在的一個前綴，且有一個黑點緊接在S S之后之后 left_minusleft_minus：maxb-a|S(a,b)maxb-a|S(a,b)是是S S的一個前綴，且有一個黑點緊接在的一個前綴，且有一個黑點緊接在S S之后之后 數(shù)據(jù)結構數(shù)據(jù)結構:括號編碼括號編碼+線段樹線段樹 利用以下公式實現(xiàn)合并：利用以下公式實現(xiàn)合并：S=S1+S2S=S1+S2，其中

13、，其中S1(a,b)S1(a,b)、S2(c,d)S2(c,d)dis(S)=maxright_plus(S1)+left_minus(S2)dis(S)=maxright_plus(S1)+left_minus(S2)，right_minus(S1)+left_plus(S2)right_minus(S1)+left_plus(S2)，dis(S1)dis(S1)，dis(S2) dis(S2) right_plus(S)right_plus(S)=maxright_plus(S1)-c+d,right_minus(S1)+c+d,right_plus(S2)=maxright_plus(S

14、1)-c+d,right_minus(S1)+c+d,right_plus(S2)left_plus(S)left_plus(S)=maxleft_plus(S2)-b+a,left_minus(S2)+b+a, left_plus(S1)=maxleft_plus(S2)-b+a,left_minus(S2)+b+a, left_plus(S1)right_minus(S)=maxright_minus(S1)+c-d,right_minus(S2)right_minus(S)=maxright_minus(S1)+c-d,right_minus(S2)left_minus(S)=maxle

15、ft_minus(S2)+b-a,left_minus(S1)left_minus(S)=maxleft_minus(S2)+b-a,left_minus(S1) 問題三小結問題三小結關鍵點關鍵點1 1：樹形變線形，為使用線段樹創(chuàng)造條件。：樹形變線形，為使用線段樹創(chuàng)造條件。關鍵點關鍵點2 2：數(shù)對表編碼，溝通整體部分關系。：數(shù)對表編碼，溝通整體部分關系。最簡母矩陣最簡母矩陣 稱一個稱一個p p* *q q的矩陣的矩陣A A為序列為序列aan n 的母矩陣，當且僅當，矩陣的母矩陣，當且僅當，矩陣A A中的所有非零元素，自上到下自左到右逐列讀出得到中的所有非零元素，自上到下自左到右逐列讀出得到aan n ，自左到右自下到上逐行讀出得到升序序列。，自左到右自下到上逐行讀出得到升序序列。 稱序列稱序列aan n 的所有母矩陣中，行數(shù)列數(shù)都最小的那個矩陣的所有母矩陣中，行數(shù)列數(shù)都最小的那個矩陣為序列為序列aan n 的最簡母矩陣。的最簡母矩陣。最簡母矩陣最簡母矩陣升序序列DFS VS BFS 其一：性質(zhì)上（結構決定性質(zhì)），其一：性質(zhì)上（結構決定性質(zhì)），DFSDFS遍歷后的可以得到遍歷后的可以得到DFSDFS樹，圖中的邊在樹，圖中的邊在DFSDFS樹中要么是樹邊要么是回邊；而樹中要么是樹邊要么是回邊；而BFSBFS遍歷后往往得到層狀結構，圖中的邊要么連接同一層遍歷后