國家集訓隊2005論文集胡偉棟

1、<p>　　淺析非完美算法在信息學競賽中的應用</p><p>　　湖南省長沙市長郡中學 胡偉棟</p><p><b>　　【目錄】</b></p><p><b>　　摘要 2</b></p><p><b>　　關(guān)鍵字 2</b></p>

2、<p><b>　　正文 2</b></p><p><b>　　引言 2</b></p><p>　　非完美算法的一些基本方法 3</p><p><b>　　隨機貪心法 3</b></p><p><b>　　抽樣測試法 4</

3、b></p><p><b>　　部分忽略法 8</b></p><p>　　完美算法的依據(jù)——RP類問題與Monte-Carlo算法 11</p><p>　　非完美算法的共性 11</p><p>　　非完美算法的優(yōu)點與缺點 12</p><p><b>　　總

4、結(jié) 13</b></p><p><b>　　感謝 13</b></p><p><b>　　參考文獻 13</b></p><p><b>　　附錄 13</b></p><p><b>　　【摘要】</b></p>

5、;<p>　　非完美算法就是用算法正確性的少量損失來換取時間、空間效率以及編程復雜度的算法。本文介紹了非完美算法的幾種重要方法及非完美算法的優(yōu)缺點，從中，可以看出：并不是完全正確的算法就一定好過非完美算法，有可能因為非完美算法的不完全性，反而使不正確的算法在很多方面比正確算法表現(xiàn)得更好。</p><p><b>　　【關(guān)鍵字】</b></p><p>　

6、　非完美算法 隨機化貪心法 抽樣測試法 部分忽略法</p><p><b>　　【正文】</b></p><p><b>　　一、引言</b></p><p>　　在平時，我們研究的算法基本都是完全正確的算法，我們所追求的，也是盡量使我們的算法正確。但在實際應用中，有很多情況都不會對數(shù)據(jù)進行天衣無縫的正確處理。如：圖片、音

7、頻、視頻的壓縮存儲，很多壓縮率比較高的方法都是有損壓縮；很多密碼驗證的方法都是采用多對一的運算方法，通過驗證的不代表密碼真正正確；搜索引擎所提供的搜索，并不能將所有滿足條件的都找到……顯然，我們不會因為它們的不完美而不使用它們，它們的存在，有著它們的實際意義：圖片、音頻、視頻的壓縮存儲，如果不損失一些，不可能將文件壓縮得很??；密碼驗證雖是多對一，但找到兩個所對的是同一個何嘗容易；搜索引擎雖不能搜索到100%的結(jié)果，但其方便、快捷是無以倫

8、比的……</p><p>　　那么，在信息學競賽中是否也可以用非完美算法解題呢？</p><p>　　本文試圖介紹一些比較有用的常見非完美算法，并希望讀者能從此得到一些啟發(fā)。</p><p>　　在開始此文前，希望讀者能認同一點：在信息學乃至整個計算機科學領(lǐng)域，不一定絕對正確的算法就是最好的算法，有可能一個在絕大多數(shù)情況下正確的算法(非完美算法)比一個完全正確的算法

9、更有前途?；蛘撸捎谒鼪]有完全正確的算法考慮得全面，而使得它的空間或時間使用得較少；或者，由于它沒有正確的算法那么嚴謹，使得編程實現(xiàn)時較容易；或者，由于所用的知識沒有正確算法那么深奧，使得它更容易被接受。</p><p>　　二、非完美算法的一些基本方法</p><p>　　1.1 隨機化貪心法</p><p>　　隨機化貪心是目前用得較廣泛的一種非完美算法。特別是

10、對求較優(yōu)解的題目，這種方法可以說是首選。</p><p>　　隨機貪心，就是用隨機與貪心結(jié)合，在算法的每一步，都盡量使決策取得優(yōu)，但不一定是最優(yōu)決策。通過多次運行，使得算法能取得一個較優(yōu)的解。有時，由于決策的優(yōu)劣判斷較復雜，直接用多次隨機也能得到較優(yōu)的結(jié)果。</p><p><b>　　例：傳染病控制</b></p><p><b>

