noip06-09試題分析.ppt

1、NOIP06-09試題分析, 623737031,能量項(xiàng)鏈(NOIP2006-1),在Mars星球上，每個(gè)Mars人都隨身佩帶著一串能量項(xiàng)鏈。在項(xiàng)鏈上有N顆能量珠。能量珠是一顆有頭標(biāo)記與尾標(biāo)記的珠子，這些標(biāo)記對(duì)應(yīng)著某個(gè)正整數(shù)。并且，對(duì)于相鄰的兩顆珠子，前一顆珠子的尾標(biāo)記一定等于后一顆珠子的頭標(biāo)記。因?yàn)橹挥羞@樣，通過(guò)吸盤（吸盤是Mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時(shí)釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標(biāo)記為m，尾標(biāo)記為r，后一顆能量珠的頭標(biāo)記為r，尾標(biāo)記為n，則聚合后釋放的能量為（Mars單位），新產(chǎn)生的珠子的頭標(biāo)記為m，尾標(biāo)記為n。,需要時(shí)，Mar

2、s人就用吸盤夾住相鄰的兩顆珠子，通過(guò)聚合得到能量，直到項(xiàng)鏈上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請(qǐng)你設(shè)計(jì)一個(gè)聚合順序，使一串項(xiàng)鏈釋放出的總能量最大。 例如：設(shè)N=4，4顆珠子的頭標(biāo)記與尾標(biāo)記依次為(2，3) (3，5) (5，10) (10，2)。我們用記號(hào)表示兩顆珠子的聚合操作，(jk)表示第j，k兩顆珠子聚合后所釋放的能量。則第4、1兩顆珠子聚合后釋放的能量為：(41)=10*2*3=60。 這一串項(xiàng)鏈可以得到最優(yōu)值的一個(gè)聚合順序所釋放的總能量為 (41)2)3）=10*2*3+10*3*5+10*5*10=710。,【輸入文件】 輸入文件energy.in的第一

3、行是一個(gè)正整數(shù)N（4N100），表示項(xiàng)鏈上珠子的個(gè)數(shù)。第二行是N個(gè)用空格隔開(kāi)的正整數(shù)，所有的數(shù)均不超過(guò)1000。第i個(gè)數(shù)為第i顆珠子的頭標(biāo)記（1iN），當(dāng)i時(shí)，第i顆珠子的尾標(biāo)記應(yīng)該等于第i+1顆珠子的頭標(biāo)記。第N顆珠子的尾標(biāo)記應(yīng)該等于第1顆珠子的頭標(biāo)記。 至于珠子的順序，你可以這樣確定：將項(xiàng)鏈放到桌面上，不要出現(xiàn)交叉，隨意指定第一顆珠子，然后按順時(shí)針?lè)较虼_定其他珠子的順序。 【輸出文件】 輸出文件energy.out只有一行，是一個(gè)正整數(shù)E（E2.1*109），為一個(gè)最優(yōu)聚合順序所釋放的總能量。,分析,先枚舉一個(gè)位置p，將珠子變成一條鏈。設(shè)鏈中的第i顆珠子頭尾標(biāo)記為(Si-1與Si)。令Gi

4、,j表示從第i顆珠子一直合并到第j顆珠子所能產(chǎn)生的最大能量，則： Gi,j=minGi,k+Gk+1,j+Si-1*Sk*Sj, i=kj 邊界條件： Gi,i=0 最后的最優(yōu)解為G1,n 該算法需要枚舉p,i,j,k，而且每一重枚舉都是O(n)，所以總的時(shí)間復(fù)雜度為O(n4)，而n可能有100，因此直接實(shí)現(xiàn)這個(gè)算法有超時(shí)的危險(xiǎn)。,在上式中，我們的方程只和珠子的標(biāo)記(即Si)有關(guān)，而與編號(hào)無(wú)關(guān)，因此，珠子從1到n編號(hào)和2到n+1編號(hào)是等效的。現(xiàn)在不枚舉p，令Si=Si mod n (n=i=2n)，仍用上面的方程計(jì)算，則計(jì)算所得的G1,n為從第一顆珠子前斷開(kāi)時(shí)最優(yōu)值，而G2,n+1計(jì)算的正好是

