淺談數(shù)據(jù)的合理組織-全文預覽
【正文】 升一個節(jié)點，其子孫節(jié)點也要一同被提升相同的高度。但是如果操作不是刪邊，而是加邊呢？顯然，在一棵樹上加上一條邊，必然產生環(huán)，伴隨著的就是新的重連通分量產生。如果每次都求一次塊的話，復雜度會很高。如此一來，對于一個現(xiàn)成的圖，我們可以很快地求出兩點間的關鍵邊數(shù)量了。如下：這樣，對于AB的詢問：若AB屬于同一個重連通分量，則沒有關鍵邊。并且，對于兩個不同的重連通分量M1,M2：在進行刪邊操作以前，詢問任意分屬這兩個分量的兩點A∈M1,B∈M2，詢問的結果都是一樣的，即結果只跟分量間的邊有關系。然而，我們所優(yōu)化后的程序依然有很高的時間復雜度，根本不能勝任此題。這個算法處理刪邊的復雜度為O(1)，處理詢問的復雜度為O(M2)，空間復雜度為O(M+N)。有興趣的同學可以參見何林同學2005年的論文。按照從大到小的順序之前先對其區(qū)間進行統(tǒng)計，利用線段樹或樹狀數(shù)組。然后依次處理每一個元素：先取得所在區(qū)間的元素個數(shù)，再將該元素插入?！緮?shù)據(jù)組織方案二】我們從特殊情況考慮：假設我們在先根遍歷序中，需要統(tǒng)計元素k，并且k所在區(qū)間里的元素都比它大。然后在對每個分解區(qū)間進行處理：二分查找在該區(qū)間中有多少元素的權值比指定的元素的權值大。這樣，預處理可以用一個歸并排序，求得樹上所有區(qū)間的有序表。對于每一個元素，統(tǒng)計一個區(qū)間中有多少元素比該元素大。我們給出一個例子：同一棵子樹構成一個連續(xù)的區(qū)間，這正方便了我們的統(tǒng)計。我們最大的困難在于求：其子樹中權值比該節(jié)點大的節(jié)點總數(shù)O(N2)的樸素統(tǒng)計方法是很容易想到的，但是本題的數(shù)據(jù)規(guī)模達到105，O(N2)的復雜度顯然太高。我們得到的啟示：憑第一感覺想出來的模型不一定是最好的，對于一個題目，我們充分挖掘其數(shù)據(jù)關系并加以利用，合理地組織數(shù)據(jù)并且嘗試用已有的知識來解決，推陳出新，才能不斷地進步。其實我們這個題主要就是對于樹形結構和線形結構的選擇，所以我們對比算法4和算法1:不難發(fā)現(xiàn)，相比算法4，算法1其實多出的操作就是枚舉分配給左兒子多少錢。并且，這個算法模型對于以前有很多類似的樹形動態(tài)規(guī)劃題目都適用，這是我們在分析本題的過程中的意外收獲。【算法4】根據(jù)前面的思考，我們先依次求出每棵樹的先根遍歷序，并保存在同一個序列l(wèi)ist[]中。思考并總結上面的結論：對于一個主件，我們如果不購買的話，那么其附件我們都不用考慮，而直接“跳”到下一個主件。關鍵字：主件在前 序列 動態(tài)規(guī)劃我們聯(lián)想到利用樹的先根遍歷序，而且正好滿足上面的關系。而利用了題目特殊條件的算法2和算法3，直接套用算法肯定是行不通的。每個物品都有一個權值(50000)。原本樹上的問題經過我們“合理地組織數(shù)據(jù)以后”，成功地轉化成了一個序列上的問題。但是對于利用原題條件特殊性的算法2，一個對象的取值可能達到N的組合級別，所以我們大可放棄對于算法2的討論。任務 購買一些物品，總價格不超過M，使得被購買的物品的權值之和最大。F[i][j]=max(F[i1][jcost[i][k]]+weight[i][k])。對于每一組，可能的購買方案最多只有：這樣，我們可以借鑒經典的01背包動態(tài)規(guī)劃，把每一組看作一個對象，取值和花費對應最多五種。顯然，如果題目中沒有附件，那么本題即為標準的01背包問題。這樣枚舉的效率顯然不高！我們可以用左兒子右兄弟表示法來表示這一棵樹，將原樹轉化成二叉樹，則我們在進行狀態(tài)轉移的時候只用考慮給左兒子分配多少錢。組織一下數(shù)據(jù)，如下圖：（圖1）如圖所示：主件1沒有附件，主件2有兩個附件，主件3只有一個附件。任務 購買一些物品，總價格不超過M，使得被購買的物品的權值之和最大。在優(yōu)化算法中有很好表現(xiàn)。不同的是HASH表和TRIE是利用數(shù)據(jù)形式的重新組織，而預排序＋二分查找是通過對數(shù)據(jù)順序的重新組織來達到優(yōu)化算法的目的的。介紹了“合理組織數(shù)據(jù)”在信息學中建立模型和優(yōu)化算法方面的一些應用，例題包含了動態(tài)規(guī)劃、數(shù)據(jù)結構、圖論類型的題目。淺談數(shù)據(jù)的合理組織 【摘要】信息學是一門高深的學科，它正在高速的發(fā)展。本文用幾個經典例題從數(shù)據(jù)的結構和順序兩個方面進行合理組織，達到優(yōu)化模型或是提升算法效率的目的。當然我們有很多已知的辦法：HASH表、TRIE、預排序+二分查找……這些算法都是通過對數(shù)據(jù)進行合理的組織而起到了減少工作量的作用。我們已經學習了很多經典的數(shù)據(jù)結構，它們都是合理組織數(shù)據(jù)的表現(xiàn)。我們稱可以直接被購買的物品為主件，稱不能被直接購買的物品為附件，附件只有當其主件被購買了才能被購買，一個主件最多有兩個附件，附件沒有下一級附件?！緦?shù)據(jù)的初步組織】主件與附件之間是樹形的關系。其中ci為a的子節(jié)點；∑bi=bcost[a]。發(fā)現(xiàn)兩道題之間的差別：附件不能被直接購買。這樣，顯然對于（圖一）中每一組（主件＋附件），可以作為整體考慮。F[i][j]表示前i個對象最多花費j元，能得到的最大權值。每個物品都有一個權值(50000)。實際上，這時候原來的算法1依然適用，復雜度仍為O(NM2)?？此坪驮瓉淼臈l件沒有什么變化，但是實際上我們給節(jié)點的位置已經加上了一個限制。很郁悶的金明【題意描述】給出N個物品，可以直接被購買的稱為主件，而不能直接被購買的稱為附件，附件只有當其主件被購買了才能被購買，一個主件可以有任意多個附件，附件可以有多級，也就是說如果某個物品是附件，那么它還有可能有附屬于
高考資料相關推薦
鄂ICP備17016276號-1