淺談數(shù)據(jù)的合理組織-閱讀頁
2025-07-15 06:12本頁面
【正文】 ：樹上的任意兩點間只有一條路徑。這跟我們的題目有什么關(guān)系呢？顯然，同一個重連通分量(塊)中的任意兩點之間都沒有關(guān)鍵邊。也就是說，一個重連通分量可以當作整體來考慮。構(gòu)成一個新圖，顯然，新圖是一棵樹。若AB屬于不同的重連通分量，則轉(zhuǎn)化為求兩個樹上節(jié)點的距離。那么AB間的距離Dis(A,B)=Depth[A]+Depth[B]2*Depth[LCA(A,B)]注意一個細節(jié)，即我們把一個重連通分量“縮”成一個節(jié)點時，事實上是把分量里面的所有點的深度都設為它們中最小的那個深度，即往上提升(在同一個重連通分量中以深度最小的點作其它點的代表)。預處理即為一個求重連通分量的操作，時間復雜度為O(M)。但事實上這道題目中的圖是隨時變化的(有刪邊操作)，這樣我們就不太好處理了。我們思考怎么處理這個問題：刪邊操作會導致塊的分裂?！具M一步組織數(shù)據(jù)】現(xiàn)在的問題是我們需要快速地將一個塊進行重新求塊，似乎是沒有現(xiàn)成的辦法。我們只需要將幾個有關(guān)的塊進行合并。如下圖：比如我們加入一條邊AB，T=LCA(A,B)，那么我們的環(huán)上的節(jié)點即為A到T的路徑中和B到T的路徑中的節(jié)點。我們研究發(fā)現(xiàn)，如果操作是加邊的話，我們似乎可以很高效地處理。現(xiàn)在我們來考慮細節(jié)實現(xiàn)：我們需要用到LCA，當然可以用中序遍歷+RMQ實現(xiàn)。然后我們還有一個提升一棵子樹的高度的操作。顯然，我們可以求出樹的先根遍歷序。利用線段樹或樹狀數(shù)組我們就可以用O(log2(N))的時間完成這項操作。我們最初利用“收縮”的思想，把圖整理成為一棵樹，然后又巧妙地將數(shù)據(jù)從后往前處理，把原題中的“刪邊操作”操作變成了“加邊操作”。在細節(jié)實現(xiàn)中，我們又利用了樹的兩大遍歷序——中序遍歷和前序遍歷，把樹上的求LCA操作和提升子樹的操作變成了序列上的求RMQ操作和給一個區(qū)間所有元素減去一個值的操作。【總結(jié)】“對數(shù)據(jù)的合理組織”無處不在，它不僅僅是一種手段，更是競賽的一種思考方向。我們在被告知一個很巧妙的算法時，感興趣的除了算法本身之外，還有就是算法的設計者到底是怎么想到這個算法的。這正是我們前進的動力，思想的源泉。感謝古楠同學和王曉珂同學對我的論文提出了很好的建議。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。主件附件打印機，掃描儀圖書臺燈，文具無如果要買歸類為附件的物品，必須先買該附件所屬的主件。附件不再有從屬于自己的附件。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。（其中*為乘號） 請你幫助金明設計一個滿足要求的購物單。 m ?。ㄆ渲蠳（32000）表示總錢數(shù)，m（60）為希望購買物品的個數(shù)。 p如果q=0，表示該物品為主件，如果q0，表示該物品為附件，q是所屬主件的編號）【輸出文件】 ，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（200000）。這天，兩只小蟲Nileh和Nixed決定一起分享一棵果樹。他們觀察著這棵果樹，果樹開始端 是露出地面的根部，接著像其他果樹一樣，有著諸多分叉（如圖3所示就是一棵果樹），在每個分叉處生長著果實，自然Nileh和Nixedd的食物就是這些果實了！他們準備把果樹分成兩部分，每個蟲蟲得到各自的一部分，兩分果樹的方法就是選擇一個分叉點，蟲蟲將他們咬斷（自然分叉點上的果實也被扔掉了），這樣果樹就被分成兩部分（每個部分不一定是連在一起的）：分叉點上面的部分和分叉點的下面部分?？紤]到被咬掉的果子會被浪費，他們想盡可能地減少浪費，于是蟲蟲給每個果子一個美味值，對于每個果子，他們決定計算如果咬掉這個果子，上面部分、下面部分和從樹根到這個分叉點的路徑中比這個果子更美味的果子各有多少個。遺憾的是果樹可能很龐大，而小蟲幾乎是不會計算的，身為程序員的你幫幫他們吧。(１號分叉即樹根，它沒有上級分叉點）輸入文件的第n+i(1=i=n)行一個正數(shù)ai,表示生長在i號分叉上的果實的美味值?！据斎霕永?11123413【輸出樣例】2 0 00 0 00 3 10 1 1航線規(guī)劃 NOI2005安徽省隊選拔賽題目【題目描述】對Samuel星球的探險已經(jīng)取得了非常巨大的成就，于是科學家們將目光投向了Samuel星球所在的星系——一個巨大的由千百萬星球構(gòu)成的Samuel星系。13245一些先遣飛船已經(jīng)出發(fā)，在星球之間開辟探險航線。例如下圖所示：在5個星球之間，有5條探險航線。顯然上圖中，1號與5號星球之間的關(guān)鍵航線有1條：即為45航線。假設在上圖中，航線42（從4號星球到2號星球）被破壞。小聯(lián)的任務是，不斷關(guān)注航線被破壞的情況，并隨時給出兩個星球之間的關(guān)鍵航線數(shù)目。輸入：第一行有兩個整數(shù)N，M。隨后有M行，每行有兩個不相同的整數(shù)A、B表示在星球A與B之間存在一條航線。C為1表示詢問當前星球A和星球B之間有多少條關(guān)鍵航線；C為0表示在星球A和星球B之間的航線被破壞，當后面再遇到C為1的情況時，表示詢問航線被破壞后，關(guān)鍵路徑的情況，且航線破壞后不可恢復； C為1表示輸入文件結(jié)束，這時該行沒有A,B的值。輸出：對每個C為1的詢問，輸出一行一個整數(shù)表示關(guān)鍵航線數(shù)目。在整個數(shù)據(jù)中，任意兩個星球之間最多只可能存在一條直接的
高考資料相關(guān)推薦
鄂ICP備17016276號-1