5、從第二顆珠子前斷開(kāi)時(shí)的最優(yōu)值。Gi,n+i-1表示從第i顆前斷的最優(yōu)值。利用這種方法將長(zhǎng)為n的環(huán)變?yōu)榱碎L(zhǎng)為2n的鏈，卻能不能枚舉p而算得最優(yōu)值。 一般而言，如果是對(duì)環(huán)的最優(yōu)值問(wèn)題能通過(guò)枚舉斷點(diǎn)而求得最優(yōu)解，都可以將環(huán)拉成鏈后復(fù)制一遍，求出鏈中所有長(zhǎng)為n的段的最優(yōu)值，此值即為環(huán)中對(duì)應(yīng)的最優(yōu)解。這此對(duì)環(huán)的動(dòng)態(tài)規(guī)劃最簡(jiǎn)單也是最常用的降維方法。 通過(guò)拉伸后，復(fù)雜度降為了O(n3)，可以迅速出解。,金明的預(yù)算方案(NOIP2006-2),金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：“你的房間需要購(gòu)買哪些物品，怎么布置，你說(shuō)了算，只要

6、不超過(guò)N元錢就行”。今天一早，金明就開(kāi)始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個(gè)主件的，下表就是一些主件與附件的例子：,如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個(gè)主件可以有0個(gè)、1個(gè)或2個(gè)附件。附件不再有從屬于自己的附件。金明想買的東西很多，肯定會(huì)超過(guò)媽媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)15表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是10元的整數(shù)倍）。他希望在不超過(guò)N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。 設(shè)第j件物品的價(jià)格為vj，重要度為wj，共選中了k件物品，編號(hào)依次為j1，

7、j2，jk，則所求的總和為： vj1*wj1+vj2*wj2+ +vjk*wjk。（其中*為乘號(hào)） 請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單。,【輸入文件】 輸入文件budget.in 的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：n m （其中N（0，表示該物品為附件，q是所屬主件的編號(hào)） 【輸出文件】 輸出文件budget.out只有一個(gè)正整數(shù)，為不超過(guò)總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（200000）。,假設(shè)只有主件的情況,給出m件物品和n元錢，每個(gè)物品有一個(gè)費(fèi)用Ci和價(jià)值Vi，問(wèn)買哪些東西能使得所購(gòu)寫的物品的價(jià)值和最大。 用Fi,j表示在前i件物品中選擇一些，使所花的錢數(shù)不超過(guò)j時(shí)所得

8、的最大價(jià)值。則 F0,j=Fi,0=0 (邊界條件) Fi,j=maxFi-1,j, Fi-1,j-Ci+Vi 此算法的復(fù)雜度為O(nm)。,回到原題,假設(shè)一件物品i有t種附件選擇方案，費(fèi)用分別為Ci1.Cit，價(jià)值分別為Vi1.Vit，則,由于每個(gè)物品不超過(guò)兩個(gè)附件，所以附件的選擇方案非常有限，只要手工枚舉一下就可以了。當(dāng)然，巧妙的做法是：為不夠兩件附件的物品增加費(fèi)用和價(jià)值都為0的虛物品，使每件物品的附件數(shù)都是2。然后分別枚舉2個(gè)附件選還是不選。這個(gè)方法的復(fù)雜度仍為O(nm)，可以很好的解決本題了,作業(yè)調(diào)度方案 (NOIP2006-3),M（20）臺(tái)機(jī)器加工n（20）個(gè)工件, 每個(gè)工件都有m

9、道工序,分別在在指定的m臺(tái)機(jī)器上進(jìn)行加工，且每個(gè)加工的加工時(shí)間不同。 每個(gè)工序的加工記為一個(gè)操作，記為j-k,表示第j個(gè)工件的第k個(gè)工序， 現(xiàn)在給出n*m個(gè)操作順序，并且每個(gè)操作需要滿足以下兩個(gè)約束條件。 (1) 對(duì)同一個(gè)工件，每道工序必須在它前面的工序完成后才能開(kāi)始； (2) 同一時(shí)刻每一臺(tái)機(jī)器至多只能加工一個(gè)工件。 一個(gè)操作可以插入到某臺(tái)機(jī)器的某個(gè)空檔時(shí)，我們約定：在保證約束條件1、2的條件下，盡量靠前插入。于是，在這些約定下，對(duì)于給定的安排順序，符合該安排順序的實(shí)施方案是唯一的 請(qǐng)你計(jì)算出該方案完成全部任務(wù)所需的總時(shí)間。,例如，取n=3,m=2，已知數(shù)據(jù)如下： 則對(duì)于安排順序“1 1 2

