淺談數(shù)據(jù)的合理組織-免費閱讀
【正文】 輸出：對每個C為1的詢問，輸出一行一個整數(shù)表示關(guān)鍵航線數(shù)目。小聯(lián)的任務(wù)是，不斷關(guān)注航線被破壞的情況，并隨時給出兩個星球之間的關(guān)鍵航線數(shù)目。13245一些先遣飛船已經(jīng)出發(fā)，在星球之間開辟探險航線?？紤]到被咬掉的果子會被浪費，他們想盡可能地減少浪費，于是蟲蟲給每個果子一個美味值，對于每個果子，他們決定計算如果咬掉這個果子，上面部分、下面部分和從樹根到這個分叉點的路徑中比這個果子更美味的果子各有多少個。 p于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)1~5表示，第5等最重要。圖書更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”?！究偨Y(jié)】“對數(shù)據(jù)的合理組織”無處不在，它不僅僅是一種手段，更是競賽的一種思考方向。顯然，我們可以求出樹的先根遍歷序。如下圖：比如我們加入一條邊AB，T=LCA(A,B)，那么我們的環(huán)上的節(jié)點即為A到T的路徑中和B到T的路徑中的節(jié)點。但事實上這道題目中的圖是隨時變化的(有刪邊操作)，這樣我們就不太好處理了。構(gòu)成一個新圖，顯然，新圖是一棵樹。利用上面的結(jié)論，我們顯然可以先用O(E)的時間求出圖中所有的橋，然后再用O(N2)的時間求出AB間的關(guān)鍵邊的數(shù)量。主要思想是也是利用樹的前根遍歷序，不同的是他的算法是基于容斥原理，需要正反兩次遍歷樹，而我們這里介紹的算法是利用了“組織數(shù)據(jù)的操作順序”這一手段來實現(xiàn)的。那么我們?nèi)绾伪ＷC當(dāng)前列表中的元素權(quán)值都比k的權(quán)值大呢？我們重新組織數(shù)據(jù)：所有元素按從大到小的順序排序。那么我們可以用log2 (L)的時間找到該區(qū)間的所有分解區(qū)間(不超過2log2 (L)個)?，F(xiàn)在問題已經(jīng)轉(zhuǎn)化成為：給出一個序列，每個元素有權(quán)值。從根節(jié)點到該節(jié)點路徑中比該節(jié)點大的節(jié)點總數(shù)：以權(quán)值為關(guān)鍵字構(gòu)造線段樹(若權(quán)值大可行離散化處理)，深度優(yōu)先遍歷樹上節(jié)點，用棧記錄下到節(jié)點的路徑，并把當(dāng)前節(jié)點插入線段樹，在線段樹中我們記錄區(qū)間的元素個數(shù)，當(dāng)前節(jié)點權(quán)值到最大權(quán)值這個區(qū)間中元素個數(shù)即為所求，我們再遞歸處理子樹，在子樹訪問完畢后還須把該節(jié)點從線段樹中刪除。我們再次分析前面的算法，試圖發(fā)現(xiàn)其中內(nèi)在的一些東西。正如上面提到的，我們要在樹的先根遍序上進行動態(tài)規(guī)劃，而這一結(jié)論正是我們成功的關(guān)鍵?；貞浰惴?的思路：把同在一個組的主件放在附件的前面，利用動態(tài)規(guī)劃“加一維”的思想，順利地實現(xiàn)了將問題轉(zhuǎn)化到序列上來。很郁悶的金明【題意描述】給出N個物品，可以直接被購買的稱為主件，而不能直接被購買的稱為附件，附件只有當(dāng)其主件被購買了才能被購買，一個主件可以有任意多個附件，附件可以有多級，也就是說如果某個物品是附件，那么它還有可能有附屬于它的下一級附件。實際上，這時候原來的算法1依然適用，復(fù)雜度仍為O(NM2)。F[i][j]表示前i個對象最多花費j元，能得到的最大權(quán)值。發(fā)現(xiàn)兩道題之間的差別：附件不能被直接購買。【對數(shù)據(jù)的初步組織】主件與附件之間是樹形的關(guān)系。我們已經(jīng)學(xué)習(xí)了很多經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，它們都是合理組織數(shù)據(jù)的表現(xiàn)。本文用幾個經(jīng)典例題從數(shù)據(jù)的結(jié)構(gòu)和順序兩個方面進行合理組織，達到優(yōu)化模型或是提升算法效率的目的。介紹了“合理組織數(shù)據(jù)”在信息學(xué)中建立模型和優(yōu)化算法方面的一些應(yīng)用，例題包含了動態(tài)規(guī)劃、數(shù)據(jù)結(jié)構(gòu)、圖論類型的題目。在優(yōu)化算法中有很好表現(xiàn)。組織一下數(shù)據(jù)，如下圖：（圖1）如圖所示：主件1沒有附件，主件2有兩個附件，主件3只有一個附件。顯然，如果題目中沒有附件，那么本題即為標(biāo)準(zhǔn)的01背包問題。F[i][j]=max(F[i1][jcost[i][k]]+weight[i][k])。但是對于利用原題條件特殊性的算法2，一個對象的取值可能達到N的組合級別，所以我們大可放棄對于算法2的討論。每個物品都有一個權(quán)值(50000)。關(guān)鍵字：主件在前 序列 動態(tài)規(guī)劃我們聯(lián)想到利用樹的先根遍歷序，而且正好滿足上面的關(guān)系?！舅惴?】根據(jù)前面的思考，我們先依次求出每棵樹的先根遍歷序，并保存在同一個序列l(wèi)ist[]中。其實我們這個題主要就是對于樹形結(jié)構(gòu)和線形結(jié)構(gòu)的選擇，所以我們對比算法4和算法1:不難發(fā)現(xiàn)，相比算法4，算法1其實多出的操作就是枚舉分配給左兒子多少錢。我們最大的困難在于求：其子樹中權(quán)值比該節(jié)點大的節(jié)點總數(shù)O(N2)的樸素統(tǒng)計方法是很容易想到的，但是本題的數(shù)據(jù)規(guī)模達到105，O(N2)的復(fù)雜度顯然太高。對于每一個元素，統(tǒng)計一個區(qū)間中有多少元素比該元素大。然后在對每個分解區(qū)間進行處理：二分查找在該區(qū)間中有多少元素的權(quán)值比指定的元素的權(quán)值大。然后依次處理每一個元素：先取得所在區(qū)間的元素個數(shù)，再將該元素插入。有興趣的同學(xué)可以參見何林同學(xué)2005年的論文。然而，我們所優(yōu)化后的程序依然有很高的時間復(fù)雜度，根本不能勝任此題。如下：這樣，對于AB的詢問：若AB屬于同一個重連通分量，則沒有關(guān)鍵邊。如果每次都求一次塊的話，復(fù)雜度會很高。我們需要把環(huán)上的節(jié)點的深度都減小到Depth[T]，并且，我們提升一個節(jié)點，其子孫節(jié)點也要一同被提升相同的高度。這樣，同一棵子樹構(gòu)成一個連續(xù)區(qū)間。在數(shù)據(jù)關(guān)系越來越復(fù)雜，解題模型越來越不明顯的信息學(xué)競賽中，合理地組織了數(shù)據(jù)，就可以說離成功只有一步之遙了。今天一早，金明就開始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：書桌他還從因特網(wǎng)上查到了每件物品的價
高考資料相關(guān)推薦
鄂ICP備17016276號-1