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