10、 3 3 2”，下圖中的有兩個(gè)實(shí)施方案，所需要的總時(shí)間分別是10與12 ，方案一正確。,分析,典型模擬題 初始化m個(gè)隊(duì)列，模擬m臺(tái)機(jī)器加工工件的情況。 按操作順序，依次將每個(gè)工件的加入到相應(yīng)的的隊(duì)列中。例如讀入的數(shù)為(i,j,k)則將第j個(gè)工件的第k個(gè)工序加入插入第i隊(duì)列中。 在插入時(shí)候，在保證工序順序的前提下，盡可能的靠前插入到對(duì)應(yīng)的空白時(shí)間。最后取m個(gè)隊(duì)列的結(jié)束時(shí)間最大值即為答案。 時(shí)間復(fù)雜度最壞情況下為O(mn2)。,2k進(jìn)制數(shù)(noip2006-4),設(shè)r是個(gè)2k 進(jìn)制數(shù)，并滿足以下條件： （1）r至少是個(gè)2位的2k 進(jìn)制數(shù)。 （2）作為2k進(jìn)制數(shù)，除最后一位外，r的每一位嚴(yán)格小于它右

11、邊相鄰的那一位。 （3）將r轉(zhuǎn)換為2進(jìn)制數(shù)q后，則q的總位數(shù)不超過(guò)w。 在這里，正整數(shù)k（1k9）和w（w30000）是事先給定的。 問(wèn)：滿足上述條件的不同的r共有多少個(gè)？,舉例,設(shè)k=3，w=7。則r是個(gè)八進(jìn)制數(shù)（23=8）。由于w=7，長(zhǎng)度為7的01字符串按3位一段分，可分為3段（即1，3，3，左邊第一段只有一個(gè)二進(jìn)制位），則滿足條件的八進(jìn)制數(shù)有： 2位數(shù)：高位為1：6個(gè)（即12，13，14，15，16，17），高位為2：5個(gè)，高位為6：1個(gè)（即67）。共6+5+1=21個(gè)。 3位數(shù)：高位只能是1，第2位為2：5個(gè)（即123，124，125，126，127），第2位為3：4個(gè)，第2位為6：

12、1個(gè)（即167）。共5+4+1=15個(gè)。 所以，滿足要求的r共有36個(gè)。,設(shè)M=2k，令A(yù)= 為一個(gè)滿足條件的M進(jìn)制數(shù)，先不看第三個(gè)位數(shù)限制的條件，原來(lái)的兩個(gè)條件可以翻譯為： (1)an-10，n1 (2)ai2，則將它的最高位即an-1去掉，為A，由00，由此可進(jìn)一步證明A也滿足這兩個(gè)條件。當(dāng)然，很容易證明，A會(huì)滿足位數(shù)限制條件。,分析(1),分析(2),首先來(lái)計(jì)算an-1為一個(gè)固定值的M進(jìn)制數(shù)的總數(shù)。設(shè)an-1=V1，則an-2可以取V1+1到M-1中的任何數(shù)，當(dāng)an-2取V2(在V1+1到M-1中)時(shí)，其總數(shù)對(duì)應(yīng)于n=n-1,an-1=V2時(shí)的數(shù)的總數(shù)，這是一個(gè)更小規(guī)模的子問(wèn)題。不難想到

