淺談數(shù)據(jù)的合理組織-wenkub.com
2025-06-27 06:12 本頁面
【正文】 在整個(gè)數(shù)據(jù)中，任意兩個(gè)星球之間最多只可能存在一條直接的航線。C為1表示詢問當(dāng)前星球A和星球B之間有多少條關(guān)鍵航線；C為0表示在星球A和星球B之間的航線被破壞，當(dāng)后面再遇到C為1的情況時(shí)，表示詢問航線被破壞后，關(guān)鍵路徑的情況，且航線破壞后不可恢復(fù)； C為1表示輸入文件結(jié)束，這時(shí)該行沒有A,B的值。輸入：第一行有兩個(gè)整數(shù)N，M。假設(shè)在上圖中，航線42（從4號(hào)星球到2號(hào)星球）被破壞。例如下圖所示：在5個(gè)星球之間，有5條探險(xiǎn)航線?！据斎霕永?11123413【輸出樣例】2 0 00 0 00 3 10 1 1航線規(guī)劃 NOI2005安徽省隊(duì)選拔賽題目【題目描述】對(duì)Samuel星球的探險(xiǎn)已經(jīng)取得了非常巨大的成就，于是科學(xué)家們將目光投向了Samuel星球所在的星系——一個(gè)巨大的由千百萬星球構(gòu)成的Samuel星系。遺憾的是果樹可能很龐大，而小蟲幾乎是不會(huì)計(jì)算的，身為程序員的你幫幫他們吧。他們觀察著這棵果樹，果樹開始端 是露出地面的根部，接著像其他果樹一樣，有著諸多分叉（如圖3所示就是一棵果樹），在每個(gè)分叉處生長著果實(shí)，自然Nileh和Nixedd的食物就是這些果實(shí)了！他們準(zhǔn)備把果樹分成兩部分，每個(gè)蟲蟲得到各自的一部分，兩分果樹的方法就是選擇一個(gè)分叉點(diǎn)，蟲蟲將他們咬斷（自然分叉點(diǎn)上的果實(shí)也被扔掉了），這樣果樹就被分成兩部分（每個(gè)部分不一定是連在一起的）：分叉點(diǎn)上面的部分和分叉點(diǎn)的下面部分。如果q=0，表示該物品為主件，如果q0，表示該物品為附件，q是所屬主件的編號(hào)）【輸出文件】 ，為不超過總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（200000）。 m ?。ㄆ渲蠳（32000）表示總錢數(shù)，m（60）為希望購買物品的個(gè)數(shù)。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。附件不再有從屬于自己的附件。臺(tái)燈，文具打印機(jī)，掃描儀主件感謝古楠同學(xué)和王曉珂同學(xué)對(duì)我的論文提出了很好的建議。我們?cè)诒桓嬷粋€(gè)很巧妙的算法時(shí)，感興趣的除了算法本身之外，還有就是算法的設(shè)計(jì)者到底是怎么想到這個(gè)算法的。在細(xì)節(jié)實(shí)現(xiàn)中，我們又利用了樹的兩大遍歷序——中序遍歷和前序遍歷，把樹上的求LCA操作和提升子樹的操作變成了序列上的求RMQ操作和給一個(gè)區(qū)間所有元素減去一個(gè)值的操作。利用線段樹或樹狀數(shù)組我們就可以用O(log2(N))的時(shí)間完成這項(xiàng)操作。然后我們還有一個(gè)提升一棵子樹的高度的操作。我們研究發(fā)現(xiàn)，如果操作是加邊的話，我們似乎可以很高效地處理。我們只需要將幾個(gè)有關(guān)的塊進(jìn)行合并。我們思考怎么處理這個(gè)問題：刪邊操作會(huì)導(dǎo)致塊的分裂。預(yù)處理即為一個(gè)求重連通分量的操作，時(shí)間復(fù)雜度為O(M)。若AB屬于不同的重連通分量，則轉(zhuǎn)化為求兩個(gè)樹上節(jié)點(diǎn)的距離。也就是說，一個(gè)重連通分量可以當(dāng)作整體來考慮。我們繼續(xù)思考：樹上的任意兩點(diǎn)間只有一條路徑。我們經(jīng)過思考后發(fā)現(xiàn)，事實(shí)上所謂的關(guān)鍵邊都是圖上的橋(由題目中的描述我們很容易想到)。“形態(tài)”和“順序”這兩種數(shù)據(jù)組織對(duì)象在上面的兩個(gè)例題中分別對(duì)我們進(jìn)行了表演。這樣，我們得到了復(fù)雜度為O(Nlog2(N))的算法。我們一個(gè)很巧妙的方法：從大到小地向線段樹里面加入元素，然后統(tǒng)計(jì)區(qū)間個(gè)數(shù)。顯然，這時(shí)比k大的元素個(gè)數(shù)就是k所在區(qū)間中的元素個(gè)數(shù)。然后把所有分解區(qū)間中比給定元素大的元素個(gè)數(shù)加起來，即為所求。時(shí)間復(fù)雜度為O(Nlog2(N))。這正是我們比較熟悉的序列上的統(tǒng)計(jì)問題。我們定義：一個(gè)元素所在子樹在遍歷序中構(gòu)成的區(qū)間叫作元素所在區(qū)間。我們自然想到利用線段樹、樹狀數(shù)組這些優(yōu)秀的統(tǒng)計(jì)數(shù)據(jù)結(jié)構(gòu)來進(jìn)行題目中要求的統(tǒng)計(jì)任務(wù)。前面我們?cè)跇鋼?jù)的組織結(jié)構(gòu)上進(jìn)行了合理地安排，成功地對(duì)于每一次加強(qiáng)的題目都設(shè)計(jì)出了優(yōu)秀的算法，下面，我們來看一看“順序”的合理安排的例子：［例二］樹的果實(shí)【題意描述】給出一棵有N個(gè)節(jié)點(diǎn)的有根樹（根為1號(hào)節(jié)點(diǎn)），每個(gè)節(jié)點(diǎn)有權(quán)值。而在線形的序列上，沒有用的錢自然地被分配給后面的元素?！拘〗Y(jié)】這是一道很有啟發(fā)性的道目。為了利用上面的結(jié)論，我們還要求出以節(jié)點(diǎn)i為根的子樹的節(jié)點(diǎn)總數(shù)count[i]。我們把它應(yīng)用到本題中來：重要結(jié)論 我們考慮一棵子樹的時(shí)候，如果我們不購買其根節(jié)點(diǎn)，那么其子樹中所有節(jié)點(diǎn)我們都不必討論了。但是這樣有什么好處嗎？還能進(jìn)行動(dòng)態(tài)規(guī)劃嗎？怎樣設(shè)計(jì)狀態(tài)才能傳遞父節(jié)點(diǎn)的狀態(tài)呢？我們?cè)倩剡^去看算法3的狀態(tài)轉(zhuǎn)移：假設(shè)當(dāng)前狀態(tài)是F[i][j][k]，且k=0。但是他們都很有啟發(fā)性：拋棄樹形的結(jié)構(gòu)，重新組織成線形。任務(wù) 購買一些物品，總價(jià)格不超過M，使得被購買的物品的權(quán)值之和最大?！舅惴?】這樣組織數(shù)據(jù)以后，我們利用前面提到的條件“一個(gè)附件能被購買的必要條件是其前面的最近的主件被購買了”，可以輕松地設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法：定義：cost[i]表示第i個(gè)物品的價(jià)格weight[i]表示第i個(gè)物品的權(quán)值F[i][j][k]表示從第i個(gè)物品到第n個(gè)物品，最多花費(fèi)j元，第i個(gè)物品前的主件有(k=1)沒有(k=0)被購買。我們是否有合理的組織數(shù)據(jù)的辦法呢？【數(shù)據(jù)組織方案三】重新安排這些物品的順序，使得每個(gè)附件都緊跟其主件，保證其左邊的第一個(gè)主件就是它附屬的主件。N60M3200【問題分析】題目放寬了“一個(gè)主件最多可以有兩個(gè)附件”這個(gè)限制，其它條件不
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1