11、　　題目大意</b></p><p>　　給出一棵傳染病傳播樹，其中根結(jié)點是被感染結(jié)點。每個時刻，被感染結(jié)點都會將傳染病傳播到它的子結(jié)點。但是，如果某時刻t切段A與其父結(jié)點B之間的邊，則時刻t以后，傳染病不會從B傳染給A(即A不會患病)。</p><p>　　每個時刻，只能切斷一條傳播途徑。問每個時刻怎樣切段傳播途徑，使最少的人被感染。</p><p>

12、<b>　　說明</b></p><p>　　本題的標準算法是搜索。關(guān)于如何用搜索解決此題，請參見附件《傳染病控制解題報告》，此解題報告由周戈林同學提供。</p><p><b>　　分析</b></p><p>　　顯然，如果某個結(jié)點已被感染，則以后沒有必要切斷它與它的父結(jié)點之間的傳播途徑，因為這樣和不切斷沒有區(qū)別(即切

13、斷已被感染的結(jié)點與其父結(jié)點之間的傳播途徑是無效的)；如果在一個時刻，切斷A與A的父結(jié)點之間的傳播途徑是有效的，切斷B與B的父結(jié)點之間的傳播途徑也是有效的，同時，B是A的子孫結(jié)點，則切斷A與A的父結(jié)點的傳播途徑優(yōu)于切斷B與B的父結(jié)點的傳播途徑。由于第t時刻被感染的顯然只可能是前t層的。因此可得到，第t時刻切斷的必然是第t層與第t+1層之間的傳播途徑。</p><p>　　本題可以用隨機貪心來做。</p>

14、<p>　　根據(jù)經(jīng)驗，每次將一個結(jié)點數(shù)最多的子樹從原樹中切開，結(jié)果會比較好。但這樣并不能適應所有情況，有時，選結(jié)點數(shù)第二多的或第三多的反而能使以后的最終結(jié)果要好一些。所以，可以多次貪心，每次都隨機的選一個能切斷的結(jié)點數(shù)較多的方案切(或者說每次使能切斷的結(jié)點數(shù)多的方案數(shù)被切的幾率大一些)，這樣，雖然大多數(shù)情況下其結(jié)果都比貪心要差，但只要隨機到一定的數(shù)量，這中間出現(xiàn)正確答案的概率就很大了。</p><p&g

15、t;　　上面加概率的隨機貪心有一點難處理的就是怎樣設(shè)置每種情況被選擇的概率。其實，對于此題，只要將每種情況被選到的概率都設(shè)成同樣大(即被選中的概率與其子結(jié)點數(shù)無關(guān))就可以了。這樣，這種方法就變成了純粹的隨機法，這種方法也能使此題得到滿分。</p><p><b>　　小結(jié)</b></p><p>　　隨機貪心是信息學競賽中的一個重要工具，由于一般情況下它都是基于簡單的

16、貪心，所以往往編程復雜性會比較低，同時運行的時間復雜度也會比較低。隨機多次是隨機貪心的一個重要手段，通過多次運行，往往能使程序得到非常優(yōu)的結(jié)果。</p><p><b>　　1.2 抽樣測試法</b></p><p>　　抽樣，即從統(tǒng)計總體中，任意抽出一部分單位作為樣本，并以其結(jié)果推算總體的相應指標。</p><p>　　在某些題目中，題設(shè)會給

17、出一系列需要測試的測試元(總體)S，若存在某一個測試元滿足某個條件A，則說S滿足性質(zhì)P，若所有測試元都不滿足條件A，則說S不滿足性質(zhì)P。</p><p>　　對于這個總體S，判斷它是否滿足性質(zhì)P，通常要將S中所有的測試元全部列舉出來才能知道。如果不列舉出全部(哪怕只有一個沒有列舉到)且當前已測試的測試元都不滿足條件A，則不敢保證剩下的測試元不滿足條件，也就不能斷定S是否滿足性質(zhì)P。</p><

18、p>　　但是，若總體具有下面的性質(zhì)：它或者不含滿足條件的測試元，或者滿足條件的測試元的個數(shù)比較多。這時，只要選取一些具有代表性的很少一部分測試元進行測試，就是保證結(jié)果基本正確。所謂有代表性，就是指取一些很特殊的測試元，同時取一些不特殊的測試元——就像問卷調(diào)查一樣，從各種工作崗位、各種年齡階段的人群中取得的問卷調(diào)查結(jié)果往往比在同一個工作崗位且年齡相仿的人群中取得的調(diào)查結(jié)果更讓人信服。</p><p>　　下面