13、，如果用Tn,V1表示位數(shù)為n的M進(jìn)制數(shù)，最高位的值為V1，且滿足題設(shè)條件的M進(jìn)制數(shù)的總數(shù)，則得到遞推公式,分析(3),令函數(shù)Sn,V1表示位數(shù)為n的M進(jìn)制數(shù)，最高位的值不小于V1，且滿足題設(shè)條件的M進(jìn)制數(shù)的總數(shù)，則 Tn,V1=Sn-1,V1+1,邊界條件： T1,V1=1 (1=V1M) Sn,M=0,1,分析(4),現(xiàn)在我們能計(jì)算出任何Tn,V1的值，是否可以計(jì)算出原問(wèn)題的解呢？ 可以！首先看一下兩位M進(jìn)制數(shù)中滿足條件的數(shù)的個(gè)數(shù)(暫不考慮w2k的情況)：最高位可以取1到M-1。其滿足題設(shè)條件的數(shù)的總數(shù)應(yīng)該是,同樣的，當(dāng)w=nk時(shí)，n位滿足條件的數(shù)應(yīng)該為Sn,1?，F(xiàn)在，所以位數(shù)小于w/k的

14、數(shù)都找出來(lái)了，只要找位數(shù)等于w/k的數(shù)。同樣，只要枚舉最高位就可以得出解，由于M正好為2的整冪，所以最高位的取值范圍是可以算出來(lái)的，設(shè)能取的最大值為U，則倍數(shù)正好為w/k位的滿足條件的數(shù)的總數(shù)為,統(tǒng)計(jì)數(shù)字 (NOIP2007-1),某次科研調(diào)查時(shí)得到了n個(gè)自然數(shù)，每個(gè)數(shù)均不超過(guò)1500000000（1.5*109）。已知不相同的數(shù)不超過(guò)10000個(gè)，現(xiàn)在需要統(tǒng)計(jì)這些自然數(shù)各自出現(xiàn)的次數(shù)，并按照自然數(shù)從小到大的順序輸出統(tǒng)計(jì)結(jié)果。 【限制】 40%的數(shù)據(jù)滿足：1=n=1000 80%的數(shù)據(jù)滿足：1=n=50000 100%的數(shù)據(jù)滿足：1=n=200000，每個(gè)數(shù)均不超過(guò)1 500 000 000（

15、1.5*109）,分析,方法1：因?yàn)閚=2*105，本題可使用快速排序，時(shí)間復(fù)雜度為O(n*logn),操作次數(shù)為2*105*log(2*105)4*106 方法2：維護(hù)一個(gè)二叉樹(shù)，以數(shù)的大小作為節(jié)點(diǎn)的權(quán)值，以數(shù)的重復(fù)次數(shù)作為節(jié)點(diǎn)的附加信息。之后中序遍歷即可。其算法復(fù)雜度依然為O(nlogn),字符串的展開(kāi) (NOIP2007-2),給定一個(gè)字符串，如果某個(gè)-左邊同為數(shù)字或同為字母，并且右邊的Ascii碼嚴(yán)格大于左邊的Ascii碼，則在原串中刪去-，并在該位置上插入左右字符之間的字符。其中插入字符有3個(gè)參數(shù)。參數(shù)p1 =1字母為小寫 =2字母為大寫 =3字母、數(shù)字都用*代替參數(shù)p2同一字母填充

16、的個(gè)數(shù)參數(shù)p3=1按ascii遞增填充， =2按ascii遞減填充。其中原串的長(zhǎng)度不大于100。,分析,按題目要求直接模擬即可，可以邊處理邊輸出。,矩陣取數(shù)游戲 （NOIP2007-3）,對(duì)于一個(gè)給定的n*m的矩陣，矩陣中的每個(gè)元素aij為非負(fù)整數(shù)。游戲規(guī)則如下： 1. 每次取數(shù)時(shí)須從每行各取走一個(gè)元素，共n個(gè)。 m次后取完矩陣所有的元素； 2. 每次取走的各個(gè)元素只能是該元素所在行的行首或行尾； 3. 每次取數(shù)都有一個(gè)得分值，為每行取數(shù)的得分之和；每行取數(shù)的得分 = 被取走的元素值*2i，其中i表示第i次取數(shù)（從1開(kāi)始編號(hào)）； 4. 游戲結(jié)束總得分為m次取數(shù)得分之和。 求出取數(shù)后的最大得分。

