淺談數(shù)據(jù)的合理組織-預(yù)覽頁(yè)
【正文】 它的下一級(jí)附件。我們依然試著從前面的題目中尋找算法：我們可以直接套用算法1，因?yàn)樵撍惴ㄕ脤?shù)據(jù)作為樹結(jié)構(gòu)來(lái)進(jìn)行處理?；貞浰惴?的思路：把同在一個(gè)組的主件放在附件的前面，利用動(dòng)態(tài)規(guī)劃“加一維”的思想，順利地實(shí)現(xiàn)了將問(wèn)題轉(zhuǎn)化到序列上來(lái)。上圖中，對(duì)于附件a，實(shí)際上一個(gè)k=0的狀態(tài)傳遞下去是沒(méi)有意義的，因?yàn)楦郊和附件c也必然不能被購(gòu)買。正如上面提到的，我們要在樹的先根遍序上進(jìn)行動(dòng)態(tài)規(guī)劃，而這一結(jié)論正是我們成功的關(guān)鍵。狀態(tài)轉(zhuǎn)移：對(duì)于一個(gè)節(jié)點(diǎn)，我們考慮是否購(gòu)買它：購(gòu)買：那么我們繼續(xù)考慮它后面的節(jié)點(diǎn)不購(gòu)買：那么我們跳過(guò)它的子孫節(jié)點(diǎn)方程如下：F[i][j]=Max{F[i+1][jcost[list[i]]]+weight[list[i]],F[i+count[list[i]]][j]}這個(gè)算法依然是O(NM)的，很完美地解決了本題。我們?cè)俅畏治銮懊娴乃惴?，試圖發(fā)現(xiàn)其中內(nèi)在的一些東西。這正是樹形動(dòng)態(tài)規(guī)劃算法的瓶頸所在！而我們利用樹的先根遍歷序?qū)⑥D(zhuǎn)樹形轉(zhuǎn)化為線形序列，成功地避免了樹形形態(tài)的限制，正是合理地組織數(shù)據(jù)。從根節(jié)點(diǎn)到該節(jié)點(diǎn)路徑中比該節(jié)點(diǎn)大的節(jié)點(diǎn)總數(shù)：以權(quán)值為關(guān)鍵字構(gòu)造線段樹(若權(quán)值大可行離散化處理)，深度優(yōu)先遍歷樹上節(jié)點(diǎn)，用棧記錄下到節(jié)點(diǎn)的路徑，并把當(dāng)前節(jié)點(diǎn)插入線段樹，在線段樹中我們記錄區(qū)間的元素個(gè)數(shù)，當(dāng)前節(jié)點(diǎn)權(quán)值到最大權(quán)值這個(gè)區(qū)間中元素個(gè)數(shù)即為所求，我們?cè)龠f歸處理子樹，在子樹訪問(wèn)完畢后還須把該節(jié)點(diǎn)從線段樹中刪除。既然沒(méi)有辦法改造數(shù)據(jù)結(jié)構(gòu)，那么我們轉(zhuǎn)換數(shù)據(jù)形態(tài)——把樹轉(zhuǎn)化為序列再進(jìn)行統(tǒng)計(jì)，先根遍歷序即是我們轉(zhuǎn)換后的理想形態(tài)?，F(xiàn)在問(wèn)題已經(jīng)轉(zhuǎn)化成為：給出一個(gè)序列，每個(gè)元素有權(quán)值。當(dāng)然我們可以構(gòu)造出一種比較有效的嵌套數(shù)據(jù)結(jié)構(gòu)——以有序表為元素的線段樹，如圖： 其中，線段樹的每一個(gè)節(jié)點(diǎn)是對(duì)應(yīng)區(qū)間的元素以權(quán)值為關(guān)鍵字的有序表。那么我們可以用log2 (L)的時(shí)間找到該區(qū)間的所有分解區(qū)間(不超過(guò)2log2 (L)個(gè))。總時(shí)間復(fù)雜度為O(Nlog22(N))，空間復(fù)雜度為O(Nlog2(N))。那么我們?nèi)绾伪ＷC當(dāng)前列表中的元素權(quán)值都比k的權(quán)值大呢？我們重新組織數(shù)據(jù)：所有元素按從大到小的順序排序。所以區(qū)間中的元素個(gè)數(shù)即為比待插入元素大的元素個(gè)數(shù)。主要思想是也是利用樹的前根遍歷序，不同的是他的算法是基于容斥原理，需要正反兩次遍歷樹，而我們這里介紹的算法是利用了“組織數(shù)據(jù)的操作順序”這一手段來(lái)實(shí)現(xiàn)的。1 ≤ N ≤ 3 * 1041 ≤ M ≤ 1051 ≤ Q ≤ 105【問(wèn)題分析】顯然，我們可以輕松地設(shè)計(jì)出一個(gè)樸素的算法：用隊(duì)列保存所有邊，當(dāng)遇到刪邊操作時(shí)加上刪除標(biāo)記（利用HASH我們可以做到O(1))，遇到詢問(wèn)操作時(shí)則枚舉刪邊然后用并查集判斷AB是否連通。利用上面的結(jié)論，我們顯然可以先用O(E)的時(shí)間求出圖中所有的橋，然后再用O(N2)的時(shí)間求出AB間的關(guān)鍵邊的數(shù)量。這跟我們的題目有什么關(guān)系呢？顯然，同一個(gè)重連通分量(塊)中的任意兩點(diǎn)之間都沒(méi)有關(guān)鍵邊。構(gòu)成一個(gè)新圖，顯然，新圖是一棵樹。那么AB間的距離Dis(A,B)=Depth[A]+Depth[B]2*Depth[LCA(A,B)]注意一個(gè)細(xì)節(jié)，即我們把一個(gè)重連通分量“縮”成一個(gè)節(jié)點(diǎn)時(shí)，事實(shí)上是把分量里面的所有點(diǎn)的深度都設(shè)為它們中最小的那個(gè)深度，即往上提升(在同一個(gè)重連通分量中以深度最小的點(diǎn)作其它點(diǎn)的代表)。但事實(shí)上這道題目中的圖是隨時(shí)變化的(有刪邊操作)，這樣我們就不太好處理了?！具M(jìn)一步組織數(shù)據(jù)】現(xiàn)在的問(wèn)題是我們需要快速地將一個(gè)塊進(jìn)行重新求塊，似乎是沒(méi)有現(xiàn)成的辦法。如下圖：比如我們加入一條邊AB，T=LCA(A,B)，那么我們的環(huán)上的節(jié)點(diǎn)即為A到T的路徑中和B到T的路徑中的節(jié)點(diǎn)?，F(xiàn)在我們來(lái)考慮細(xì)節(jié)實(shí)現(xiàn)：我們需要用到LCA，當(dāng)然可以用中序遍歷+RMQ實(shí)現(xiàn)。顯然，我們可以求出樹的先根遍歷序。我們最初利用“收縮”的思想，把圖整理成為一棵樹，然后又巧妙地將數(shù)據(jù)從后往前處理，把原題中的“刪邊操作”操作變成了“加邊操作”。【總結(jié)】“對(duì)數(shù)據(jù)的合理組織”無(wú)處不在，它不僅僅是一種手段，更是競(jìng)賽的一種思考方向。這正是我們前進(jìn)的動(dòng)力，思想的源泉。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：“你的房間需要購(gòu)買哪些物品，怎么布置，你說(shuō)了算，只要不超過(guò)N元錢就行”。附件圖書無(wú)如果要買歸類為附件的物品，必須先買該附件所屬的主件。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)1~5表示，第5等最重要。（其中*為乘號(hào)） 請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單。 p這天，兩只小蟲Nileh和Nixed決定一起分享一棵果樹?？紤]到被咬掉的果子會(huì)被浪費(fèi)，他們想盡可能地減少浪費(fèi)，于是蟲蟲給每個(gè)果子一個(gè)美味值，對(duì)于每個(gè)果子，他們決定計(jì)算如果咬掉這個(gè)果子，上面部分、下面部分和從樹根到這個(gè)分叉點(diǎn)的路徑中比這個(gè)果子更美味的果子各有多少個(gè)。(１號(hào)分叉即樹根，它沒(méi)有上級(jí)分叉點(diǎn)）輸入文件的第n+i(1=i=n)行一個(gè)正數(shù)ai,表示生長(zhǎng)在i號(hào)分叉上的果實(shí)的美味值。13245一些先遣飛船已經(jīng)出發(fā)，在星球之間開(kāi)辟探險(xiǎn)航線。顯然上圖中，1號(hào)與5號(hào)星球之間的關(guān)鍵航線有1條：即為45航線。小聯(lián)的任務(wù)是，不斷關(guān)注航線被破壞的情況，并隨時(shí)給出兩個(gè)星球之間的關(guān)鍵航線數(shù)目。隨后有M行，每行有兩個(gè)不相同的整數(shù)A、B表示在星球A與B之間存在一條航線。輸出：對(duì)每個(gè)C為1的詢問(wèn)，輸出一行一個(gè)整數(shù)表示關(guān)鍵航線
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1