19、，我們來看一個例子：一個總體S中含有10000個測試元，其中有100個測試元滿足條件A，現(xiàn)在，若從S中取出100個測試元進行測試，則檢查出S滿足性質(zhì)P的概率約為：63.6%，若取200個測試元，則檢查出的概率為86.9%，若取300個，則檢查出的概率可達95.3%。</p><p>　　下圖中給出了取的個數(shù)與正確率之間的關(guān)系(注意：這里只畫了取0至800個時的圖像，當取800個以上時，由于其正確率太接近100%，

20、其圖像近似一條水平直線而沒有再畫出的意義)：</p><p>　　從圖中還可以看出，只要抽樣大約70個，就有50%的正確率，抽樣大約230個，就有90%的正確率。</p><p>　　再看一個例子：如果總體S是{’A’,’B’,…,’Z’}的所有子集，而條件A是同時含有’A’~’G’的子集。按照上面，根據(jù)上面一例，可以想到，如果取一定量的子集測試，效果也會比較好，但好，對于總體S，它存在一

21、些特殊的子集——如空集、全集{’A’,’B’,…,’Z’}、只含一個元素的集合{’A’},{’B’}……這些都是我們認為比較特殊的集合，如果從這些特殊的集合中先取出幾個測試，則可能在這些集合中就能找到滿足條件A的，如此例中取全集顯然就會滿足條件。</p><p>　　下面看一個具體的實例：</p><p>　　例：Intuitionistic Logic(直覺主義邏輯)</p>

22、<p><b>　　題目大意</b></p><p>　　給定一個有向無環(huán)圖G=(V,E)，在頂點V之間建立一些偏序關(guān)系：對于x,yV，定義x≤y當且僅當x到y(tǒng)之間存在路徑(可能長度為0)。對于一個頂點集合S，定義Max(S)為S中所有最大元素的集合(即Max(S)中的任意一個頂點都不可能通過一條或多條E中的邊到達S中的其他頂點)，寫成表達式的形式為：</p>&

23、lt;p>　　Max(S)={xS|不存在yS,x≠y,x≤y}</p><p>　　令β為所有滿足Max(S)=S的集合所組成的集合，即：</p><p>　　β={S|Max(S)=S}</p><p>　　令0=Max(V)，1=，顯然0和1都屬于β</p><p>　　定義β中元素的一些操作：</p><p&

24、gt;　　P=>Q={xQ|不存在yP,x≤y},</p><p>　　PQ=Max(P∪Q),</p><p>　　PQ=Max({xV|存在yP,zQ,x≤y,x≤z}),</p><p><b>　　P=(P=>0),</b></p><p>　　P≡Q=((P=>Q)(P=>Q)) <

25、;/p><p>　　問題：對于一個含有變量的表達式，問是否無論變量如何在β中取值，其運算結(jié)果都是1？</p><p>　　數(shù)據(jù)范圍：其中|V|≤100；|E|≤5000；對于同一個圖，要處理k個表示式，k≤20；每個表達式長度不超過254個字符；|β|≤100； (vj是在第j個表達式中用到的變量個數(shù))</p><p><b>　　分析</b>&l

26、t;/p><p>　　本題的最后一個數(shù)據(jù)范圍其實暗示了我們，此題可以用枚舉來做，即枚舉所有變量的所有可能取值。顯然，如果要求完全正確，變量取值的總方案數(shù)是不可能減少的，即可能達到106，這時，就得設(shè)法減少計算的復雜度。顯然，上面的基本運算都是O(|V|)或O(|E|)或更高的，而計算一個表達式可能要使用上百次基本運算，這樣，盡管此題有5秒的時限，這樣的枚舉也是很難出解的。</p><p>　　

27、由|β|≤100，可以想到，將β中的每一個元素先用一個整數(shù)代替，并計算出對這些數(shù)進行上面的基本運算所得的值(當然也用整數(shù)表示)。對這些值列一個表，以后計算時就只要從表中查找結(jié)果了。這樣，基本運算的復雜度就可以降到O(1)，總的復雜度就可以降為。</p><p>　　此題還有一種解決方法，那就是抽樣。將變量取β中一些比較特殊的值(如0，1，……)看作特殊樣品，其它的看作一般樣品。抽取一些特殊樣品和一些一般樣品，對它

