noip06-09試題分析.ppt

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

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

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

4、,j表示從第i顆珠子一直合并到第j顆珠子所能產生的最大能量，則： 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)，所以總的時間復雜度為O(n4)，而n可能有100，因此直接實現(xiàn)這個算法有超時的危險。,在上式中，我們的方程只和珠子的標記(即Si)有關，而與編號無關，因此，珠子從1到n編號和2到n+1編號是等效的?，F(xiàn)在不枚舉p，令Si=Si mod n (n=i=2n)，仍用上面的方程計算，則計算所得的G1,n為從第一顆珠子前斷開時最優(yōu)值，而G2,n+1計算的正好是

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

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

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

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

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

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

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

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

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

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

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

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

17、,樣例,輸入 輸出 2 3 82 1 2 43 4 2 說明：(1*21+2*21)+(2*22+3*22)+(3*23+4*23)=82 數(shù)據(jù)范圍： 60%的數(shù)據(jù)滿足：1=n, m=30，答案不超過1016 100%的數(shù)據(jù)滿足：1=n, m=80，0=aij=1000,分析,首先，n行求值可以獨立考慮！ 設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為止。,樹網的核 (NOIP2007-4),給出一棵無根樹，邊上有權。稱樹的最長路徑為直徑

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

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

20、左上角走兩次到右下角,兩次走的路徑不能有交集(即一個點不能被走兩次),求兩次走過的格子上的數(shù)的和最大是多少.(類似二取方格數(shù)),分析,二取方格數(shù)很經典的題目了,于是便直接以 fi,jk,p 表示第一條路徑走到(i,j),第二條路徑走到(k,p)所取到的數(shù)的最大值. 轉移方程如下 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,從坐標(1,1)-(n,n)枚舉即可。 同時注意判斷兩條路不要從同一個點轉移過來就好了. 時間復雜度O(N4),雙棧排序 (NOIP2008-4),

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

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

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

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

25、, 素因數(shù)分解, 以及最大公約數(shù)/最小公倍數(shù)的素因數(shù)分解形式. 如果對初等數(shù)論足夠熟悉, 解決本題并不困難. 對于任意兩個整數(shù)a, b , 根據(jù)算術基本定理, 我們可以將他們唯一地寫成素數(shù)的冪的乘積: a=p1a1 * p2a2 * p3a3 * * pnan b=p1b1 * p2b2 * p3b3 * * pnbn 其中pi是互不相同的素數(shù)且至少整除a,b中的一個, ai和 bi不同時為0. 我們稱這個形式為一個數(shù)的素因數(shù)分解形式, 求這個形式的過程叫做素因數(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ù).,分析,至此, 思路就比較清晰了. 我們首先對a0, a1, b0, b1進行素因數(shù)分解: a0=p1a01 * p2a02 * * pna0n a1=p1a11 * p2a12 * * pna1n b0=p1b01 * p2b02 * * pnb0n b1=p1b11 * p2b12 * * pnb1n 其中pi是互不相同的素數(shù)

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

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