17、,樣例,輸入 輸出 2 3 82 1 2 43 4 2 說(shuō)明：(1*21+2*21)+(2*22+3*22)+(3*23+4*23)=82 數(shù)據(jù)范圍： 60%的數(shù)據(jù)滿足：1=n, m=30，答案不超過(guò)1016 100%的數(shù)據(jù)滿足：1=n, m=80，0=aij=1000,分析,首先，n行求值可以獨(dú)立考慮！ 設(shè)fi,j表示區(qū)間i-j的最優(yōu)值 fi,j=maxfi+1,j+w*ai,fi,j-1+w*aj 其中w=w+w,即w*2 需要做若干次高精度加法和乘法。 直到求出，maxfi,i+w*ai，i=1.m為止。,樹(shù)網(wǎng)的核 (NOIP2007-4),給出一棵無(wú)根樹(shù)，邊上有權(quán)。稱樹(shù)的最長(zhǎng)路徑為直徑

18、，定義路徑的偏心距為：點(diǎn)到路徑的上的點(diǎn)的最小值的最大值，給出一個(gè)s，找出直徑上的某段長(zhǎng)度不超過(guò)s的路徑，使得偏心距最小。,分析,考慮到樹(shù)的性質(zhì)，對(duì)于任意兩點(diǎn)，最短路=聯(lián)通路=最長(zhǎng)路。首先用floyd算法求出任意兩點(diǎn)之間最短路。同時(shí)可以求出最長(zhǎng)路徑上都有哪些點(diǎn)。由于這是一棵樹(shù)，最短路必然唯一。設(shè)mida,b是a,b之間的聯(lián)通路上的一個(gè)中間點(diǎn)?？紤]問(wèn)題的解，構(gòu)造一個(gè)函數(shù)F(k,a,b)為K到ab間的最短路的長(zhǎng)度。則 f(k,a,b)=mindk,mida,b,fk,a,mida,b,fk,mida,b,b 寫出了這個(gè)方程，便不難得出一個(gè)三次方的算法。在實(shí)際做的時(shí)候，可以把k放在最外層枚舉，這樣內(nèi)層

19、實(shí)際上只用到了f的后面2維，用2維數(shù)組記錄即可。,笨小猴 （NOIP2008-1）,給出一個(gè)單詞,統(tǒng)計(jì)其中出現(xiàn)最多的字母出現(xiàn)的次數(shù)maxn,以及出現(xiàn)最少的字母的次數(shù)minn,如果maxn-minn是質(zhì)數(shù)的話則作為一個(gè)Lucky Word.否則即為No Answer.,分析,直接掃描每個(gè)單詞，統(tǒng)計(jì)模擬即可.,火柴棒等式 (NOIP2008-2),給你n(n=24)根火柴棒,叫你拼出 A + B = C這樣的等式,求方案數(shù).,分析,直接枚舉A和B(事實(shí)證明只到3位數(shù)),事先預(yù)處理2000以內(nèi)各個(gè)數(shù)所用的火柴數(shù).直接枚舉出解,傳紙條 (NOIP2008-3),給一個(gè)矩陣(左上角和右下角固定為0),從

20、左上角走兩次到右下角,兩次走的路徑不能有交集(即一個(gè)點(diǎn)不能被走兩次),求兩次走過(guò)的格子上的數(shù)的和最大是多少.(類似二取方格數(shù)),分析,二取方格數(shù)很經(jīng)典的題目了,于是便直接以 fi,jk,p 表示第一條路徑走到(i,j),第二條路徑走到(k,p)所取到的數(shù)的最大值. 轉(zhuǎn)移方程如下 fi,jk,p=maxfi-1,jk-1,p, fi-1,jk,p-1 fi,j-1k-1,p，fi,j-1k,p-1+ai,j+ap,k f(1,1,1,1)=a1,1,從坐標(biāo)(1,1)-(n,n)枚舉即可。 同時(shí)注意判斷兩條路不要從同一個(gè)點(diǎn)轉(zhuǎn)移過(guò)來(lái)就好了. 時(shí)間復(fù)雜度O(N4),雙棧排序 (NOIP2008-4),