28、們進行測試，如果對于一個式子，所有的樣品都滿足條件，則說明式子滿足條件，否則說式子滿足條件。實踐證明，只要抽取不到1000個樣品即可得到比較高的正確率。</p><p>　　當然，對于這類多測試數(shù)據(jù)的題目，要基本保證一個測試點對，每組測試數(shù)據(jù)的正確概率必須更高一些。如：對于有20個組測試數(shù)據(jù)的測試點，如果保證每組數(shù)據(jù)的正確概率為95%，則整個測試點的正確概率只有0.9520，還不到36%；如果保證每組數(shù)據(jù)的正確概

29、率為99%，整個測試點的正確概率才82%；如果每組數(shù)據(jù)正確概率達到99.9%，則整個測試點的正確概率就會有98%。</p><p>　　這里特別要說明的是：一般情況下，抽樣的數(shù)目應該盡量多(在保證不超時的前提下)，這樣才能保證正確概率較大。</p><p><b>　　抽樣法的實際運用：</b></p><p>　　在測試質(zhì)數(shù)時，抽樣法是一個非

30、常有用的工具。下面給出一種質(zhì)數(shù)判定方法：</p><p>　　對于待判定的整數(shù)n。設(shè)n-1=d*2s(d是奇數(shù))。對于給定的基底a，若</p><p><b>　　或存在0≤r<s使</b></p><p>　　則稱n為以a為底的強偽質(zhì)數(shù)(Strong Pseudoprime)。利用二分法，可以在O(log2n)的時間內(nèi)判定n是否為以a為

31、底的強偽質(zhì)數(shù)。</p><p>　　對于合數(shù)c，以小于c的數(shù)為底，c至多有1/4的機會為強偽質(zhì)數(shù)(Monier 1980, Rabin 1980)。</p><p>　　根據(jù)這條，判斷一個數(shù)n是否為質(zhì)數(shù)，可以隨機地抽取小于n的k個數(shù)為底。這樣，正確的概率不小于1-4-k。顯然，這已經(jīng)非常優(yōu)秀了，通常只要取幾十組就可以保證基本正確。</p><p>　　如果不是隨機抽

32、樣，而是抽樣特殊情況——最小的幾個質(zhì)數(shù)，則：</p><p>　　如果只用2一個數(shù)進行測試，最小的強偽質(zhì)數(shù)(反例)是2047(所以一個數(shù)顯然不夠)；</p><p>　　如果用2和3兩個數(shù)進行測試，最小的強偽質(zhì)數(shù)大于106；</p><p>　　如果用2,3,5進行測試，最小的強偽質(zhì)數(shù)大于2×107；</p><p>　　如果用2,

33、3,5,7進行測試，最小的強偽質(zhì)數(shù)大于3×109，已經(jīng)比32位帶符號整數(shù)的最大值(Pascal中的Maxlongint)還大了。</p><p>　　可見，通常只要抽取2,3,5,7這幾個固定的數(shù)進行測試就能保證測試的正確性了。</p><p>　　我們知道，最樸素的質(zhì)數(shù)測試方法是用2至的數(shù)對n進行試除。這樣，測試一個數(shù)的復雜度為O(n0.5)，用上面的方法，每次測試只要O(lo

34、g2n)的復雜度，由于只要測試很少的幾次，所以，其總復雜度仍是O(log2n)的?？梢?，用抽樣的方法對質(zhì)數(shù)進行測試的算法明顯優(yōu)于樸素的質(zhì)數(shù)測試法。</p><p><b>　　小結(jié)</b></p><p>　　從上面的例子可以看出，由于抽樣法只對總體中的一部分更行測試，所以它要測試的次數(shù)非常少，從而使得算法需要的時間比完全枚舉少很多，算法的效率也會高很多。</p

35、><p><b>　　1.3 部分忽略法</b></p><p>　　在信息學中，可能會遇到這樣情況：一個題的分類非常復雜，且某些情況的處理非常復雜，但這些情況往往不是主要情況(即出現(xiàn)的概率很小或不處理這些情況對答案不會造成很大的影響)。有時，忽略這些復雜卻影響不大的情況會使程序達到令人滿意的結(jié)果。</p><p><b>　　例：Pol

