平衡規(guī)劃淺析一類平衡思想在信息學(xué)競(jìng)賽中的應(yīng)用【目錄】摘要2關(guān)鍵字2正文2引言2應(yīng)用平衡思想的幾類問題3經(jīng)典算法的非典型實(shí)現(xiàn)3例題一、警衛(wèi)安排問題3例題二、JACKPOT6效果優(yōu)秀的非完美算法8例題三、追捕盜賊8復(fù)雜問題的簡(jiǎn)單化構(gòu)造12例題四、數(shù)列維護(hù)12例題五、樹的維護(hù)14總結(jié)17感謝18參考文獻(xiàn)18附錄18【摘要】應(yīng)用計(jì)算機(jī)解題的核心是算法設(shè)計(jì)。但算法設(shè)計(jì)方面涉及的領(lǐng)域十分豐富。我們不能奢求能完美地應(yīng)用所有的算法，所以我們關(guān)注的通常是如何合理運(yùn)用已學(xué)知識(shí)，并在所掌握算法間構(gòu)建一種平衡，在限定的時(shí)間內(nè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、博弈問題。有許多博弈類問題都可以轉(zhuǎn)化成尋找平衡點(diǎn)的問題。2、數(shù)據(jù)結(jié)構(gòu)的構(gòu)建。每種數(shù)據(jù)結(jié)構(gòu)都能以優(yōu)秀的性能支持某些操作，合理選擇應(yīng)用數(shù)據(jù)結(jié)構(gòu)，往往能通過略微提高一些操作的復(fù)雜度，降低大多數(shù)操作的復(fù)雜度，在不同操作的效率之間構(gòu)建一種平衡，以達(dá)到優(yōu)化的目的。3、時(shí)間效率VS空間效率。這類問題是我們經(jīng)常遇到的問題。這類問題通常有這樣的特性，我們能找到時(shí)間效率（或空間效率）十分優(yōu)秀的算法，但代價(jià)是空間效率（或時(shí)間效率）極端低下。如何合理設(shè)計(jì)算法，組織數(shù)據(jù)，平衡二者的關(guān)系是解決這類問題的重點(diǎn)。4、時(shí)空效率VS其他。如果面對(duì)難題難以設(shè)計(jì)出優(yōu)美的算法，又或者設(shè)計(jì)了優(yōu)秀效率的算法，卻無法實(shí)現(xiàn)或難以實(shí)現(xiàn)，就會(huì)出現(xiàn)非常尷尬的局面。合理應(yīng)用平衡規(guī)劃解決這類問題，往往能收到意想不到的效果。而這類問題也正是本文所要重點(diǎn)探討的問題。下文將試圖論述運(yùn)用平衡思想解決這類問題中的三種常見模式經(jīng)典算法的非典型實(shí)現(xiàn)，效果優(yōu)秀的非完美算法，以及復(fù)雜問題的簡(jiǎn)單化構(gòu)造。2、應(yīng)用平衡思想的幾類問題1、經(jīng)典算法的非典型實(shí)現(xiàn)。大多數(shù)經(jīng)典算法通常是為很多人所熟知，并且能夠熟悉運(yùn)用。經(jīng)典算法通常也有很多不同的實(shí)現(xiàn)方法。例如拓?fù)渑判?，如果?shù)據(jù)范圍比較大，通常使用算法復(fù)雜度為ON的程序，但是如果范圍比較小，一個(gè)不超過10行的的2NO程序可以使代碼看起來更為簡(jiǎn)潔。而不同的實(shí)現(xiàn)方法中，哪怕只是細(xì)微的不同，實(shí)現(xiàn)后的性能與效率也可能有很大的差別。更進(jìn)一步，有些算法雖然堪稱經(jīng)典，但是無論是思考復(fù)雜度還是實(shí)現(xiàn)復(fù)雜度都相對(duì)頗高，在考場(chǎng)上來說，使用一些相對(duì)簡(jiǎn)單實(shí)用的方法無疑是一種不錯(cuò)的選擇。例題一、警衛(wèi)安排問題URAL1099題目描述給定若干警衛(wèi)間搭檔關(guān)系，要求成對(duì)給警衛(wèi)安排保衛(wèi)工作，求能夠安排警衛(wèi)的最大值。（警衛(wèi)人數(shù)不超過222）初步分析題目描述很簡(jiǎn)單，稍加分析后我們很容易看出來，這題的本質(zhì)其實(shí)是要求我們求出任意圖的最大匹配。任意圖的最大匹配的經(jīng)典算法是應(yīng)用帶花匈牙利樹，時(shí)間復(fù)雜度為，3NO對(duì)付這道題來說是綽綽有余的。但是帶花樹本身比較復(fù)雜，思維復(fù)雜度與編程復(fù)雜度較高，而且實(shí)現(xiàn)起來很容易退化，考場(chǎng)上有限的時(shí)間內(nèi)難以完成。于是我們嘗試考慮替代算法予以解決。解法分析34521678圖一解決二分圖最大匹配的時(shí)候，主要過程是不斷尋找交錯(cuò)增廣樹來調(diào)整。那么這么做對(duì)于任意圖是否可行答案是否定的?？疾煊疫呥@張圖（圖一）。圖中粗線表示當(dāng)前狀態(tài)下已匹配邊，虛線表示未匹配邊。若我們當(dāng)前找的增廣樹如圖二所示，那么我們就無法找到一條增廣路。但實(shí)際上，存這樣的一條增廣路。為了876321找到增廣路，我們可以采用搜索的方法，但這樣尋找增廣路復(fù)雜度過高。我們注意到，采用調(diào)整增廣軌的方法，如果一個(gè)點(diǎn)之前已經(jīng)被匹配到，則之后無論如何調(diào)整，這個(gè)點(diǎn)始終能被匹配到。因此，對(duì)于一個(gè)待匹配點(diǎn)，是否能找到一條以它為起點(diǎn)的增廣路是優(yōu)化解的關(guān)鍵。而是否能找到一棵增廣樹又很大程度上依賴于之前找尋的情況，若要設(shè)計(jì)數(shù)據(jù)使得無法找到增廣樹通常又依賴于特定的擴(kuò)展順序。這啟發(fā)我們采用隨機(jī)擴(kuò)展順序的方法來盡量避免形成類似圖一的特殊局面。筆者的程序中生成了兩個(gè)隨機(jī)序列，一個(gè)作為點(diǎn)的初次訪問序，一個(gè)作為點(diǎn)的拓展順序，然后直接使用一開始所說的尋找交錯(cuò)樹的方法來擴(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ù)還是比較大，說明算法本身具有比較大的不確定因素，以及出最優(yōu)解概率并不是很高。所以我們需要進(jìn)一步優(yōu)化以提高一次運(yùn)行的最優(yōu)解出現(xiàn)概率。進(jìn)一步優(yōu)化上述解法中曾提到，采用調(diào)整增廣軌的方法，如果一個(gè)點(diǎn)之前已經(jīng)被匹配到，則之后無論如何調(diào)整，這個(gè)點(diǎn)始終能被匹配到。它帶來的另一個(gè)信息是，若一個(gè)點(diǎn)之前未被匹配到，那么在本輪搜索中，這個(gè)點(diǎn)最終將很可能保持未匹配的狀態(tài)。因此影響最終結(jié)果的，往往是某個(gè)本應(yīng)該被匹配到的點(diǎn)因?yàn)橹霸?452167圖二廣樹的查找失敗而被放棄匹配。初始算法解決這個(gè)問題的方法是全局重新搜索，所以常常出現(xiàn)為了一個(gè)點(diǎn)而全部重來的尷尬場(chǎng)面。其實(shí)這是舍近求遠(yuǎn)。我們完全可以換一個(gè)擴(kuò)展順序，對(duì)于當(dāng)前未找到交錯(cuò)樹從而無法匹配的點(diǎn)，直接重新搜索一棵交錯(cuò)樹當(dāng)然大部分的圖都無法實(shí)現(xiàn)完美匹配，所以類似運(yùn)行次數(shù)的限制，我們需要設(shè)置一個(gè)失敗次數(shù)上限。當(dāng)為一個(gè)未匹配點(diǎn)尋找匹配點(diǎn)時(shí)，只有失敗次數(shù)超過了這個(gè)上限才放棄。那么失敗上限次數(shù)應(yīng)該設(shè)置為多少比較好進(jìn)一步的，這個(gè)方法實(shí)現(xiàn)起來究竟效果如何呢為此筆者進(jìn)行了一系列的實(shí)驗(yàn)，得到了如下的實(shí)驗(yàn)數(shù)據(jù)表運(yùn)行次數(shù)失敗上限5551010110102012010501ACCEPTED90100090600100WRONGANSWER100100104000TIMELIMITEXCEEDED000001000平均AC時(shí)間0076101471029600038500795實(shí)驗(yàn)的運(yùn)行平臺(tái)是URAL1099的測(cè)試，時(shí)限是05秒。表頭的NM表示程序?qū)⒅貜?fù)運(yùn)行N次，失敗上限設(shè)置為M，例如55表示程序?qū)⒅貜?fù)運(yùn)行5次，失敗上限設(shè)置為5。實(shí)驗(yàn)表明，這個(gè)方法能顯著地提高一次運(yùn)行的最優(yōu)解出現(xiàn)概率。從表中數(shù)據(jù)可以看出，初始算法直到201才有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)了如表中510是100AC但是1010卻只有90的AC率的情況。但正所謂有得必有失。優(yōu)化后的方法有著極高的準(zhǔn)確率，但同時(shí)時(shí)間效率并不高。實(shí)驗(yàn)中，55的時(shí)間已經(jīng)逼近了501的時(shí)間。雖然相對(duì)于時(shí)限來說還是比較輕松，但是其增長(zhǎng)還是較可觀的（2010的全部超時(shí)就可以說明這一點(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í)際算法的需求來進(jìn)行選擇。進(jìn)一步擴(kuò)展隨機(jī)搜索序和設(shè)置失敗上限的作用并不局限于此。對(duì)于隨機(jī)搜索序，表面上看是根據(jù)克制數(shù)據(jù)或克制情況的順序依賴性1，應(yīng)用隨機(jī)的順序來進(jìn)行回避。其實(shí)其本質(zhì)是通過設(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ī)算法不可避免還是有可能無法得到我們理想的狀態(tài)或結(jié)果（例如本題依然可能找不到存在的增廣路，又例如TREAP并不完全平衡）。隨機(jī)搜索序通常是全局重新運(yùn)行來提高最優(yōu)解的出現(xiàn)概率，而設(shè)置失敗上限則是通過對(duì)于局部問題的精益求精來強(qiáng)化全局目標(biāo)情況出現(xiàn)概率，常見的應(yīng)用有大素?cái)?shù)的測(cè)試等。小結(jié)對(duì)于這道題，兩種方法都可以比較輕松地通過?？紤]到數(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,P3PN中至少一個(gè)數(shù)整除，那么稱當(dāng)前情況為勝利局面。給定P1,P2,P3PN，（N解題報(bào)告周戈林3CATCH題目分析許智磊6、附錄例一的原題URAL1099WORKSCHEDULINGTHEREISCERTAINAMOUNTOFNIGHTGUARDSTHATAREAVAILABLETOPROTECTTHELOCALJUNKYARDFROMPOSSIBLEJUNKROBBERIESTHESEGUARDSNEEDTOSCHEDULEDINPAIRS,SOTHATEACHPAIRGUARDSATDIFFERENTNIGHTTHEJUNKYARDCEOORDEREDYOUTOWRITEAPROGRAMWHICHGIVENTHEGUARDSCHARACTERISTICSDETERMINESTHEMAXIMUMAMOUNTOFSCHEDULEDGUARDSTHERESTWILLBEFIREDPLEASENOTETHATEACHGUARDCANBESCHEDULEDWITHONLYONEOFHISCOLLEAGUESANDNOGUARDCANWORKALONEINPUTTHEFIRSTLINEOFINPUTCONTAINSONENUMBERN222THISISTHEAMOUNTOFNIGHTGUARDSUNLIMITEDNUMBEROFLINESCONSISTINGOFUNORDEREDPAIRSI,JFOLLOW,EACHSUCHPAIRMEANSTHATGUARDIANDGUARDJCANWORKTOGETHER,BECAUSEITISPOSSIBLETOFINDUNIFORMSTHATSUITBOTHOFTHEMTHEJUNKYARDUSESDIFFERENTPARTSOFUNIFORMSFORDIFFERENTGUARDSIEHELMETS,PANTS,JACKETSITISIMPOSSIBLETOPUTSMALLHELMETONAGUARDWITHABIGHEADORBIGSHOESONGUARDWITHSMALLFEETTHEINPUTENDSWITHEOFOUTPUTYOUSHOULDOUTPUTONEPOSSIBLEOPTIMALASSIGNMENTONTHEFIRSTLINEOFTHEOUTPUTWRITETHEEVENNUMBERCTHEAMOUNTOFSCHEDULEDGUARDSTHENOUTPUTC/2LINES,EACHCONTAINING2INTEGERSI,JTHATDENOTETHATIANDJWILLWORKTOGETHERSAMPLEINPUTOUTPUT3122313212PROBLEMAUTHORJIVKOGANEV例二的原題PKU2103JACKPOTDESCRIPTIONTHEGREATDODGERSCOMPANYHASRECENTLYDEVELOPEDABRANDNEWPLAYINGMACHINEYOUPUTACOININTOTHEMACHINEANDPULLTHEHANDLEAFTERTHATITCHOOSESSOMEINTEGERNUMBERIFTHECHOSENNUMBERISZEROYOUWINAJACKPOTINTHEOTHERCASETHEMACHINETRIESTODIVIDETHECHOSENNUMBERBYTHELUCKYNUMBERSP1,P2,PNIFATLEASTONEOFTHEREMAINDERSISZEROYOUWINGREATDODGERSWANTTOCALCULATETHEPROBABILITYOFWINNINGONTHEIRMACHINETHEYTRIEDTODOIT,BUTFAILEDSOGREATDODGERSHIREDYOUTOWRITEAPROGRAMTHATCALCULATESTHECORRESPONDINGPROBABILITYUNFORTUNATELY,PROBABILITYTHEORYDOESNOTALLOWYOUTOASSUMETHATALLINTEGERNUMBERSHAVEEQUALPROBABILITYBUTONEMATHEMATICIANHINTEDYOUTHATTHEREQUIREDPROBABILITYCANBEAPPROXIMATEDASTHEFOLLOWINGLIMIT12/LIMKSKKHERESKISTHENUMBEROFINTEGERSBETWEENKANDKTHATAREDIVISIBLEBYATLEASTONEOFTHELUCKYNUMBERSINPUTINPUTFILECONTAINSNTHENUMBEROFLUCKYNUMBERS1S8，則得到10的分。數(shù)據(jù)規(guī)模和約定輸入保證描述了一棵連通的N結(jié)點(diǎn)樹，1N1000。例題五原題PKU3237TREEDESCRIPTIONYOUAREGIVENATREEWITHNNODESTHETREESNODESARENUMBERED1THROUGHNANDITSEDGESARENUMBERED1THROUGHN1EACHEDGEISASSOCIATEDWITHAWEIGHTTHENYOUARETOEXECUTEASERIESOFINSTRUCTIONSONTHETREETHEINSTRUCTIONSCANBEONEOFTHEFOLLOWINGFORMSCHANGEIVCHANGETHEWEIGHTOFTHEITHEDGETOVNEGATEABNEGATETHEWEIGHTOFEVERYEDGEON