算法合集之《淺談數(shù)據(jù)的合理組織》(文件)
【正文】 用數(shù)據(jù)結(jié)構(gòu)來進行統(tǒng)計。假設(shè)現(xiàn)在我們要統(tǒng)計一個區(qū)間(長度為L)。這樣每統(tǒng)計一個元素的復(fù)雜度為O(log22(N))。統(tǒng)計區(qū)間元素個數(shù)我們可以直接利用線段樹和樹狀數(shù)組。從大到小保證了現(xiàn)有的所有元素都比待插入的元素大。WC2005何林同學(xué)的論文中介紹了此題的另一解法，復(fù)雜度也為O(Nlog2(N))。下面我們再來分析一個更經(jīng)典的題目：［例三］航線規(guī)劃【題意描述】給出一個有N個點M條邊的無向圖，兩點之間可能有多條邊，然后給出Q個命令，命令共有如下兩種：1 A B表示刪除一條A到B的邊2 A B表示詢問AB間共有多少條關(guān)鍵邊（即刪除改邊后使得AB不連通)數(shù)據(jù)保證任意時刻圖都是連通的。而橋的數(shù)量是O(N)級別的。也就是說樹上的任意一條邊都是關(guān)鍵邊?！境醪浇M織數(shù)據(jù)】由前面的思考，我們把圖中的重連分量都“縮”成一個點。求樹上兩個節(jié)點的距離我們有現(xiàn)成的辦法，定義：Depth[A]為節(jié)點A的深度LCA(A,B)為節(jié)點A和節(jié)點B的最近公共祖先。而對于每一個詢問我們都可以O(shè)(1)完成回答。我們當然可以只對被刪邊所在的塊進行處理，但是最壞情況下還是和每次求一次塊是一樣的。換句話說，就是把一些點的位置抬高，并把它們合并成一個塊。那么我們當然可以把操作反過來處理(先處理后面的操作)，這樣就可以實現(xiàn)我們所要達到我們所期望的結(jié)果——操作變?yōu)橹挥屑舆吅驮儐?。即把一棵子樹的所有?jié)點的Detph都減去同一個數(shù)?！拘〗Y(jié)】這是一道很經(jīng)典的題目。無處不體現(xiàn)出“對數(shù)據(jù)的合理組織”。甚至，我們往往對后者所產(chǎn)生的興趣超過前者?！靖戒洝拷鹈鞯念A(yù)算方案 NOIP2006【題目描述】金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。書柜工作椅金明想買的東西很多，肯定會超過媽媽限定的N元。 設(shè)第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1，j2，……，jk，則所求的總和為： v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。） 從第2行到第m+1行，第j行給出了編號為j1的物品的基本數(shù)據(jù)，每行有3個非負整數(shù) v【輸入樣例】1000 5800 2 0400 5 1300 5 1400 3 0500 2 0【輸出樣例】2200樹的果實 NOI2004浙江省隊選拔賽題目【題目描述】森林中生長著許多奇特的果樹，它們不僅外形獨特，其果實更是可口。Nileh和Nixed就會各自選一個部分吃啦！比如對于左邊這棵樹，如果他們咬掉藍色的果子，那么就被分為紅色和黃色的兩個部分?！据斎敫袷健枯斎胛募谝恍惺且粋€整數(shù)n(n=105)表示樹的分叉數(shù)（包括樹根）輸入文件的第i行一個數(shù)pi，表示分叉i的上一級分叉的編號(pii)。星際空間站的Samuel II巨型計算機經(jīng)過長期探測，已經(jīng)鎖定了Samuel星系中許多星球的空間坐標，并對這些星球從1開始編號3……。A、B兩星球之間，如果某條航線不存在，就無法從A星球抵達B星球，我們則稱這條航線為關(guān)鍵航線。此時，1號與5號星球之間的關(guān)鍵航線就有3條：13，34，45。表示有N個星球（1 N 30000），初始時已經(jīng)有M條航線（1 M 100000）。被破壞的航線數(shù)目與詢問的次數(shù)總和不超過40000。【輸入樣例】5 51 21 33 44 54 21 1 50 4 21 5 11【輸出樣例】13。注意：我們保證無論航線如何被破壞，任意時刻任意兩個星球都能夠相互到達。接下來每行有三個整數(shù)C、A、B。現(xiàn)在請你幫助完成。然而，在宇宙中一些未知的磁暴和行星的沖撞，使得已有的某些航線被破壞，隨著越來越多的航線被破壞，探險飛船又不能及時回復(fù)這些航線，可見兩個星球之間的關(guān)鍵航線會越來越多。探險航線是雙向的，例如從1號星球到3號星球開辟探險航線，那么從3號星球到1號星球也可以使用這條航線。（每個果子的美味值不相等）【輸出格式】輸出共n行，每行三個數(shù)，分別表示咬掉第i個果實后上面部分、下面部分、從樹根到這個分叉點的路徑中比它美味的果實數(shù)。他們以此來選擇最終要被咬掉的果子是哪一個。他們從一直辛勤工作到下午，終于把這棵果樹鋸倒了。 q ?。ㄆ渲衯表示該物品的價格（v10000），p表示該物品的重要度（1~5），q表示該物品是主件還是附件?！据斎胛募俊 ?的第1行，為兩個正整數(shù)，用一個空格隔開： N他還從因特網(wǎng)上查到了每件物品的價格（都是10元的整數(shù)倍）。每個主件可以有0個、1個或2個附件。書桌電腦今天一早，金明就開始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個主件的，下表就是一些主件與附件的例子：多思考、多總結(jié)、勇于探索、不斷創(chuàng)新！【參考資料】《算法藝術(shù)與信息學(xué)競賽》 劉汝佳 黃亮 著2005年國家集訓(xùn)隊論文《數(shù)據(jù)關(guān)系的簡化》何林【感謝】感謝葉詩富老師對我的指導(dǎo)和幫助。在數(shù)據(jù)關(guān)系越來越復(fù)雜，解題模型越來越不明顯的信息學(xué)競賽中，合理地組織了數(shù)據(jù)，就可以說離成功只有一步之遙了。既有“形態(tài)”，又有“順序”上的考慮。這樣，同一棵子樹構(gòu)成一個連續(xù)區(qū)間。而且，加邊操作并不影響LCA。我們需要把環(huán)上的節(jié)點的深度都減小到Depth[T]，并且，我們提升一個節(jié)點，其子孫節(jié)點也
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1