36、ygon</b></p><p><b>　　題目大意</b></p><p>　　在此題中，所有的多邊形均指凸多邊形。</p><p>　　給定兩個多邊形A和B，A和B的Minkowski和是指包含所有形如(x1+x2, y1+y2) 的點的多邊形，其中(x1,y1) 是A中的點，(x2,y2)是B中的點。</p>

37、<p>　　我們考慮Minkowski和的一種逆運算。給定一個多邊形P, 我們尋找兩個多邊形A和B，滿足：</p><p>　　- P是A和B的Minkowski和；</p><p>　　- A有2到4個不同的頂點(線段、三角形或四邊形)；</p><p>　　- A必須包含盡可能多的頂點。</p><p>　　說明：此題附官方解答

38、，其復雜度為O(N2m2)，其中N為多邊形P的頂點數(shù)，m為P的邊上的整點個數(shù)的最大值</p><p><b>　　分析</b></p><p>　　由于本題中，位置并不是很難處理，所以此題將不考慮多邊形的位置問題，只考慮其形狀和大小。</p><p>　　根據(jù)定義可以知道，對兩個多邊形A、B求Minkowski和，就是將它們的所有的邊看作有順序

39、的向量，對所有向量按其級角排序，然后將所有的向量順次連接，最后將共線同向的向量合并的過程。</p><p>　　由上面加法的過程不難想到，原來的多邊形A、B的每條邊在P中仍存在一條邊與原邊共線同向且模不小于原邊，因此：</p><p>　　將一個多邊形P拆成邊數(shù)為K的多邊形A與不定邊數(shù)的多邊形B相加的形式，就是要從P中找出K條邊，從每邊取出一段(或整條邊)，使這K段正好能圍成一個多邊形，這

40、個多邊形就是A，剩下的按照向量首尾相連可得到B。</p><p>　　如：從上圖的多邊形P中取一個邊數(shù)為2的多邊形：</p><p>　　從P中取出一個三角形、四邊形，也是同樣的方法。</p><p>　　這個算法看起來很簡單，但實現(xiàn)起來并沒有想象中那么輕松。</p><p>　　找一個二邊形，只要找到一對共線向量即可。</p>

41、<p>　　找一個三角形，可以枚舉三條邊，然后判斷，其復雜度是O(N3m3)。在提交答案類題看來，已經(jīng)很不錯了。</p><p>　　找一個四邊形，如果枚舉四條邊，然后判斷，其復雜度是O(N4m4)，因其中的m是未知的，所以不敢輕易使用。這時可以枚舉三條邊，另一條邊通過對邊的二分查找得到。由于第四條邊可能是多邊形P中某條邊的一段，而P中一共可能有N*m段，因m未知，使得空間分配也不好處理；同時，由于存

42、儲時不僅要存儲每段所對應的原來的邊的序號，還要存儲每段是占原來的幾分之幾……此時遇到的問題可能還遠不只這些，這時，就很難保證程序不出錯。</p><p>　　這種，不妨做一個大膽的假設(shè)：假設(shè)第四條邊是P中的一條完整的邊。這樣，只要存儲P條邊即可，且這P條邊都是原來多邊形中的完整的邊，所以編程中要考慮的問題就少多了，同時出錯的可能性也小多了。</p><p>　　這樣做，對于官方的數(shù)據(jù)，有9

43、個測試點可以出解，所出的解全部是最優(yōu)解。另一個測試點可以用手做。</p><p>　　部分忽略法的實際應用</p><p>　　下面看一下判斷一個點P是否在一個簡單多邊形內(nèi)的算法：</p><p>　　假設(shè)已經(jīng)判斷了P在多邊形邊上這種特殊情況，剩下的只有點在多邊形內(nèi)和外的問題。</p><p>　　傳統(tǒng)的判斷算法是：以P為端點作一條射線，然后

44、根據(jù)射線與多邊形的交點個數(shù)是奇數(shù)個還是偶數(shù)個來判斷其是否在多邊形內(nèi)。</p><p>　　但是，在計算交點個數(shù)的時候，有一種特殊情況：所作的射線經(jīng)過多邊形的某個頂點(有可能更特殊的與多邊形的一條邊重合)。如下圖：</p><p>　　在(a)中，處理的結(jié)果應為射線與多邊形有奇數(shù)個交點，而(b)中，處理的結(jié)果應為射線與多邊形有偶數(shù)個交點，如果不加特殊處理，則兩種情況所得到的結(jié)果是相同的。&l

