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