21、有兩個(gè)隊(duì)列和兩個(gè)棧,分別命名為隊(duì)列1(q1),隊(duì)列2(q2),棧1(s1)和棧2(s2).最初的時(shí)候,q2,s1和s2都為空,而q1中有n個(gè)數(shù)(n=1000),為1n的某個(gè)排列.現(xiàn)在支持如下四種操作: a操作,將 q1的首元素提取出并加入s1的棧頂. b操作,將s1的棧頂元素彈出并加入q2的隊(duì)列尾. c操作,將 q1的首元素提取出并加入s2的棧頂. d操作,將s2的棧頂元素彈出并加入q2的隊(duì)列尾. 請(qǐng)判斷,是否可以經(jīng)過(guò)一系列操作之后,使得q2中依次存儲(chǔ)著1,2,3,n.如果可以,求出字典序最小的一個(gè)操作序列.,分析,第一步需要解決的問(wèn)題是,判斷是否有解. 定理: 考慮對(duì)于任意兩個(gè)數(shù)q1i和q1

22、j來(lái)說(shuō),它們不能壓入同一個(gè)棧中的充要條件p是:存在一個(gè)k,使得ijk且q1kq1iq1j.,證明,充分性：即如果滿足條件p,那么這兩個(gè)數(shù)一定不能壓入同一個(gè)棧.這個(gè)結(jié)論很顯然,使用反證法可證.假設(shè)這兩個(gè)數(shù)壓入了同一個(gè)棧,那么在壓入q1k的時(shí)候棧內(nèi)情況如下:q1iq1j因?yàn)閝1k比q1i和q1j都小,所以很顯然,當(dāng)q1k沒(méi)有被彈出的時(shí)候,另外兩個(gè)數(shù)也都不能被彈出(否則q2中的數(shù)字順序就不是1,2,3,n了).而之后,無(wú)論其它的數(shù)字在什么時(shí)候被彈出,q1j總是會(huì)在q1i之前彈出.而q1jq1i,這顯然是不正確的. 必要性：也就是,如果兩個(gè)數(shù)不可以壓入同一個(gè)棧,那么它們一定滿足條件p.這里我們來(lái)證明它

23、的逆否命題,也就是如果不滿足條件p,那么這兩個(gè)數(shù)一定可以壓入同一個(gè)棧.不滿足條件p有兩種情況:一種是對(duì)于任意iq1i;另一種是對(duì)于任意iq1j.第一種情況下,很顯然,在q1k被壓入棧的時(shí)候,q1i已經(jīng)被彈出棧.那么,q1k不會(huì)對(duì)q1j產(chǎn)生任何影響(這里可能有點(diǎn)亂,因?yàn)榭雌饋?lái),當(dāng)q1jQ1K的時(shí)候,是會(huì)有影響的,但實(shí)際上,這還需要另一個(gè)數(shù)R,滿足JKR且 q1rq1jq1k,也就是證明充分性的時(shí)候所說(shuō)的情況而事實(shí)上我們現(xiàn)在并不考慮這個(gè)r,所以說(shuō)q1k對(duì)q1j沒(méi)有影響).第二種情況下,我們可以發(fā)現(xiàn)這其實(shí)就是一個(gè)降序序列,所以所有數(shù)字都可以壓入同一個(gè)棧.這樣,原命題的逆否命題得證,所以原命題得證.

24、此時(shí),條件p為q1i和q1j不能壓入同一個(gè)棧的充要條件也得證.,解決,這樣,我們對(duì)所有的數(shù)對(duì)(i,j)滿足1 M,潛伏者（NOIP2009-1）,使用兩個(gè)數(shù)組 A 和 B, Ai 代表”原字” i 對(duì)應(yīng)的”密字”, Bi 代表”密字” i 對(duì)應(yīng)的”原字”. 首先對(duì)密文進(jìn)行一次掃描, 判斷有沒(méi)有一個(gè)密字對(duì)應(yīng)兩個(gè)原字的情況; 再對(duì)原文進(jìn)行一次掃描, 判斷有沒(méi)有一個(gè)原字對(duì)應(yīng)兩個(gè)密字的情況; 最后檢查 A, B 中是不是每一個(gè)字母的信息都有. 如果出現(xiàn)以上三種情況的任何一種就可以立即輸出 Failed. 否則直接利用 B 進(jìn)行解密.,Hankson 的趣味題（noip2009-2）,題涉及算術(shù)基本定理