45、t;/p><p>　　如果采用部分忽略法似乎會出現(xiàn)錯誤。但是，如果取的射線是一條很“一般”的射線：如在平面內(nèi)隨機取一個異于P的點Q，且保證Q的坐標有若干位小數(shù)，從P作一條射線，使射線經(jīng)過Q，則，可以說，要出錯的概率是非常小的。如果多取幾個點，分別對這幾個點進行判斷，然后取這些結(jié)果中出現(xiàn)得最多的結(jié)果，則要出錯就更不可能了。</p><p><b>　　小結(jié)</b></

46、p><p>　　通過上面的例題可以看出，能過忽略部分復雜情況，能使算法的思考復雜性和編程復雜性降低。僅管它可能造成算法在一定程度上的錯誤，但這種錯誤通常是很小的。所以，有時采用部分忽略法仍是非常好的選擇。</p><p>　　三、非完美算法的依據(jù)——RP類問題與Monte-Carlo算法</p><p>　　前面所講的一些方法，似乎都是靠的“運氣”成分。但是，這些算法有

47、它的依據(jù)：</p><p>　　如果一個問題存在一個隨機算法，使得它有50%以上的概率得到期望的結(jié)果，那么這個問題屬于RP類問題。該算法稱為Monte-Carlo算法。</p><p>　　如果一個問題是RP類問題，可以通過多次運行它的一個Monte-Carlo算法而得到“幾乎每次都是正確”的算法。</p><p>　　由于RP類問題與Monte-Carlo算法不是

48、本文研究的重點，這里不再多做介紹，有興趣的讀者可以參閱相關(guān)的資料。</p><p>　　四、非完美算法的共性</p><p>　　非完美算法有很多種，但是，它們并不是完全不同的，它們之間存在一個共同的性質(zhì)，那就是不完全性。上面的非完美算法都是由于其不完全性而使得它們具有一些完全正確的算法所不能具備的優(yōu)勢，同時，其不完全性也導致了算法不是完全正確的。</p><p>

49、　　五、非完美算法的優(yōu)點與缺點</p><p><b>　　4.1 優(yōu)點</b></p><p>　　從上面的分析和舉例，相信讀者對非完美算法的優(yōu)點已經(jīng)有所了解了，現(xiàn)整理如下：</p><p>　　①時空消耗低：這是非完美算法的一個最突出的優(yōu)點，也是大多數(shù)情況下使用它的原因。</p><p>　　②編程復雜度低：因為非完

50、美算法會可能繞過紛繁的處理或會忽略掉非常難處理的一些情況，其編程復雜度可以得到一定的降低。在比賽中，低的編程復雜度往往比低的算法時間復雜更容易得到令人滿意的結(jié)果。</p><p>　?、鬯季S復雜度低：同樣也是因為非完美算法可能忽略掉非常難處理的一些情況。</p><p>　?、苣軠p少編程錯誤：通過前面幾點，這點也就顯然了。也許，一個非常優(yōu)秀的算法，因為它的一點點小錯誤，就導致其前功盡棄，而

51、一個非完美的算法，因為它較容易實現(xiàn)，減少或避免了編程錯誤，反而能得到意想不到的好結(jié)果。</p><p><b>　　4.2 缺點</b></p><p>　　非正確性：這是不言而喻的，非完美算法，值得利用的就是它的非正確性。但非正確性使得算法不僅依賴算法的好壞、代碼的好壞，還依賴于數(shù)據(jù)。如果數(shù)據(jù)較弱，非完美算法可能得到較高的分數(shù)，如果數(shù)據(jù)較強，其結(jié)果不一定很理想。&l

52、t;/p><p><b>　　【總結(jié)】</b></p><p>　　本文主要介紹了非完美算法的幾種重要方法。從上面的算法可以看到，并不是正確的算法就一定好過不完全正確的算法，因為非完美算法的不完全性，反而使非完美算法在很多方面比正確算法表現(xiàn)得更好。因此，合理的使用非完美算法能使我們得到令人滿意結(jié)果。</p><p><b>　　【感謝】&

