算法合集之《平衡規(guī)劃》.doc

本資料由-大學(xué)生創(chuàng)業(yè)|創(chuàng)業(yè)|創(chuàng)業(yè)網(wǎng)/提供資料平衡規(guī)劃淺析一類(lèi)平衡思想在信息學(xué)競(jìng)賽中的應(yīng)用福建省福州市第八中學(xué) 鄭 暾 【目錄】l 摘要 2l 關(guān)鍵字 2l 正文 2u 引言 2u 應(yīng)用平衡思想的幾類(lèi)問(wèn)題 3l 經(jīng)典算法的非典型實(shí)現(xiàn) 3n 例題一、警衛(wèi)安排問(wèn)題 3n 例題二、Jackpot 6l 效果優(yōu)秀的非完美算法 8n 例題三、追捕盜賊 8l 復(fù)雜問(wèn)題的簡(jiǎn)單化構(gòu)造 12n 例題四、數(shù)列維護(hù) 12n 例題五、樹(shù)的維護(hù) 14u 總結(jié) 17l 感謝 18l 參考文獻(xiàn) 18l 附錄 18【摘要】 應(yīng)用計(jì)算機(jī)解題的核心是算法設(shè)計(jì)。但算法設(shè)計(jì)方面涉及的領(lǐng)域十分豐富。我們不能奢求能完美地應(yīng)用所有的算法，所以我們關(guān)注的通常是如何合理運(yùn)用已學(xué)知識(shí)，并在所掌握算法間構(gòu)建一種平衡，在限定的時(shí)間內(nèi)盡可能多地解決問(wèn)題。本文嘗試討論一類(lèi)平衡思想應(yīng)用于算法構(gòu)造、算法實(shí)現(xiàn)的模式?！娟P(guān)鍵字】平衡思想、平衡點(diǎn)、時(shí)空效率、編程復(fù)雜度【正文】一、引言 平衡通常指物體或系統(tǒng)的一種狀態(tài)。處于平衡狀態(tài)的物體或系統(tǒng)，除非受到外界的影響，它本身不會(huì)有任何自發(fā)的變化。多種狀態(tài)達(dá)到平衡通常是我們所追求的目標(biāo)。 平衡思想是一種奇妙的思想，它的應(yīng)用十分廣泛。在算法設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)甚至程序設(shè)計(jì)中都能發(fā)現(xiàn)它的身影。計(jì)算機(jī)競(jìng)賽就是一場(chǎng)博弈，尋找這場(chǎng)博弈中的平衡點(diǎn)，合理應(yīng)用平衡思想輔助算法設(shè)計(jì)與程序?qū)崿F(xiàn)，往往能起到化腐朽為神奇的作用。 在信息學(xué)競(jìng)賽中，平衡思想通常有以下幾個(gè)方面的運(yùn)用： 1、博弈問(wèn)題。有許多博弈類(lèi)問(wèn)題都可以轉(zhuǎn)化成尋找平衡點(diǎn)的問(wèn)題。 2、數(shù)據(jù)結(jié)構(gòu)的構(gòu)建。每種數(shù)據(jù)結(jié)構(gòu)都能以?xún)?yōu)秀的性能支持某些操作，合理選擇應(yīng)用數(shù)據(jù)結(jié)構(gòu)，往往能通過(guò)略微提高一些操作的復(fù)雜度，降低大多數(shù)操作的復(fù)雜度，在不同操作的效率之間構(gòu)建一種平衡，以達(dá)到優(yōu)化的目的。3、時(shí)間效率 vs 空間效率。這類(lèi)問(wèn)題是我們經(jīng)常遇到的問(wèn)題。這類(lèi)問(wèn)題通常有這樣的特性，我們能找到時(shí)間效率（或空間效率）十分優(yōu)秀的算法，但代價(jià)是空間效率（或時(shí)間效率）極端低下。如何合理設(shè)計(jì)算法，組織數(shù)據(jù)，平衡二者的關(guān)系是解決這類(lèi)問(wèn)題的重點(diǎn)。4、時(shí)空效率 vs 其他。如果面對(duì)難題難以設(shè)計(jì)出優(yōu)美的算法，又或者設(shè)計(jì)了優(yōu)秀效率的算法，卻無(wú)法實(shí)現(xiàn)或難以實(shí)現(xiàn)，就會(huì)出現(xiàn)非常尷尬的局面。合理應(yīng)用平衡規(guī)劃解決這類(lèi)問(wèn)題，往往能收到意想不到的效果。而這類(lèi)問(wèn)題也正是本文所要重點(diǎn)探討的問(wèn)題。下文將試圖論述運(yùn)用平衡思想解決這類(lèi)問(wèn)題中的三種常見(jiàn)模式：經(jīng)典算法的非典型實(shí)現(xiàn)，效果優(yōu)秀的非完美算法，以及復(fù)雜問(wèn)題的簡(jiǎn)單化構(gòu)造。2、 應(yīng)用平衡思想的幾類(lèi)問(wèn)題1、經(jīng)典算法的非典型實(shí)現(xiàn)。 大多數(shù)經(jīng)典算法通常是為很多人所熟知，并且能夠熟悉運(yùn)用。經(jīng)典算法通常也有很多不同的實(shí)現(xiàn)方法。例如拓?fù)渑判颍绻麛?shù)據(jù)范圍比較大，通常使用算法復(fù)雜度為O(n)的程序，但是如果范圍比較小，一個(gè)不超過(guò)10行的的程序可以使代碼看起來(lái)更為簡(jiǎn)潔。而不同的實(shí)現(xiàn)方法中，哪怕只是細(xì)微的不同，實(shí)現(xiàn)后的性能與效率也可能有很大的差別。更進(jìn)一步，有些算法雖然堪稱(chēng)經(jīng)典，但是無(wú)論是思考復(fù)雜度還是實(shí)現(xiàn)復(fù)雜度都相對(duì)頗高，在考場(chǎng)上來(lái)說(shuō)，使用一些相對(duì)簡(jiǎn)單實(shí)用的方法無(wú)疑是一種不錯(cuò)的選擇。例題一、警衛(wèi)安排問(wèn)題(ural 1099)題目描述： 給定若干警衛(wèi)間搭檔關(guān)系，要求成對(duì)給警衛(wèi)安排保衛(wèi)工作，求能夠安排警衛(wèi)的最大值。（警衛(wèi)人數(shù)不超過(guò)222）初步分析： 題目描述很簡(jiǎn)單，稍加分析后我們很容易看出來(lái)，這題的本質(zhì)其實(shí)是要求我們求出任意圖的最大匹配。 任意圖的最大匹配的經(jīng)典算法是應(yīng)用帶花匈牙利樹(shù)，時(shí)間復(fù)雜度為，對(duì)付這道題來(lái)說(shuō)是綽綽有余的。但是帶花樹(shù)本身比較復(fù)雜，思維復(fù)雜度與編程復(fù)雜度較高，而且實(shí)現(xiàn)起來(lái)很容易退化，考場(chǎng)上有限的時(shí)間內(nèi)難以完成。于是我們嘗試考慮替代算法予以解決。解法分析：解決二分圖最大匹配的時(shí)候，主要過(guò)程是不斷尋找交錯(cuò)增廣樹(shù)來(lái)調(diào)整。那么這么做對(duì)于任意圖是否可行？答案是否定的?？疾煊疫呥@張圖（圖一）。圖中粗線表示當(dāng)前狀態(tài)下已匹配邊，虛線表示未匹配邊。若我們當(dāng)前找的增廣樹(shù)如圖二所示，那么我們就無(wú)法找到一條增廣路。但實(shí)際上，存這樣的一條增廣路：。為了找到增廣路，我們可以采用搜索的方法，但這樣尋找增廣路復(fù)雜度過(guò)高。3452167圖二34521678圖一 我們注意到，采用調(diào)整增廣軌的方法，如果一個(gè)點(diǎn)之前已經(jīng)被匹配到，則之后無(wú)論如何調(diào)整，這個(gè)點(diǎn)始終能被匹配到。因此，對(duì)于一個(gè)待匹配點(diǎn)，是否能找到一條以它為起點(diǎn)的增廣路是優(yōu)化解的關(guān)鍵。而是否能找到一棵增廣樹(shù)又很大程度上依賴(lài)于之前找尋的情況，若要設(shè)計(jì)數(shù)據(jù)使得無(wú)法找到增廣樹(shù)通常又依賴(lài)于特定的擴(kuò)展順序。這啟發(fā)我們采用隨機(jī)擴(kuò)展順序的方法來(lái)盡量避免形成類(lèi)似圖一的特殊局面。 筆者的程序中生成了兩個(gè)隨機(jī)序列，一個(gè)作為點(diǎn)的初次訪問(wèn)序，一個(gè)作為點(diǎn)的拓展順序，然后直接使用一開(kāi)始所說(shuō)的尋找交錯(cuò)樹(shù)的方法來(lái)擴(kuò)展。同時(shí)，采用多次隨機(jī)運(yùn)行的方法提高最優(yōu)解的出現(xiàn)概率。但是作為隨機(jī)貪心算法，除了拿到AC之外，我們更應(yīng)該關(guān)注這個(gè)程序通常的運(yùn)行情況如何。上述算法中，在ural點(diǎn)數(shù)限制僅僅為222以下的情況下，通常運(yùn)行次數(shù)卻要設(shè)定為20至50才能基本上保證AC。相對(duì)于數(shù)據(jù)本身，這個(gè)運(yùn)行次數(shù)還是比較大，說(shuō)明算法本身具有比較大的不確定因素，以及出最優(yōu)解概率并不是很高。所以我們需要進(jìn)一步優(yōu)化以提高一次運(yùn)行的最優(yōu)解出現(xiàn)概率。進(jìn)一步優(yōu)化上述解法中曾提到，采用調(diào)整增廣軌的方法，如果一個(gè)點(diǎn)之前已經(jīng)被匹配到，則之后無(wú)論如何調(diào)整，這個(gè)點(diǎn)始終能被匹配到。它帶來(lái)的另一個(gè)信息是，若一個(gè)點(diǎn)之前未被匹配到，那么在本輪搜索中，這個(gè)點(diǎn)最終將很可能保持未匹配的狀態(tài)。因此影響最終結(jié)果的，往往是某個(gè)本應(yīng)該被匹配到的點(diǎn)因?yàn)橹霸鰪V樹(shù)的查找失敗而被放棄匹配。初始算法解決這個(gè)問(wèn)題的方法是全局重新搜索，所以常常出現(xiàn)為了一個(gè)點(diǎn)而全部重來(lái)的尷尬場(chǎng)面。其實(shí)這是舍近求遠(yuǎn)。我們完全可以換一個(gè)擴(kuò)展順序，對(duì)于當(dāng)前未找到交錯(cuò)樹(shù)從而無(wú)法匹配的點(diǎn)，直接重新搜索一棵交錯(cuò)樹(shù)！當(dāng)然大部分的圖都無(wú)法實(shí)現(xiàn)完美匹配，所以類(lèi)似運(yùn)行次數(shù)的限制，我們需要設(shè)置一個(gè)失敗次數(shù)上限。當(dāng)為一個(gè)未匹配點(diǎn)尋找匹配點(diǎn)時(shí)，只有失敗次數(shù)超過(guò)了這個(gè)上限才放棄。那么失敗上限次數(shù)應(yīng)該設(shè)置為多少比較好？進(jìn)一步的，這個(gè)方法實(shí)現(xiàn)起來(lái)究竟效果如何呢？為此筆者進(jìn)行了一系列的實(shí)驗(yàn)，得到了如下的實(shí)驗(yàn)數(shù)據(jù)表：運(yùn)行次數(shù)-失敗上限5-55-1010-110-1020-120-1050-1Accepted90%100%0%90%60%0%100%Wrong answer10%0%100%10%40%0%0%Time limit exceeded0%0%0%0%0%100%0%平均AC時(shí)間0.07610.1471-0.29600.0385-0.0795實(shí)驗(yàn)的運(yùn)行平臺(tái)是Ural1099的測(cè)試，時(shí)限是0.5秒。表頭的N-M表示程序?qū)⒅貜?fù)運(yùn)行N次，失敗上限設(shè)置為M，例如5-5表示程序?qū)⒅貜?fù)運(yùn)行5次，失敗上限設(shè)置為5。實(shí)驗(yàn)表明，這個(gè)方法能顯著地提高一次運(yùn)行的最優(yōu)解出現(xiàn)概率。從表中數(shù)據(jù)可以看出，初始算法直到20-1才有50%以上的AC率，而優(yōu)化后的方法將失敗上限設(shè)置為5就可以讓僅僅重復(fù)運(yùn)行5次的AC率達(dá)到了90%。當(dāng)然，這種方法同樣存在一定的隨機(jī)因素，加之Ural1099的數(shù)據(jù)比較強(qiáng)大（從數(shù)量到質(zhì)量），所以出現(xiàn)了如表中5-10是100%AC但是10-10卻只有90%的AC率的情況。但正所謂有得必有失。優(yōu)化后的方法有著極高的準(zhǔn)確率，但同時(shí)時(shí)間效率并不高。實(shí)驗(yàn)中，5-5的時(shí)間已經(jīng)逼近了50-1的時(shí)間。雖然相對(duì)于時(shí)限來(lái)說(shuō)還是比較輕松，但是其增長(zhǎng)還是較可觀的（20-10的全部超時(shí)就可以說(shuō)明這一點(diǎn)）。實(shí)際上，雖然理論上時(shí)間復(fù)雜度僅僅是多一個(gè)所設(shè)置的失敗上限的常數(shù)，但由于將進(jìn)一步優(yōu)化中需要大量地使用了隨機(jī)函數(shù)，而生成隨機(jī)函數(shù)的常數(shù)比較大，造成了實(shí)際程序的常數(shù)較大，拖累了時(shí)間。所以，兩種算法都有其各自的優(yōu)缺點(diǎn)，這就需要我們根據(jù)題目的給出的信息，根據(jù)實(shí)際算法的需求來(lái)進(jìn)行選擇。進(jìn)一步擴(kuò)展：隨機(jī)搜索序和設(shè)置失敗上限的作用并不局限于此。對(duì)于隨機(jī)搜索序，表面上看是根據(jù)克制數(shù)據(jù)或克制情況的順序依賴(lài)性 即特殊情況依賴(lài)于一定的順序，例如本題是克制數(shù)據(jù)的生成依賴(lài)于一定的搜索順序。，應(yīng)用隨機(jī)的順序來(lái)進(jìn)行回避。其實(shí)其本質(zhì)是：通過(guò)設(shè)置一些隨機(jī)權(quán)值，以改變一個(gè)當(dāng)前狀態(tài)的屬性，從而回避特殊情況的生成（例如本題是回避克制數(shù)據(jù)的生成）。我們常用的Treap，隨機(jī)快排（隨機(jī)選擇比較變量），其本質(zhì)也是如此。設(shè)置失敗上限則是隨機(jī)搜索序關(guān)于準(zhǔn)確率的一個(gè)優(yōu)化。隨機(jī)算法不可避免還是有可能無(wú)法得到我們理想的狀態(tài)或結(jié)果（例如本題依然可能找不到存在的增廣路，又例如Treap并不完全平衡）。隨機(jī)搜索序通常是全局重新運(yùn)行來(lái)提高最優(yōu)解的出現(xiàn)概率，而設(shè)置失敗上限則是通過(guò)對(duì)于局部問(wèn)題的精益求精來(lái)強(qiáng)化全局目標(biāo)情況出現(xiàn)概率，常見(jiàn)的應(yīng)用有大素?cái)?shù)的測(cè)試等。小結(jié)：對(duì)于這道題，兩種方法都可以比較輕松地通過(guò)?？紤]到數(shù)據(jù)范圍并不大，為了追求準(zhǔn)確率可以增加參數(shù)上限，或者為了保證時(shí)間效率壓縮參數(shù)上限，這需要我們根據(jù)實(shí)際情況合理平衡二者之間的關(guān)系。以準(zhǔn)確率為代價(jià)我們得到了隨機(jī)貪心算法，以時(shí)間復(fù)雜度為代價(jià)我們得到了準(zhǔn)確率的進(jìn)一步的優(yōu)化，但不論是哪種方法，都能有效地降低了思維與編程復(fù)雜度，達(dá)到了二者之間的相對(duì)平衡。例題二、Jackpot（PKU2103）題目描述： 等概率選擇任意整數(shù)，若其能被p1,p2,p3.pn中至少一個(gè)數(shù)整除，那么稱(chēng)當(dāng)前情況為勝利局面。給定p1,p2,p3.pn，（n=16）求得到勝利局面的概率（用最簡(jiǎn)分?jǐn)?shù)表示）。初步分析： 本題看起來(lái)十分復(fù)雜。題目作為參考，給了一個(gè)比較復(fù)雜的計(jì)算概率的式子。 其中P表示最后結(jié)果的概率，是 - k 到 k 之間至少能被給定的p1,p2.pn其中一個(gè)數(shù)整除的個(gè)數(shù)。 但如果直接用這個(gè)式子比較復(fù)雜。所以我們?cè)O(shè)計(jì)了下述算法代替。注意題目中涉及高精度計(jì)算，但本題時(shí)限卡的比較緊，如果用普通的高精度容易超時(shí)，巨大的常數(shù)無(wú)法忍受。如何合理優(yōu)化常數(shù)成為了解決問(wèn)題的關(guān)鍵。解法分析： 本題其實(shí)是數(shù)學(xué)題。題目等價(jià)于求取數(shù)區(qū)間為1lcm(p1,p2,p3.)的時(shí)候的概率，但由于1 = pi = 109，使得最小公倍數(shù)可能很大，直接掃描顯然不現(xiàn)實(shí)。注意到給定的數(shù)最多只有16個(gè)，所以我們可以應(yīng)用容斥原理求出區(qū)間中可以得到勝利局面的數(shù)的個(gè)數(shù)。由于題目涉及了許多求gcd，lcm的高精度，一個(gè)小技巧是開(kāi)一個(gè)素?cái)?shù)列表，當(dāng)前狀態(tài)以紀(jì)錄素?cái)?shù)的次數(shù)的方式記錄，最后再還原成原來(lái)的整數(shù)。主算法的設(shè)計(jì)與實(shí)現(xiàn)并不困難。所以在主算法相同的情況下，高精度算法的實(shí)現(xiàn)優(yōu)劣就成了左右程序效率的關(guān)鍵。 本題涵蓋了許多的高精度算法，而幾乎每一次運(yùn)算都要使用到高精度運(yùn)算。其中使用最多的有高精度乘以單精度與高精度加減法。高精度運(yùn)算有一個(gè)通用的優(yōu)化：壓位。在longint范圍內(nèi)通常是壓4位（即萬(wàn)進(jìn)制），在int64則可以壓8位，而壓位能有效地減少高精度數(shù)組的長(zhǎng)度，從而提高效率。注意到程序?qū)崿F(xiàn)時(shí)要大量使用div與mod運(yùn)算，這兩個(gè)運(yùn)算的常數(shù)是比較大的。那么是否有辦法繞開(kāi)這兩個(gè)運(yùn)算呢？答案是肯定的。我們注意到，除法與取模的運(yùn)算是為了進(jìn)行壓位處理的操作，（注意到若是高精度乘法，中間結(jié)果可能比較大，所以用while遞減實(shí)現(xiàn)取模的效果更差）。但無(wú)論壓位與否，我們的所采用的萬(wàn)進(jìn)制等進(jìn)行壓位實(shí)質(zhì)上還是沿用著通常的十進(jìn)制的思維模式。但計(jì)算機(jī)處理二進(jìn)制運(yùn)算（位操作）顯然要比十進(jìn)制常數(shù)小。所以我們可以跳出思維慣性，采用二進(jìn)制壓位，這樣，一些取?；蛘叱ㄟ\(yùn)算就能用位操作很好地實(shí)現(xiàn)。 下面是兩個(gè)程序主要部分的偽代碼的對(duì)比。（高精度與單精度乘法）采用進(jìn)制壓位的乘法采用進(jìn)制壓位的乘法for i 1 to a0 + 1 do begin p ai * b + p div ; ai p mod ; end;for i 1 to a0 + 1 do begin p ai * b + p shr n; ai p and (-1); end; 可以發(fā)現(xiàn)，兩者的程序幾乎相同。但采用進(jìn)制壓位的乘法利用位運(yùn)算代替了運(yùn)算常數(shù)很高的div與mod，而同等情況下壓位后數(shù)組長(zhǎng)度與通常的壓位差別不大（甚至稍?xún)?yōu)），所以實(shí)際應(yīng)用時(shí)可以取得很好的效果。在本題中，筆者的程序應(yīng)用了這個(gè)方法，在1秒內(nèi)就通過(guò)了所有的數(shù)據(jù)。 當(dāng)然有得必有失。這種優(yōu)化因?yàn)椴捎眠M(jìn)制進(jìn)行壓位，但通常答案都是要求輸出10進(jìn)制的結(jié)果，所以無(wú)法類(lèi)似那樣直接輸出。在輸出時(shí)需要對(duì)其進(jìn)行高精度計(jì)算對(duì)10取模。這里就不再贅述了。小結(jié)：例題在實(shí)現(xiàn)中跳出了典型實(shí)現(xiàn)的思維框架，創(chuàng)新地使用了二進(jìn)制壓位思想。雖然修改后在最后輸出時(shí)的取模操作提高了輸出的時(shí)間復(fù)雜度，但畢竟輸出的次數(shù)通常不多，而程序中調(diào)用高精度運(yùn)算的次數(shù)卻可能很大（例如本題）。這里以提高輸出的復(fù)雜度為代價(jià)，降低了運(yùn)算的常數(shù)復(fù)雜度，實(shí)質(zhì)上是構(gòu)建了二者的算法復(fù)雜度之間的平衡，所以最后能取得相當(dāng)不錯(cuò)的效果。 經(jīng)典算法還有很多，也有一大部分無(wú)論設(shè)計(jì)與實(shí)現(xiàn)都存在一定的困難，很多細(xì)節(jié)的操作往往也能左右算法的效率。在這樣一類(lèi)問(wèn)題中，本來(lái)是簡(jiǎn)化問(wèn)題的經(jīng)典算法卻成為了程序?qū)崿F(xiàn)的障礙。根據(jù)實(shí)際需求，合理改造算法，細(xì)心設(shè)計(jì)算法細(xì)節(jié)的實(shí)現(xiàn)，有效地平衡算法中不同部分的復(fù)雜度關(guān)系，建立各部分之間的平衡，往往是解決這類(lèi)問(wèn)題的利器。2、效果優(yōu)秀的非完美算法 在信息學(xué)競(jìng)賽的賽場(chǎng)上，遇到不會(huì)做的題目對(duì)大多數(shù)人來(lái)說(shuō)是很平常的事情。但是如果就此放棄也未免太可惜了。畢竟一道題一百分往往能直接左右競(jìng)賽的結(jié)果。如果題目有部分分，又或者題目是要求我們求最優(yōu)解或者構(gòu)造最優(yōu)方案時(shí)，采用些非完美算法或者近似算法往往能收到不錯(cuò)的效果（雖然不一定能滿分）。如果類(lèi)似下文能使用DP、貪心算法構(gòu)造出“幾乎是對(duì)”的算法的話，則能為我們節(jié)省下大量的思考時(shí)間，達(dá)到了得到的分?jǐn)?shù)與所消耗時(shí)間的平衡，性?xún)r(jià)比可謂是非常高。例題三、追捕盜賊（NOI2007 Day2 catch)題目描述： Magic Land 由N 個(gè)城市，N-1 條公路彼此連接起來(lái)，任意兩個(gè)城市間都可以通過(guò)若干條公路互達(dá)。大盜Frank能夠在公路上以任意速度移動(dòng)。你的任務(wù)就是抓住大盜Frank。但是你完全不知道Frank躲在哪個(gè)城市，或者正在哪條公路上移動(dòng)，所以需要制定一個(gè)周密的抓捕計(jì)劃。每個(gè)單位時(shí)間你可以完成以下幾個(gè)操作：1、在某個(gè)城市空降一位警探。2、把留在某個(gè)城市里的一位警探直接召回指揮部。3、讓待在某個(gè)城市的一位警探沿著公路移動(dòng)到另一個(gè)城市。若警探和大盜在同一城市或者同一條公路上移動(dòng)則可以抓獲大盜。請(qǐng)你制定一個(gè)使用人數(shù)最少的捕獲計(jì)劃，并且操作次數(shù)不能超過(guò)20000。初步分析： 本題初看上去并不復(fù)雜，但卻是這次比賽最難的一道題。事實(shí)上，這是一道論文題級(jí)別的題目 本題實(shí)質(zhì)上是圖論中的“Search Number”問(wèn)題，對(duì)于一般圖，Search Number問(wèn)題是NPC的。對(duì)于樹(shù)上的特殊問(wèn)題，可以在O(N)時(shí)間內(nèi)求出Search Number，在O(NlogN)時(shí)間內(nèi)求出相應(yīng)方案。有興趣的同學(xué)可以查找相應(yīng)的資料。，涉及許多定理與推論，思維復(fù)雜度編程復(fù)雜度同時(shí)達(dá)到一定的高度。事實(shí)證明，考場(chǎng)上也沒(méi)有人想出來(lái)標(biāo)準(zhǔn)做法。但這一百分也不能扔掉?？紤]到這題的評(píng)分標(biāo)準(zhǔn)存在部分分，而且只要有一個(gè)可行解就有分，即使是簡(jiǎn)單的構(gòu)造也能拿到一定的分?jǐn)?shù)。所以各種騙分的算法蜂擁而至，也取得了一定的效果。但是這題的數(shù)據(jù)還是比較強(qiáng)大，尋常的騙分效果并不理想。于是經(jīng)過(guò)一定的思考，我們可以發(fā)現(xiàn)一種比較不錯(cuò)的替代算法。解法分析：1234 我們首先考察簡(jiǎn)單的樣例數(shù)據(jù)。 城市與城市之間的連接關(guān)系如右圖所示。一種可行解是：始終在城市2駐扎一個(gè)警探，然后在城市1降落1個(gè)警探并往城市2移動(dòng)，到達(dá)城市2后收回，并對(duì)城市3、4進(jìn)行類(lèi)似的操作。 樣例雖然簡(jiǎn)單，但給我們提供了一種非常有用的構(gòu)造思想。我們知道，樹(shù)上的任意一個(gè)點(diǎn)可以將樹(shù)拆分成若干個(gè)無(wú)關(guān)的部分。對(duì)應(yīng)于這道題目來(lái)說(shuō)，在一個(gè)點(diǎn)上常駐一個(gè)警探可以使大盜無(wú)法從被這個(gè)點(diǎn)分隔開(kāi)的一個(gè)部分進(jìn)入另一個(gè)部分。顯然，為了使我們之前的搜索過(guò)程沒(méi)有浪費(fèi)，進(jìn)行分叉的搜索時(shí)，在分割點(diǎn)上駐一個(gè)警探可以保住之前的搜索成果。 這樣，我們就可以每次選擇一個(gè)點(diǎn)將圖拆分成若干個(gè)不同的部分。每個(gè)部分就是一個(gè)縮小規(guī)模版本的題目。這不是神似我們常用的動(dòng)態(tài)規(guī)劃的解題構(gòu)造法么？根據(jù)這個(gè)思路，我們能得到一個(gè)大概的轉(zhuǎn)移方程式： 其中，表示樹(shù)的點(diǎn)集為V時(shí)候的較優(yōu)（最優(yōu)）警探放置數(shù)量，表示第i棵子樹(shù)（點(diǎn)集為）的情況。 但是子狀態(tài)的情況并不好構(gòu)造，如果構(gòu)造不當(dāng)，這樣的結(jié)果并不一定很優(yōu)。 最簡(jiǎn)單的方法，我們可以搜索每次拆分的點(diǎn)。但是這么做時(shí)間復(fù)雜度十分高，而且輸出方案、程序?qū)崿F(xiàn)也相對(duì)麻煩。同時(shí)我們考慮這樣的情況，例如一個(gè)點(diǎn)將這棵樹(shù)分成了若干個(gè)部分，如果我們搜索行動(dòng)進(jìn)行到了最后一部分時(shí)，原本駐扎的警探就可以沿路徑前進(jìn)，這樣可以節(jié)省一個(gè)駐扎在分割點(diǎn)的警探，結(jié)果通常會(huì)更優(yōu)。而且，一棵子樹(shù)的最優(yōu)解情況并不容易轉(zhuǎn)移到原樹(shù)上。對(duì)于這種方法，子樹(shù)的若干最優(yōu)解如何選擇，如何與整棵樹(shù)的解進(jìn)行銜接從而構(gòu)造最終解，如何保證正確性最優(yōu)性的兼并？這些都是我們需要考慮但又十分困難的問(wèn)題。但我們?cè)跄芫痛朔艞夁@道題？花時(shí)間考慮過(guò)于復(fù)雜的標(biāo)準(zhǔn)方法顯然不現(xiàn)實(shí)?？紤]到有部分分，我們完全可以修改上述方法使之能取得一個(gè)較優(yōu)解。 上述方法有一個(gè)重點(diǎn)是考慮將樹(shù)分解成了若干個(gè)小規(guī)模的問(wèn)題，但同時(shí)產(chǎn)生一個(gè)問(wèn)題，如何銜接子問(wèn)題與總問(wèn)題的構(gòu)造？我們不妨將初始的分割點(diǎn)作為樹(shù)的根，構(gòu)建整棵樹(shù)，子問(wèn)題的分割點(diǎn)直接設(shè)置為子樹(shù)的根。每次選取一個(gè)需求最多的子樹(shù)作為最后擴(kuò)展部分。采用這樣的思路，一個(gè)新的近似構(gòu)造方法產(chǎn)生了。 首先枚舉初始分割點(diǎn)，將初始分割點(diǎn)作為樹(shù)根建樹(shù)。對(duì)這棵樹(shù)進(jìn)行類(lèi)似樹(shù)狀動(dòng)態(tài)規(guī)劃的貪心構(gòu)造。我們有如下?tīng)顟B(tài)轉(zhuǎn)移方程。其中D(x)表示以x為根節(jié)點(diǎn)的樹(shù)的較優(yōu)（最優(yōu)）警探放置數(shù)量。sonx表示節(jié)點(diǎn)x的兒子節(jié)點(diǎn)的集合。 構(gòu)造具體解的時(shí)候，我們也完全可以按照轉(zhuǎn)移來(lái)進(jìn)行構(gòu)造。整個(gè)過(guò)程是遞歸實(shí)現(xiàn)的。將兩個(gè)警探駐扎在分割點(diǎn)上，派出一個(gè)警探移動(dòng)向分割點(diǎn)的子節(jié)點(diǎn)，然后重復(fù)上述過(guò)程，探索完畢（即警探走到了葉子節(jié)點(diǎn)）就立刻將警探回收。對(duì)每一個(gè)分割點(diǎn)，最后探索需求警探數(shù)最大的子樹(shù)，此時(shí)不用額外派遣警探，直接將分割點(diǎn)上警探移動(dòng)到子節(jié)點(diǎn)，并重復(fù)上述過(guò)程直到整棵樹(shù)探索完畢。 從實(shí)現(xiàn)方面來(lái)說(shuō)，算法的主體部分無(wú)論計(jì)算還是構(gòu)造，實(shí)現(xiàn)起來(lái)都相對(duì)比較輕松。但這個(gè)算法的最后效果如何呢？上述算法主要弱點(diǎn)在于，我們除了初始的分割點(diǎn)是枚舉的外，其余子樹(shù)初始分割點(diǎn)直接定為子樹(shù)的根。這樣做雖然使得構(gòu)造解變得輕松，但有可能使得子樹(shù)得到的解無(wú)法保證最優(yōu)，從而影響整體解的質(zhì)量。例如下圖的情況 虛線與省略號(hào)部分表示節(jié)點(diǎn)root還有不少于2個(gè)和“節(jié)點(diǎn)1所在的子樹(shù)”相同的子樹(shù)。實(shí)際上，若root節(jié)點(diǎn)只有2個(gè)“節(jié)點(diǎn)1所在的子樹(shù)”，那么這個(gè)貪心依然能得到3這個(gè)最優(yōu)解。，如果按照上述的貪心算法，我們會(huì)得到最后的答案是4，但是156893724root實(shí)際上最優(yōu)解只需要3個(gè)警探就可以了。構(gòu)造方案如下，root節(jié)點(diǎn)始終駐扎警探，分別派遣警探a，警探b到節(jié)點(diǎn)5，6，并同時(shí)往節(jié)點(diǎn)2移動(dòng)，回收警探b，讓警探a往節(jié)點(diǎn)1移動(dòng)。派遣警探b到root節(jié)點(diǎn)并順次移動(dòng)到節(jié)點(diǎn)1，4，9。回收警探b，派遣a往節(jié)點(diǎn)3移動(dòng)并派遣警探b到節(jié)點(diǎn)3，之后警探a，b分別往節(jié)點(diǎn)7，8移動(dòng)并回收。對(duì)于root的其他子樹(shù)采取類(lèi)似的操作。我們的貪心算法因?yàn)閷?duì)于子樹(shù)默認(rèn)以根節(jié)點(diǎn)作為分割點(diǎn)，所以無(wú)法得到上述的構(gòu)造方案。那么這個(gè)算法是否還有意義呢？我們注意到影響到當(dāng)前點(diǎn)解的質(zhì)量只有2個(gè)因素，即子節(jié)點(diǎn)中需求警探數(shù)最大與次大的點(diǎn)。因此，其他子節(jié)點(diǎn)的解即使稍劣也不會(huì)影響最終結(jié)果。也就是說(shuō)，實(shí)際的解給部分的解提供了一個(gè)彈性空間。同時(shí)，即使部分?jǐn)?shù)據(jù)可以克制這個(gè)算法，但由于小部分克制數(shù)據(jù)比較難以構(gòu)造（上述反例也至少需要大約30個(gè)節(jié)點(diǎn)來(lái)“配合”），隨著數(shù)據(jù)量加大，通常隨機(jī)的數(shù)據(jù)即使生成了克制數(shù)據(jù)也幾乎無(wú)法影響最后的解。而且，即使是給定順序的分割點(diǎn)，得到的解通常也是較優(yōu)解甚至最優(yōu)解。而枚舉第一個(gè)分割點(diǎn)雖然把時(shí)間復(fù)雜度提高到了O(N2)，但時(shí)間方面依然很寬裕，解的質(zhì)量卻有效地提高了。筆者使用這個(gè)方法測(cè)試了1000組隨機(jī)數(shù)據(jù)，結(jié)果表明，有百分之八十五左右的計(jì)算結(jié)果只需要5個(gè)警探，其余都是6個(gè)警探（極偶然出現(xiàn)過(guò)只需4個(gè)警探的情況）。對(duì)照得分規(guī)則，可以發(fā)現(xiàn)這樣至少能獲得60%的分?jǐn)?shù)。（2個(gè)以下警探肯定能正確出解）。實(shí)踐證明，這種方法對(duì)于考場(chǎng)的數(shù)據(jù)可以拿到96分的好成績(jī)，只有一個(gè)數(shù)據(jù)點(diǎn)結(jié)果會(huì)比標(biāo)準(zhǔn)答案大1。小結(jié)： 雖然沒(méi)有AC掉這道題，但對(duì)于實(shí)質(zhì)上屬于論文難度級(jí)別的這道題，考場(chǎng)上能夠做到96分已經(jīng)足夠了?？紤]到這種構(gòu)造法思維復(fù)雜度較低，實(shí)現(xiàn)起來(lái)十分輕松，時(shí)間復(fù)雜度中規(guī)中矩，時(shí)限范圍內(nèi)足夠出解，而且解的質(zhì)量相對(duì)較高?？紙?chǎng)上，這樣的程序能為我們省下大量的時(shí)間去解決其它問(wèn)題。在這道題目中，我們用解的質(zhì)量為代價(jià)，極大地降低了程序思維復(fù)雜度與實(shí)現(xiàn)方面的難度，同時(shí)在基礎(chǔ)的方案上，我們合理優(yōu)化構(gòu)造的方法，使得解的質(zhì)量通?？梢赃_(dá)到最優(yōu)。 在這一類(lèi)問(wèn)題中，原本復(fù)雜的問(wèn)題我們無(wú)法解決，一味追求AC往往得不償失，而選擇一些效果不錯(cuò)的近似算法就有著較高的性?xún)r(jià)比。這樣實(shí)質(zhì)上是通過(guò)些另類(lèi)的途徑，有效地建立了所得分?jǐn)?shù)與所耗時(shí)間的平衡，以少量的代價(jià)取得了優(yōu)秀的效果，也不失為一種優(yōu)秀的解題策略。3、復(fù)雜問(wèn)題的簡(jiǎn)單化構(gòu)造當(dāng)然，并不是每一道題都能夠找到第二類(lèi)問(wèn)題那樣的效果優(yōu)秀的近似算法。而且如果是形如ACM之類(lèi)的比賽，或者題目要求維護(hù)一系列操作時(shí)，近似算法的作用往往會(huì)被限制。此時(shí)，我們即使無(wú)法找到時(shí)空效率十分優(yōu)美的算法，也需要沉著下來(lái)，仔細(xì)分析題目特征。一類(lèi)常常使用的方法就是，在可行的時(shí)空限制下，以時(shí)空效率為代價(jià)，降低思維復(fù)雜度，建立時(shí)空復(fù)雜度與思考實(shí)現(xiàn)復(fù)雜度的平衡，這就是復(fù)雜問(wèn)題的簡(jiǎn)單化構(gòu)造。 這類(lèi)問(wèn)題通常有一個(gè)特征。如果題目所給的條件再?gòu)?qiáng)大一些，把可能涉及的情況限制成某些特例時(shí)，我們能找到優(yōu)秀的算法，但擴(kuò)展之后卻不能通用。如何有效應(yīng)用特例提供的信息來(lái)簡(jiǎn)化模型，進(jìn)一步地建立特例與一般的平衡，往往是解決問(wèn)題的關(guān)鍵。例題四、數(shù)列維護(hù)題目描述： 給一個(gè)長(zhǎng)度為n(n=100000)的整數(shù)數(shù)列，要求維護(hù)以下幾個(gè)操作。 1、數(shù)列第i項(xiàng)到第j項(xiàng)同時(shí)加上一個(gè)整數(shù)。 2、詢(xún)問(wèn)第i項(xiàng)到第j項(xiàng)中比整數(shù)c小的數(shù)有多少個(gè)。 最大操作數(shù)不超過(guò)10000。初步分析：本題要求我們應(yīng)用數(shù)據(jù)結(jié)構(gòu)維護(hù)關(guān)于序列區(qū)間的一些操作。由于同時(shí)涉及區(qū)間的比大小，詢(xún)問(wèn)，增減操作，我們的第一反應(yīng)通常是用樹(shù)套樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)解決這樣的問(wèn)題。但注意到題目中有變換區(qū)間序列的操作，簡(jiǎn)單地套用模型會(huì)使得區(qū)間合并的時(shí)候時(shí)間復(fù)雜度并不理想。再者，樹(shù)套樹(shù)有著復(fù)雜的代碼量，調(diào)試起來(lái)也并不容易，如果不小心就可能造成巨大的損失。注意到題目中最大操作數(shù)僅10000，時(shí)限方面也并不緊張（5s），我們可以放棄樹(shù)套樹(shù)的思想，考慮采用實(shí)現(xiàn)簡(jiǎn)單、代碼量低、調(diào)試方便的算法來(lái)代替。解法分析： 對(duì)于區(qū)間操作，還有一種數(shù)據(jù)結(jié)構(gòu)也常常為我們所用，那就是塊狀鏈表。不過(guò)，直接寫(xiě)普通的塊狀鏈表復(fù)雜度是，但代碼量依然巨大。但塊狀鏈表的思想可以為我們所用。我們注意到，題目中的區(qū)間操作僅局限于區(qū)間增減或者詢(xún)問(wèn)，并不會(huì)打亂數(shù)列的順序，所以，我們不妨稍微改造下塊狀鏈表塊狀數(shù)組。 塊狀數(shù)組是這樣的一個(gè)數(shù)組，它直接對(duì)原數(shù)組進(jìn)行劃分，分為個(gè)部分，每個(gè)部分長(zhǎng)度為，每個(gè)部分開(kāi)相應(yīng)的域以記錄類(lèi)似增減的操作信息（當(dāng)然也可以是一些統(tǒng)計(jì)的信息，但這不在本題考慮范圍之內(nèi)）。這樣的結(jié)構(gòu)實(shí)現(xiàn)起來(lái)十分簡(jiǎn)單（使用原數(shù)組即可），適合的操作包括一些區(qū)間大小詢(xún)問(wèn)，區(qū)間增減操作，但不支持區(qū)間插入刪除操作，原因是塊狀數(shù)組適合這樣的序列操作，序列項(xiàng)與項(xiàng)之間隱含著嚴(yán)格不變的次序關(guān)系。但本題所要求的操作正好能滿足這個(gè)條件。 在這道題目中，我們需要維護(hù)的操作有兩個(gè)：區(qū)間增減操作，區(qū)間詢(xún)問(wèn)操作。注意到增減操作時(shí)，如果完全覆蓋了一個(gè)劃分區(qū)間，那么這個(gè)操作就不會(huì)影響這個(gè)劃分區(qū)間中數(shù)的大小關(guān)系。也就是說(shuō)，對(duì)于一個(gè)區(qū)間增減操作，我們至多只需要更新“操作區(qū)間”的頭尾所在的劃分區(qū)間的序列關(guān)系。而值得注意的是，如果我們能保證時(shí)時(shí)維護(hù)劃分區(qū)間使之有序，那么區(qū)間詢(xún)問(wèn)操作就可以應(yīng)用二分法輕松完成?；谏鲜鏊枷?，我們可以設(shè)計(jì)出如下在線算法。 設(shè)數(shù)組A為原數(shù)組，令數(shù)組。預(yù)處理為：將數(shù)組B劃分為塊，每塊長(zhǎng)度為（塊狀數(shù)組）。對(duì)于數(shù)組B的每個(gè)部分，應(yīng)用快速排序?qū)⑵浒磸男〉酱笈判?，并開(kāi)額外的域來(lái)記錄區(qū)間增減情況。初始時(shí)所有額外域的數(shù)值為0。 對(duì)于操作1（數(shù)列第i項(xiàng)到第j項(xiàng)同時(shí)加上一個(gè)整數(shù)），用常數(shù)時(shí)間求出操作區(qū)間的連續(xù)部分。對(duì)于完全被操作區(qū)間覆蓋的部分，只需修改相應(yīng)的標(biāo)記域值即可。對(duì)于未被完全覆蓋的部分（只可能是頭尾，最多兩個(gè)部分），直接對(duì)該部分內(nèi)相應(yīng)數(shù)值進(jìn)行修改。最多修改個(gè)區(qū)間，頭尾區(qū)間最多修改個(gè)數(shù)值，修改后重排序代價(jià)為，所以該操作最壞情況下復(fù)雜度為。 對(duì)于操作2（詢(xún)問(wèn)第i項(xiàng)到第j項(xiàng)中比整數(shù)c小的數(shù)有多少個(gè)），方法是類(lèi)似的。首先用常數(shù)時(shí)間求出操作區(qū)間的連續(xù)部分，對(duì)于完全被操作區(qū)間覆蓋的部分。因?yàn)槠渲惺怯行虻?，可以使用二分法求出比c小的數(shù)的個(gè)數(shù)。對(duì)于頭尾所在的兩個(gè)區(qū)間，只需直接掃描一遍并統(tǒng)計(jì)即可。這樣最多訪問(wèn)個(gè)區(qū)間，每個(gè)區(qū)間詢(xún)問(wèn)復(fù)雜度為，頭尾區(qū)間最多掃描個(gè)數(shù)值，所以總的時(shí)間復(fù)雜度最壞為。 綜上所述，總共m個(gè)操作，時(shí)間復(fù)雜度最壞為，最壞情況復(fù)雜度在千萬(wàn)級(jí)別，足夠通過(guò)所有數(shù)據(jù)。小結(jié)：實(shí)際上，本題雖然有采用樹(shù)套樹(shù)，時(shí)間復(fù)雜度為的算法，但其思維復(fù)雜度比較高，實(shí)現(xiàn)也并不容易?？紤]到題目的特殊性，我們可以發(fā)現(xiàn)序列中隱含的不變的次序關(guān)系，并根據(jù)數(shù)據(jù)范圍和時(shí)限選擇合適的算法。本題中，我們并沒(méi)有硬性追求時(shí)間復(fù)雜度十分優(yōu)美的算法。由于題設(shè)對(duì)操作的限制，使得我們能通過(guò)改造經(jīng)典數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方法，有效地降低了思維與編程復(fù)雜度，還在一定程度上優(yōu)化了常數(shù)。這實(shí)質(zhì)上正是在時(shí)間復(fù)雜度與思維復(fù)雜度之間找到了一個(gè)平衡點(diǎn)，并借此有效地解決了問(wèn)題。例題五、樹(shù)的維護(hù)(PKU 3237)題目描述： 給定一棵有N個(gè)節(jié)點(diǎn)的樹(shù)，點(diǎn)編號(hào)為1N，邊按給定順序編號(hào)為1N-1，每一條邊有一個(gè)邊權(quán)。需要對(duì)這棵樹(shù)維護(hù)三個(gè)操作： 1、將某一條邊的權(quán)值修改為V。 2、將點(diǎn)A到B的路徑上的邊權(quán)值取負(fù)號(hào)。 3、詢(xún)問(wèn)點(diǎn)A到B的路徑上的權(quán)值最大值。 數(shù)據(jù)組數(shù)不超過(guò)20，點(diǎn)的個(gè)數(shù)不超過(guò)10000。初步分析： 本題主要是對(duì)樹(shù)上的路徑進(jìn)行操作，這類(lèi)問(wèn)題我們往往可以采用動(dòng)態(tài)樹(shù)來(lái)解決。并且對(duì)于這道題，動(dòng)態(tài)樹(shù)有“看著十分舒服”的對(duì)數(shù)級(jí)別復(fù)雜度。但問(wèn)題并沒(méi)有解決。首先，對(duì)這題使用動(dòng)態(tài)樹(shù)有種“大材小用”的感覺(jué)，因?yàn)閯?dòng)態(tài)樹(shù)功能最強(qiáng)大的地方在于它能維護(hù)一棵不斷改變形狀的樹(shù)，但本題中樹(shù)的形狀是固定的。其次，動(dòng)態(tài)樹(shù)實(shí)現(xiàn)起來(lái)比較復(fù)雜，巨大的常系數(shù)也不得不為我們所考慮。所以，我們嘗試考慮一些其他算法來(lái)代替動(dòng)態(tài)樹(shù)，以便更有效地解決這個(gè)問(wèn)題。解法分析： 我們不妨先考慮題目的一種特例情況，即樹(shù)退化成了一條鏈的情況。這個(gè)問(wèn)題便是我們常常見(jiàn)到一類(lèi)應(yīng)用線段樹(shù)解決的問(wèn)題。那么是否能將一條鏈推廣成樹(shù)的情況呢？ 筆者首先考慮的情況，是將樹(shù)按照某種規(guī)則（例如深搜序）進(jìn)行遍歷，將遍歷時(shí)產(chǎn)生的訪問(wèn)序列當(dāng)成一條鏈的情況來(lái)處理。遺憾的是，經(jīng)過(guò)若干次嘗試后，發(fā)現(xiàn)情況并沒(méi)有想象中那么簡(jiǎn)單，故放棄了這種想法。 但上述想法也并非一無(wú)是處。其實(shí)上述想法的主要目的是將樹(shù)的情況轉(zhuǎn)化成鏈的情況。既然轉(zhuǎn)化不成功，不如直接把樹(shù)拆成一條一條的鏈來(lái)做。于是，下述算法產(chǎn)生了。首先我們?nèi)芜x一點(diǎn)為根構(gòu)建整棵樹(shù)，并將每條邊的權(quán)值下放到邊連接的兩點(diǎn)中的兒子節(jié)點(diǎn)上。（整棵樹(shù)的根取值可以定為任意值，因?yàn)椴⒉挥绊懭魏尾僮鳎?duì)于任意一個(gè)節(jié)點(diǎn)x，假設(shè)它的兒子們都屬于一條自底向上，并且以自己為結(jié)尾的鏈上，那么我們選擇其中最長(zhǎng)的一條鏈連到x上。這樣樹(shù)上的所有點(diǎn)都屬于不同的鏈上（有些鏈只有一個(gè)節(jié)點(diǎn)），我們稱(chēng)這些鏈為拆分鏈。注意之前對(duì)邊下放權(quán)值的好處這里就體現(xiàn)出來(lái)了鏈與鏈之間斷開(kāi)的邊不用作為單獨(dú)的邊而特殊考慮了。827136945例如右圖的情況，我們就將這棵樹(shù)拆成了如下5條拆分鏈（圖中用粗線表示拆分鏈的邊）：，4，5，8。對(duì)于每條鏈，建立一棵線段樹(shù)，由于取負(fù)操作的存在，需要同時(shí)維護(hù)這條鏈中的最大邊與最小邊。鏈與鏈的拆分關(guān)系可以用并查集存儲(chǔ)。 對(duì)于操作1，直接修改存儲(chǔ)該邊權(quán)值的點(diǎn)的權(quán)值，并維護(hù)該點(diǎn)所在線段樹(shù)中的最大值與最小值。復(fù)雜度為。顯然m的最大值為n。 對(duì)于操作2，我們先求出點(diǎn)A與B的最近公共祖先root，然后分別對(duì)A到root，B到root的兩條鏈進(jìn)行操作。每次操作就是依次訪問(wèn)他們之間的拆分鏈，在相應(yīng)的線段樹(shù)上進(jìn)行取負(fù)操作。 對(duì)于操作3，類(lèi)似操作2，求出A與B的最近公共祖先root，分別求出A到root，B到root的兩條路徑的結(jié)果，取較大的輸出。每次操作依然是依次查找當(dāng)前路徑所在的拆分鏈，然后對(duì)這一段在這條鏈的線段樹(shù)上進(jìn)行詢(xún)問(wèn)操作。 以上所有關(guān)于最近公共祖先，路徑與拆分鏈的查找，都可以在常數(shù)時(shí)間內(nèi)完成。所以這個(gè)算法復(fù)雜度的瓶頸就在于，操作2與操作3中最多可能訪問(wèn)的樹(shù)的拆分鏈的個(gè)數(shù)。從直觀感覺(jué)上來(lái)說(shuō)，我們的拆鏈方法對(duì)于普通的數(shù)據(jù)，都能使得很多的路徑基本落在拆分鏈上，所以這個(gè)數(shù)通常并不會(huì)很大。但這樣總是不夠保險(xiǎn)。實(shí)際上，我們也可以估算出，操作2與操作3的復(fù)雜度最多不超過(guò)。 引理按照以上貪心思想對(duì)任意一棵n個(gè)節(jié)點(diǎn)的樹(shù)進(jìn)行拆鏈，任意點(diǎn)x到其任意祖先root之間的拆分鏈數(shù)目不超過(guò)條。 證明定義一個(gè)集合S，它的元素是x到root之間所有的邊。設(shè)S中的邊屬于k條拆分鏈，這些拆分鏈與路徑公共部分的最上層節(jié)點(diǎn)為，其中。那么必然連接著另外一條向下走的拆分鏈，這條拆分鏈除去屬于S的部分至少還有1個(gè)點(diǎn)；同時(shí)也必然連接著另外一條向下走的拆分鏈，這條拆分鏈除去屬于S的部分至少還有2個(gè)點(diǎn)；同理連接的向下走的拆分鏈除去屬于S的部分至少還有k-1個(gè)點(diǎn)。這樣以root為根的子樹(shù)至少要有個(gè)點(diǎn)。顯然最大為n，這時(shí)。引理得證。 定理理論上操作2與操作3的時(shí)間復(fù)雜度最壞為。證明根據(jù)引理，我們知道每次操作2與操作3最多訪問(wèn)條拆分鏈，而每次訪問(wèn)拆分鏈需要維護(hù)拆分鏈對(duì)應(yīng)的線段樹(shù)，維護(hù)的復(fù)雜度為，其中m最多不超過(guò)n。所以操作2與操作3的時(shí)間復(fù)雜度最壞為。 以上我們證明了操作2與操作3的復(fù)雜度最多不超過(guò)。從而對(duì)于一組數(shù)據(jù)，整個(gè)算法的時(shí)間復(fù)雜度為，看起來(lái)時(shí)限有些吃緊。但實(shí)際上這個(gè)上限是一個(gè)十分寬松的上限，而且程序?qū)崿F(xiàn)的常數(shù)比較低，所以運(yùn)行起來(lái)效果相當(dāng)不錯(cuò)。PKU上，筆者的程序用了951MS就通過(guò)了所有的數(shù)據(jù)。小結(jié)：本題中，我們放棄了看上去十分優(yōu)美的對(duì)數(shù)復(fù)雜度的動(dòng)態(tài)樹(shù)(復(fù)雜度為)，轉(zhuǎn)而通過(guò)對(duì)樹(shù)的拆鏈操作來(lái)完成題目要求的操作。我們通過(guò)對(duì)特例情況的考慮，尋找到了最后的解法，這實(shí)際上是建立了特例與推廣的平衡，從而有效地解決了這個(gè)問(wèn)題。雖然我們估計(jì)的最壞復(fù)雜度比較龐大，但是實(shí)際運(yùn)行效果相當(dāng)優(yōu)秀，而且程序?qū)崿F(xiàn)方面也相對(duì)簡(jiǎn)單。雖然沒(méi)有精細(xì)地計(jì)算出時(shí)間復(fù)雜度的上限，但這并不妨礙這個(gè)算法的實(shí)用價(jià)值。 實(shí)際上，ural某次比賽中也曾出現(xiàn)過(guò)這題（ural1553)，在比賽中，筆者也正是用這種方法第一個(gè)AC此題，也正說(shuō)明這種方法是行之有效的。3、 總結(jié)我們知道有一個(gè)經(jīng)典的木桶：一個(gè)木桶由許多塊木板組成，如果組成木桶的這些木板長(zhǎng)短不一，那么這個(gè)木桶的最大容量不取決于長(zhǎng)的木板，而取決于最短的那塊木板。如果把時(shí)間復(fù)雜度，空間復(fù)雜度等都看作是解決問(wèn)題這個(gè)木桶的一個(gè)木板，那么我們常常忽略的便是思維與實(shí)現(xiàn)復(fù)雜度這塊木板。為了增加容量，不妨截取較長(zhǎng)的木板來(lái)拼接到短的木板上，所有木板長(zhǎng)度相同時(shí)容量也達(dá)到了最大。平衡思想正是這樣一種取長(zhǎng)補(bǔ)短的思想。 應(yīng)用平衡思想解決的問(wèn)題有一個(gè)特征：存在瓶頸。這瓶頸通常是阻礙我們解決問(wèn)題的主要障礙。本文就對(duì)可應(yīng)用于這類(lèi)的平衡思想作了一定的介紹，同時(shí)較深入地討論了一類(lèi)以其他方面為代價(jià)，降低問(wèn)題的思維復(fù)雜度與程序的實(shí)現(xiàn)復(fù)雜度的模型。通過(guò)構(gòu)建各方面復(fù)雜度的平衡，我們能有效地在有限的時(shí)間里盡可能多地解決問(wèn)題。賽場(chǎng)上，我們不必追求最完美的時(shí)空復(fù)雜度，因?yàn)楦叻植攀怯驳览?，AC才是硬道理！ 外在看來(lái)，平衡規(guī)劃更像是一種“騙分”思想。但筆者認(rèn)為，解決信息學(xué)問(wèn)題并不能只是單純追求時(shí)間復(fù)雜度的完美，在有限的時(shí)間內(nèi)要綜合考慮各方面因素所帶來(lái)的問(wèn)題，這也正是信息學(xué)競(jìng)賽的魅力所在。合理應(yīng)用我們所學(xué)的知識(shí)并將他們有效結(jié)合，合理決策對(duì)問(wèn)題的數(shù)學(xué)模型，算法各方面（包括設(shè)計(jì)，實(shí)現(xiàn)）的精力分配，才能有效地解決問(wèn)題。當(dāng)然，即使如此，也需要我們有扎實(shí)的基本功，才能在賽場(chǎng)上能有更多的選擇。而且這類(lèi)思想需要我們不斷地練習(xí)才能較好地掌握，實(shí)踐才是感悟這一類(lèi)問(wèn)題最有效的途徑。畢竟，紙上得來(lái)終覺(jué)淺, 絕知此事要躬行。4、 感謝感謝 陳丹琦 同學(xué) 提供部分資料并對(duì)本文的實(shí)現(xiàn)與修改提出建議；感謝 董華星 同學(xué) 為本文的修改提出建議；感謝 劉 弈 同學(xué) 為本文的修改提出建議；感謝 劉汝佳 教練 對(duì)本文的實(shí)現(xiàn)與修改提出建議；感謝 陳 光 老師 為本文的修改提出建議；感謝 胡山立 老師 為本文的修改提出建議。5、 參考文獻(xiàn)1算法藝術(shù)與信息學(xué)競(jìng)賽 劉汝佳 黃亮 著2解題報(bào)告 周戈林3Catch題目分析 許智磊6、 附錄例一的原題：ural1099. Work schedulingThere is certain amount of night guards that are available to protect the local junkyard from possible junk robberies. These guards need to scheduled in pairs, so that each pair guards at different night. The junkyard CEO ordered you to write a program which given the guards characteristics determines the maximum amount of scheduled guards (the rest will be fired). Please note that each guard can be scheduled with only one of his colleagues and no guard can work alone. InputThe first line of input contains one number N 222 this is the amount of night guards. Unlimited number of lines consisting of unordered pairs (i, j) follow, each such pair means that guard #i and guard #j can work together, because it is possible to find uniforms that suit both of them (The junkyard uses different parts of uniforms for different guards i.e. helmets, pants, jackets. It is impossible to put small helmet on a guard with a big head or big shoes on guard with small feet). The input ends with Eof.OutputYou should output one possible optimal assignment. On the first line of the output write the even number C the amount of scheduled guards. Then output C/2 lines, each containing 2 integers (i, j) that denote that i and j will work together.SampleInputOutput31 22 31 321 2Problem Author: Jivko Ganev例二的原題：PKU2103 JackpotDescriptionThe Great Dodgers company has recently developed a brand-new playing machine. You put a coin into the machine and pull the handle. After that it chooses some integer number. If the chosen number is zero you win a jackpot. In the other case the machine tries to divide the chosen number by the lucky numbers p1 , p2 , . . . , pn . If at least one of the remainders is zero - you win. Great Dodgers want to calculate the probability of winning on their machine. They tried to do it, but failed. So Great Dodgers hired you to write a program that calculates the corresponding probability. Unfortunately, probability theory does not allow you to assume that all integer numbers have equal probability. But one mathematician hinted you that the required probability can be approximated as the following limit: Here Sk is the number of integers between -k and k that are divisible by at least one of the lucky numbers.InputInput file contains n - the number of lucky numbers (1 = n = 16), followed by n lucky numbers (1 = pi = 109 ).OutputIt is clear that the requested probability is rational. Output it as an irreducible fraction. On the first line of the output file print the numerator of the winning probability. On the second line print its denominator. Both numerator and denominator must be printed without leading zeroes. Remember that the fraction must be irreducible. SampleInputoutput24 613SourceNortheastern Europe 2004, Northern Subregion例三的原題：追捕盜賊問(wèn)題描述 魔法國(guó)度Magic Land 里最近出現(xiàn)了一個(gè)大盜Frank，他在Magic Land 四處作案，專(zhuān)門(mén)竊取政府機(jī)關(guān)的機(jī)密文件（因而有人懷疑Frank 是敵國(guó)派來(lái)的間諜）。為了捉住Frank，Magic Land 的安全局重拳出擊！ Magic Land 由N 個(gè)城市組成，并且這N 個(gè)城市又由恰好N-1 條公路彼此連接起來(lái)，使得任意兩個(gè)城市間都可以通過(guò)若干條公路互達(dá)。從數(shù)據(jù)結(jié)構(gòu)的角度我們也可以說(shuō)，這N 個(gè)城市和N-1 條公路形成了一棵樹(shù)。 例如，下圖就是Magic Land 的一個(gè)可能格局（4 個(gè)城市用數(shù)字編號(hào)，3 條公路用字母編號(hào)）： 大盜Frank 能夠在公路上以任意速度移動(dòng)。 比方說(shuō)，對(duì)于上圖給出的格局，在0.00001 秒鐘內(nèi)（或者任意短的一段時(shí)間內(nèi)），F(xiàn)rank 就可以從城市1 經(jīng)過(guò)城市2 到達(dá)城市4，中間經(jīng)過(guò)了兩條公路。 想要生擒Frank 困難重重，所以