國家集訓隊2005論文集 周源

《國家集訓隊2005論文集 周源》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、壓去冗余縮得精華——淺談信息學競賽中的“壓縮法”安徽周源壓去冗余縮得精華——淺談信息學競賽中的“壓縮法”安徽周源第20頁共20頁壓去冗余縮得精華——淺談信息學競賽中的“壓縮法”安徽周源摘要在信息學競賽中，我們經(jīng)常遇到這樣一類問題：數(shù)據(jù)規(guī)模大，或是數(shù)據(jù)間的關(guān)系復雜，總而言之即輸入數(shù)據(jù)的信息量過大。作者在綜合分析了很多信息學競賽試題后，提出了“壓縮法”這個概念：即壓去輸入數(shù)據(jù)中的冗余信息，保留下對解決問題有幫助的精華部分。壓縮法在信息學競賽中有著廣泛的應(yīng)用，但在各類問題中卻有看起來截然不同的表現(xiàn)形式，本文即將選擇多道有代表性的例題，提煉它們的共同點，提出壓縮法適用問題的兩個要點。最后，作者

2、將在總結(jié)部分著重分析壓縮法的工作特點，認為壓縮法是在化歸思想的基礎(chǔ)上，加上了“信息化”的因素，通過合理的利用信息達到化簡問題的目的。關(guān)鍵字信息學競賽壓縮法冗余/精華信息可壓縮性替代法則化歸思想信息化第20頁共20頁壓去冗余縮得精華——淺談信息學競賽中的“壓縮法”安徽周源目錄壓去冗余縮得精華1——淺談信息學競賽中的“壓縮法”1摘要2關(guān)鍵字2目錄3引子4壓縮法的定義4壓縮法的簡單實例4[例一]多源最短路問題（經(jīng)典問題）4[例二]球隊問題（經(jīng)典問題）5壓縮法的要點71.可壓縮性72.替代法則7[例三]模方程組的替代法則（經(jīng)典問題）7壓縮法的應(yīng)用8[例四]歐元兌換（BOI2003）8[分析]9

3、[動態(tài)規(guī)劃的矛盾]9[壓縮法化解矛盾]10[小結(jié)]12[例五]合并數(shù)列問題（ZOJp1794MergingSequenceProblem改編）12[分析]13[觀察壓縮要點]13[尋找可壓縮性：第一階段壓縮]14[尋找可壓縮性：第二階段壓縮]16[貪心法解題]17[小結(jié)]17總結(jié)18附錄19附錄一：關(guān)于[例四]中的斜率優(yōu)化法19附錄二：論文附件19附錄三：關(guān)于MergeSequence.pas程序的輸入格式20參考文獻20第20頁共20頁壓去冗余縮得精華——淺談信息學競賽中的“壓縮法”安徽周源引子可能不少同學都對題目中“壓縮法”這個名詞感到很陌生，不錯，因為這是作者自己發(fā)明的一個名詞J

4、。這篇論文就將帶領(lǐng)大家走近我所說的“壓縮法”，熟悉“壓縮法”?？吹健皦嚎s”二字，可能有的同學會想到我們常用的壓縮軟件，如WinZip,WinRAR等等，他們都是想盡辦法的減小文件占用的空間來為我們服務(wù)。這正是壓縮一詞的本義，即“加以壓力,以減小體積、大小、持續(xù)時間、密度和濃度等”摘錄自《高級漢語大詞典》。。然而本文中要討論的“壓縮法”的含義則為：“除去冗余信息，留下精華，以減小問題的規(guī)?！?，看得出，這正是為信息學競賽量身定制一種好方法。下面，就讓我們看看壓縮法在競賽中的精彩表現(xiàn)吧！壓縮法的定義一般來說，當我們處理問題時常常遇到一個集合S，S內(nèi)部各個元素之間的關(guān)系對問題的結(jié)果不造成影響，

5、而且也不會受到外部因素的干擾，那么我們可以將S看作一個內(nèi)外隔絕的包裹（package），忽略包裹內(nèi)部的冗余信息，并將這個包裹與外部事物的聯(lián)系保留，打包、壓縮后作為一個新的元素存儲下來以供以后分析處理。這就是壓縮法工作的基本流程，其好處在于略去了包裹內(nèi)部種種紛擾卻無用的信息，從而化簡了問題，進而用更好的方法去解決問題。壓縮法的簡單實例其實我們對壓縮法并不陌生，相信大家對下面兩個例子都有一定的了解。[例一]多源最短路問題（經(jīng)典問題）如下圖。在一個加正權(quán)的有向圖G={V,E}中，給出源的位置，求源到其余所有點的最短路長度。與一般最短路問題不同的是，本題中源是一個集合S中的所有點。而S到某一個

6、點p的最短距離等于S中所有點與p最短距離的最小值。圖中邊上的數(shù)值為邊的權(quán)值，頂點后括號內(nèi)的數(shù)值為到該點最短路的長度。第20頁共20頁壓去冗余縮得精華——淺談信息學競賽中的“壓縮法”安徽周源(2)(3)(4)AS1S3232BCDE132(3)(2)212S2圖1[分析]這道題目的關(guān)鍵在于有多個源，而為了提高效率，只能執(zhí)行一次Dijkstra算法。其實這是很簡單的，很多不同的方法都可以做到這一點。下面讓我們看一看壓縮法是怎么實現(xiàn)的：可以看出，由于不可能有一條最短路徑從一個源點出發(fā)卻又經(jīng)過另外一個源點，因此源點集合S中任何兩點間的連邊關(guān)系對答案都沒有影響。如上文所述，可以將S視為一個內(nèi)外隔

7、絕的“包裹”，舍去包裹內(nèi)的冗余信息，并將其“壓縮”成為一個新的點PS。另一方面，我們還需要保留S中節(jié)點對外的連邊情況作為壓縮后節(jié)點PS的對外連邊。這樣，我們就成功的完成了壓縮流程，得到的是一張新圖和一個單源最短路問題：這正是Dijkstra所做的。(3)(4)(2)232ABCDE1322(3)(2)PS圖2[例二]球隊問題（經(jīng)典問題）給出某個籃球隊的球員通訊圖G={V,E}如下，若存在有向邊(u,v)表示球員u可將消息及時告訴v，若教練想將一