53、lt;/b></p><p>　　衷心感謝向期中老師在我寫這篇論文時對我的指導和幫助。</p><p>　　衷心感謝劉汝佳教練對我的指導和啟發(fā)。</p><p>　　衷心感謝王俊、任愷同學對我的支持和幫助。</p><p>　　衷心感謝肖湘寧、周戈林同學在臨近期末考試時還能為我看論文，并向我提很多寶貴的意見，特別感謝周戈林同學提供NOI

54、P2003《傳染病控制》的解題報告。</p><p><b>　　【參考文獻】</b></p><p>　　《論隨機化算法的原理與設(shè)計》——周詠基,1999</p><p>　　《The CRC Concise Encyclopedia of Mathematics》——Eric W. Weisstein,CRC Press</p>

55、<p>　　《計算幾何——算法分析與設(shè)計》——周培德,清華大學出版社,廣西科學技術(shù)出版社</p><p>　　《算法藝術(shù)與信息學競賽》——劉汝佳、黃亮，清華大學出版社</p><p>　　《IOI'04: Solution of Polygon》——Ioannis Emiris and Elias Tsigaridas,2004</p><p>

56、;<b>　　【附錄】</b></p><p><b>　　最小強偽質(zhì)數(shù)表</b></p><p>　　傳染病控制原題(NOIP2003)</p><p><b>　　【問題背景】</b></p><p>　　近來，一種新的傳染病肆虐全球。蓬萊國也發(fā)現(xiàn)了零星感染者，為防止該病在

57、蓬萊國</p><p>　　大范圍流行，該國政府決定不惜一切代價控制傳染病的蔓延。不幸的是，由于人們尚未完</p><p>　　全認識這種傳染病，難以準確判別病毒攜帶者，更沒有研制出疫苗以保護易感人群。于是，</p><p>　　蓬萊國的疾病控制中心決定采取切斷傳播途徑的方法控制疾病傳播。經(jīng)過 WHO（世界衛(wèi)</p><p>　　生組織）以及

58、全球各國科研部門的努力，這種新興傳染病的傳播途徑和控制方法已經(jīng)研究</p><p>　　消楚，剩下的任務就是由你協(xié)助蓬萊國疾控中心制定一個有效的控制辦法。</p><p><b>　　【問題描述】</b></p><p>　　研究表明，這種傳染病的傳播具有兩種很特殊的性質(zhì)；</p><p>　　第一是它的傳播途徑是樹型的

59、，一個人X只可能被某個特定的人Y感染，只要Y不</p><p>　　得病，或者是XY之間的傳播途徑被切斷，則X就不會得病。</p><p>　　第二是，這種疾病的傳播有周期性，在一個疾病傳播周期之內(nèi)，傳染病將只會感染一</p><p>　　代患者，而不會再傳播給下一代。</p><p>　　這些性質(zhì)大大減輕了蓬萊國疾病防控的壓力，并且他們已經(jīng)

60、得到了國內(nèi)部分易感人群</p><p>　　的潛在傳播途徑圖（一棵樹）。但是，麻煩還沒有結(jié)束。由于蓬萊國疾控中心人手不夠，同</p><p>　　時也缺乏強大的技術(shù)，以致他們在一個疾病傳播周期內(nèi)，只能設(shè)法切斷一條傳播途徑，而</p><p>　　沒有被控制的傳播途徑就會引起更多的易感人群被感染（也就是與當前已經(jīng)被感染的人有</p><p>　

61、　傳播途徑相連，且連接途徑?jīng)]有被切斷的人群）。當不可能有健康人被感染時，疾病就中止</p><p>　　傳播。所以，蓬萊國疾控中心要制定出一個切斷傳播途徑的順序，以使盡量少的人被感染。</p><p>　　你的程序要針對給定的樹，找出合適的切斷順序。</p><p><b>　　【輸入格式】</b></p><p>　　

62、輸入格式的第一行是兩個整數(shù)n（1≤n≤300）和p。接下來p行，每一行有兩個整數(shù)i</p><p>　　和j，表示節(jié)點i和j間有邊相連（意即，第i人和第j人之間有傳播途徑相連）。其中節(jié)點</p><p>　　1是已經(jīng)被感染的患者。</p><p><b>　　【輸出格式】</b></p><p>　　只有一行，輸出總共被

63、感染的人數(shù)。</p><p><b>　　【輸入樣例】</b></p><p><b>　　7 6</b></p><p><b>　　1 2</b></p><p><b>　　1 3</b></p><p><b>　

