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