25、, 素因數(shù)分解, 以及最大公約數(shù)/最小公倍數(shù)的素因數(shù)分解形式. 如果對(duì)初等數(shù)論足夠熟悉, 解決本題并不困難. 對(duì)于任意兩個(gè)整數(shù)a, b , 根據(jù)算術(shù)基本定理, 我們可以將他們唯一地寫成素?cái)?shù)的冪的乘積: a=p1a1 * p2a2 * p3a3 * * pnan b=p1b1 * p2b2 * p3b3 * * pnbn 其中pi是互不相同的素?cái)?shù)且至少整除a,b中的一個(gè), ai和 bi不同時(shí)為0. 我們稱這個(gè)形式為一個(gè)數(shù)的素因數(shù)分解形式, 求這個(gè)形式的過(guò)程叫做素因數(shù)分解.,分析,將a, b寫成素因數(shù)分解形式之后, 不難證明, 最大公約數(shù)(gcd)和最小公倍數(shù)(lcm)可以表示為: gcd(a,b

26、) = p1mina1,b1 * p2mina2,b2 * * pnminan,bn lcm(a,b) = p1maxa1,b1 * p2max a2,b2 * * pnmax an,bn 其中mina,b代表a, b中較小的數(shù), maxa,b代表a, b中較大的數(shù).,分析,至此, 思路就比較清晰了. 我們首先對(duì)a0, a1, b0, b1進(jìn)行素因數(shù)分解: a0=p1a01 * p2a02 * * pna0n a1=p1a11 * p2a12 * * pna1n b0=p1b01 * p2b02 * * pnb0n b1=p1b11 * p2b12 * * pnb1n 其中pi是互不相同的素?cái)?shù)

27、且整除a0,a1,b0,b1中的一個(gè). 很明顯, 不存在素?cái)?shù)p!=pi且p | x (否則x和b0的最小公倍數(shù)不可能為b1, 由最小公倍數(shù)的素因數(shù)分解形式很容易推出這一點(diǎn)).所以x也可以表示為pi的冪的乘積, 設(shè): x=p1x1 * p2x2 * * pnxn,分析,gcd(x,a0)=a1等價(jià)于: min(x1,a01)=a11 min(x2,a02)=a12 min(xn,a0n)=a1n lcm(x,b0)=b1等價(jià)于: max(x1,b01)=b11 max(x2,b02)=b12 max(xn, b0n)=b1n 所以我們只需要計(jì)算每一個(gè)xi的取值范圍, 設(shè)xi一共有yi個(gè)滿足條件的

28、取值, 那么由乘法原理, x一共有y1*y2*yn個(gè).,現(xiàn)在考慮如何求得xi的取值范圍. 很明顯, xi的取值相互沒(méi)有影響, 所以只需要單獨(dú)考慮每一個(gè)xi的取值范圍即可. 我們分以下幾種情況進(jìn)行討論. a0i = a1i 且b0i = b1i xi 必須大于等于a0i , 否則min(xi,a0i )b1i , 不滿足要求. 所以此時(shí)xi 的取值范圍是a0i ,b0i , 可能的取值有b0i -a0i +1個(gè). 注意, a0i b0i的時(shí)候不存在滿足條件的xi , 所以無(wú)解, 直接輸出0. a0i = a1i 且 b0i != b1i x必須等于b1i , 只有一個(gè)可能的取值. 由于題目中保證了b0 | b1, 所以不會(huì)出現(xiàn)b0i b1i的情況. a0i != a1i 且 b0i = b1i x必須等于a1i , 只有一個(gè)可能的取值. 由于題目中保證了 a1 | a0, 所以不會(huì)出現(xiàn)a0i a1i的情況. a0i != a1i 且 b0i != b1i 若此時(shí)a1i != b1i則無(wú)解, 否則x必須等于a1i , 僅有一個(gè)取, 問(wèn)題得到完美解決. 算法的效率取決于如何進(jìn)行素因數(shù)分解. 一個(gè)實(shí)現(xiàn)簡(jiǎn)單并且效率較好的方法是事先篩出sqrt(2*109)之內(nèi)的素?cái)?shù), 然后利用這些素?cái)?shù)進(jìn)行試除. 如果除不盡的話, 那么