64、　2 4</b></p><p><b>　　2 5</b></p><p><b>　　3 6</b></p><p><b>　　3 7</b></p><p><b>　　【輸出樣例】</b></p><p>&l

65、t;b>　　3</b></p><p>　　Polygon中文原題</p><p><b>　　【問題描述】</b></p><p>　　凸多邊形的定義如下：多邊形內(nèi)任意兩點X和 Y 的連線上的所有點都在多邊形內(nèi)部。在本題中的所有多邊形都是擁有至少兩個頂點的凸多邊形并且所有頂點互不相同，且具有整數(shù)坐標。多邊形的任意三個頂點不共

66、線。在下文中的“多邊形” 一詞都是指這樣的多邊形。</p><p>　　給定兩個多邊形A 和 B， A 和 B 的Minkowski 和 包含所有形如(x1+x2, y1+y2) 的點，其中 (x1, y1) 是 A 中的點，(x2, y2) 是 B 中的點。多邊形的Minkowski 和也是一個多邊形。下圖是一個例子：兩個三角形和它們的 Minkowski 和。</p><p>　　我

67、們考慮Minkowski 和 的一種逆運算。給定一個多邊形P, 我們尋找兩個多邊形A 和 B ，滿足:</p><p>　　P 是A 和 B 的Minkowski 和, </p><p>　　A 有2 到 4 個不同的頂點，例如，它是一條線段（2個頂點）, 一個三角形（3個頂點），或一個四邊形（4個頂點），</p><p>　　A 必須包含盡可能多的頂點，例如：&

68、lt;/p><p>　　A 如果可能的話，必須是一個四邊形， </p><p>　　如果 A 不可能是一個四邊形而有可能是一個三角形，則它必須是一個三角形， </p><p><b>　　否則它是一條線段。</b></p><p>　　很顯然， A 和 B 都不能等于 P ，因為如果其中一個等于P， 則另一個只能是一個點，而

69、點不是一個合法的多邊形。</p><p>　　給定多個輸入文件，每個輸入文件描述一個多邊形P。 對于每一個輸入文件，你必須找出滿足上述條件的A 和 B， 并且創(chuàng)建一個文件來描述A 和 B 。 對于所有給定的輸入文件， A 和 B 一定存在。如果存在多組解，只需要輸出其中的任意一組。不要提交源程序，只需要提交輸出文件。 </p><p><b>　　【輸入格式】</b>

70、</p><p>　　共有十組輸入文件從 polygon1.in 到 polygon10.in, 在polygon 后的數(shù)字是輸入文件序號。每個輸入文件的構(gòu)成如下：第一行包含一個整數(shù)N： 多邊形 P的頂點個數(shù)。 接下來的N 行以逆時針方向描述了N 個頂點的坐標，每個頂點一行。第I+1 (I = 1, 2, ..., N) 行包含兩個整數(shù)XI 和 YI， 以一個空格隔開，表示第I 個頂點。所有坐標為非負整數(shù)。&l

71、t;/p><p><b>　　【輸出格式】</b></p><p>　　針對給定的輸入文件，你需要給出相應的10個輸出文件用以描述相應的A 和 B。輸出文件的第一行應包含：</p><p>　　#FILE polygon I</p><p>　　這里整數(shù)I 表示相應的輸入文件序號。</p><p>　

72、　輸出文件的格式與輸入文件類似。第二行包含一個整數(shù) NA：A中的頂點數(shù) (2≤NA≤4)。 接下來的 NA 行以逆時針方向描述A 的NA個頂點，每個頂點一行。第 I+2 ( I = 1, 2, ..., NA) 行包含兩個整數(shù) X 和 Y, 以一個空格隔開：表示A的第I個頂點。</p><p>　　第 NA +3 行包含一個整數(shù) NB： 表示 B 中的頂點個數(shù) (2≤NB)。 接下來的 NB 行以逆時針方向描述B

73、 的NB 個頂點，每個頂點一行。第NA +J+3 ( J = 1, 2, ..., NB) 行包含兩個整數(shù)X 和 Y， 以一個空格隔開：表示B 的第 J個頂點。 </p><p><b>　　【輸入輸出樣例】</b></p><p>　　polygon0.in</p><p>　　對于上面的輸入，下面兩種輸出都是正確的，因為在每種輸出中A 都是