1、NOIP2004題目解析河南省實驗中學 羅宇龍津津的儲蓄計劃 津津的零花錢一直都是自己管理。每個月的月初媽媽給津津300元錢，津津會預算這個月的花銷，并且總能做到實際花銷和預算的相同。 為了讓津津?qū)W習如何儲蓄，媽媽提出，津津可以隨時把整百的錢存在她那里，到了年末她會加上20還給津津。因此津津制定了一個儲蓄計劃：每個月的月初，在得到媽媽給的零花錢后，如果她預計到這個月的月末手中還會有多于100元或恰好100元，她就會把整百的錢存在媽媽那里，剩余的錢留在自己手中。 津津的儲蓄計劃 例如11月初津津手中還有83元，媽媽給了津津300元。津津預計11月的花銷是180元，那么她就會在媽媽那里存200元，

2、自己留下183元。到了11月月末，津津手中會剩下3元錢。 津津發(fā)現(xiàn)這個儲蓄計劃的主要風險是，存在媽媽那里的錢在年末之前不能取出。有可能在某個月的月初，津津手中的錢加上這個月媽媽給的錢，不夠這個月的原定預算。如果出現(xiàn)這種情況，津津?qū)⒉坏貌辉谶@個月省吃儉用，壓縮預算。 現(xiàn)在請你根據(jù)2004年1月到12月每個月津津的預算，判斷會不會出現(xiàn)這種情況。如果不會，計算到2004年年末，媽媽將津津平常存的錢加上20還給津津之后，津津手中會有多少錢。 樣例一輸入： save.in29023028020030017034050 90 80 20060 輸出：save.out-7 樣例二輸入： save.in290

3、 230 280 200 300 170 330 50 90 80 200 60 輸出：save.out1580 算法分析本題是NOIP2004中最簡單的一道題目。只需要認真讀題，理解題意。單純的按照題目要求進行模擬即可。分析樣例一129010002230800032800100100420001002005300002006170301003007340-108509901080112001260輸出：-7月份 預算 現(xiàn)有 上繳 存儲分析樣例二129010002230800032800100100420001002005300002006170301003007330003008505020

4、050099060200700108080200900112008010010001260203001300輸出：13001.2+20=1580月份 預算 現(xiàn)有 上繳 存儲算法實現(xiàn)數(shù)據(jù)定義costi表示津津第i個月的花費sum表示津津在媽媽那里存的錢now表示津津當前手頭的錢ans表示輸出的答案算法實現(xiàn)程序框架讀入數(shù)據(jù)主過程輸出結果算法實現(xiàn)主過程(pascal版)Begin sum:=0; now:=0; for i:=1 to maxn do begin if now+300costi then begin ans:=-i; exit; end; now:=now+300-costi; te

5、mp:=now div 100; inc(sum,100*temp); dec(now,100*temp); end; ans:=now+trunc(sum*1.2);End;合并果子 在一個果園里，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。 每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和。可以看出，所有的果子經(jīng)過n-1次合并之后，就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。 因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節(jié)省體力。假定每個果子重量都為1，并且已知果子

6、的種類數(shù)和每種果子的數(shù)目，你的任務是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值。 輸入輸出樣例輸入： fruit.in3 1 2 9 輸出：fruit.out15 數(shù)據(jù)規(guī)模 對于30的數(shù)據(jù)，保證有n=1000： 對于50的數(shù)據(jù)，保證有n=5000； 對于全部的數(shù)據(jù)，保證有n=10000。 算法分析看到這個題目我們都會很自然的想：如果每次都取當前數(shù)量最小的兩堆果子進行合并，那么結果會不會就是最優(yōu)的呢？對，答案是肯定的！并且我們可以運用數(shù)學歸納法來證明這種策略得到的結果就是我們所求的最優(yōu)解。證明略。以上的思考過程就是一個貪心策略的過程。進一步的思考，實際上我們的方法與求

7、哈夫曼樹的方法本質(zhì)上是相同的！算法框架讀入數(shù)據(jù)主過程 1.每次從當前果子堆中選擇數(shù)量最少的兩堆 2.累加體力消耗總和 3.將這兩堆進行合并后再放回果子堆中。輸出數(shù)據(jù)算法實現(xiàn)分析建立一個數(shù)學模型，我們所需要的操作就是從一個數(shù)列中取最小值，并且在進行操作后插入一個新的值。由于本題的數(shù)據(jù)規(guī)模達到了n=10000，所以怎樣高效的實現(xiàn)取最小值和插入值成了本題的關鍵！算法實現(xiàn)一用數(shù)組和二重循環(huán)模擬實現(xiàn)。每次遍歷大小為n的數(shù)組，找到最小的值。當找夠兩個最小值后求和，并將放入數(shù)組中的任意空位。算法一的代碼實現(xiàn)(pascal版)Begin ans:=0; for i:=1 to n-1 do begin tem

8、p:=0; for j:=1 to 2 do begin min:=maxint; for k:=1 to n do if datakmin then begin min:=datak; minnumber:=k; end; inc(temp,min); dataminnumber:=maxint; end; inc(ans,temp); dataminnumber:=temp; end;End;算法一的效率分析時間復雜度 o(n2)空間復雜度 o(n)編程復雜度：低結論：由于最大數(shù)據(jù)為n=10000,所以這樣的方法太慢了！那么有沒有更好的算法呢算法二分析答案是肯定的！由于本題牽涉到了取最小值

9、的操作，我們自然想到了一種數(shù)據(jù)結構堆。那么什么是堆？它支持的操作有哪些？時間復雜度是多少？又應該怎么樣實現(xiàn)呢？堆的定義堆是一棵近似滿二叉樹，它可分為大根堆和小根堆。堆的定義是遞歸的。堆的定義： 1.二叉樹的每一個節(jié)點存儲一個元素 2.二叉樹的每一個非葉子所存儲元素的優(yōu)先級高于其兒子存儲的元素的優(yōu)先級。 堆的樣例16478953以上就是一個小根堆的樣例堆支持的三種基本操作插入值 Insert 取最小值 Getmin刪除最小值 Deletemin 堆的插入16478953例如：插入一個值為2。插入的過程中始終維護堆性質(zhì)2堆的插入16478953例如：插入一個值為2。插入的過程中始終維護堆性質(zhì)2堆的

10、插入16478953例如：插入一個值為2。插入的過程中始終維護堆性質(zhì)2堆的刪除16478953例如：刪除堆頂元素，并且始終維護堆性質(zhì)。2堆的刪除6478953例如：刪除堆頂元素，并且始終維護堆性質(zhì)。2堆的刪除6478953例如：刪除堆頂元素，并且始終維護堆性質(zhì)。2堆的刪除6478953例如：刪除堆頂元素，并且始終維護堆性質(zhì)。2堆的刪除6478953例如：刪除堆頂元素，并且始終維護堆性質(zhì)。2堆的數(shù)組實現(xiàn)由于堆有一些特殊的性質(zhì)，所以我們可以用數(shù)組來實現(xiàn)堆。tot保存堆中元素的個數(shù)heapi (1=i1時，heapi的父親存放在heapi div 2當中所以任何時刻當堆不為空的時候，堆的最小元素始終

11、存放在heap1的位置。 堆的插入操作代碼實現(xiàn)(pascal版)Procedure Insert(x:longint);var s:integer;begin inc(tot); heaptot:=x; s:=tot; while (s1)and(heapsheaps div 2) do begin swap(heaps,heaps div 2); s:=s div 2; end;End;堆的刪除操作代碼實現(xiàn)(pascal版)Procedure Delete;var s:integer;begin heap1:=heaptot; dec(tot); s:=1; while (s*2=tot)

12、do begin if (s*2=tot) or (heaps*2heapj then begin swap(heaps,heapj); s:=j; end else exit; end;end;堆的各種操作的時間復雜度分析由于用數(shù)組實現(xiàn)的堆時刻是一棵近似滿二叉樹，因此插入和刪除的操作時間復雜度僅跟這棵二叉樹的高度有關系。每次操作的復雜度為o(logN)取最小值操作的時間復雜度為o(1).有了堆這個強大的武器做保證，我們就可以快速的實現(xiàn)本題所需要的各種操作了！方法二主過程代碼實現(xiàn)(pascal版)Procedure Main;var temp: longint;begin ans:=0; fo

13、r i:=1 to n-1 do begin temp:=data1; delete; inc(temp,data1); delete; inc(ans,temp); Insert(temp); end;end;算法二的效率分析時間復雜度 o(nlogn)空間復雜度 o(n)編程復雜度：一般結論：由于最大數(shù)據(jù)為n=10000,所以這樣的方法完全可以對付所有的數(shù)據(jù)！那么有沒有更好的算法呢算法三分析答案是肯定的！注意到題目中的一個性質(zhì)：每一次合并過的果子堆的重量是遞增的。題目中給出果子范圍=20000.如果能夠從分的利用好了這兩個條件，我們將得到一種更優(yōu)的算法！算法三分析這種算法的基本思想是：利用

14、有序隊列！首先，將所有果子數(shù)讀入。由于果子數(shù)范圍小，我們可以利用桶排序在o(n)的時間內(nèi)構造一個有序隊列count同時我們把每次新產(chǎn)生的堆的數(shù)目加到另外一個隊列seq中，使seq也保持遞增的性質(zhì)。這樣每次的最小值只有可能在seq或者count的隊首取得。每次取最小值和刪除最小值的時間復雜度為o(1)當新產(chǎn)生一對果子后，利用新產(chǎn)生果子遞增的性質(zhì)，我們可以直接把它加在隊列seq的隊尾。時間復雜度為o(1).方法三演示例如當n=7,果子堆數(shù)分別為7 15 2 4 6 10 5 時，我們先進行第一步工作，用桶排序構造一個初始有序序列count. 456710152方法三演示初始數(shù)據(jù)隊列count456

15、710152新增數(shù)據(jù)隊列seqAns=0方法三演示初始數(shù)據(jù)隊列count456710152新增數(shù)據(jù)隊列seqAns=0合并6方法三演示初始數(shù)據(jù)隊列count5671015新增數(shù)據(jù)隊列seqAns=66方法三演示初始數(shù)據(jù)隊列count5671015新增數(shù)據(jù)隊列seqAns=66合并11方法三演示初始數(shù)據(jù)隊列count671015新增數(shù)據(jù)隊列seqAns=1711合并13方法三演示初始數(shù)據(jù)隊列count1015新增數(shù)據(jù)隊列seqAns=301113方法三演示初始數(shù)據(jù)隊列count1015新增數(shù)據(jù)隊列seqAns=301113合并21方法三演示初始數(shù)據(jù)隊列count1615新增數(shù)據(jù)隊列seqAns=

16、511321方法三演示初始數(shù)據(jù)隊列count1615新增數(shù)據(jù)隊列seqAns=5113合并2821方法三演示初始數(shù)據(jù)隊列count1628新增數(shù)據(jù)隊列seqAns=7921方法三演示初始數(shù)據(jù)隊列count212849新增數(shù)據(jù)隊列seqAns=79合并方法三演示初始數(shù)據(jù)隊列count49新增數(shù)據(jù)隊列seqAns=128算法三代碼實現(xiàn)桶排序(pascal版)Procedure Init;Begin Fillchar(count,sizeof(count),0); readln(n); for i:=1 to n do begin read(j); inc(countj); end; point:=

17、1;end;counti表示大小為i的數(shù)據(jù)的個數(shù)。point是count隊列的指針。算法三主過程代碼實現(xiàn)(pascal版)Procedure Main;var a,b,temp :longint;begin ans:=0; for i:=1 to n-1 do begin temp:=0; for j:=1 to 2 do begin a:=Get_count; b:=Get_seq; if ab then begin inc(temp,a); delete_count; end else begin inc(temp,b); delete_seq; end; end; inc(ans,tem

18、p); Insert_seq(temp); end;end;算法三隊列操作代碼實現(xiàn)(pascal版)Function Get_count:longint;begin while (countpoint=0) and (point20001) do inc(point); if point20001 then Get_count:=point else Get_count:=maxlongint;end;Procedure Delete_count;begin if point20001 then dec(countpoint);end;Procedure Insert_seq(x:longin

19、t);begin inc(r); seqr:=x;end;Function Get_seq:longint;begin if l=r then Get_seq:=seql else Get_seq:=maxlongint;end;Procedure Delete_seq;begin if l=r then inc(l);end;算法三的效率分析時間復雜度 o(n)空間復雜度 o(n)編程復雜度：一般！結論：這算法在各個方面都非常的優(yōu)秀那么有沒有更好的算法呢算法三小結算法三在的時間復雜度在理論上已經(jīng)是下界了，但是希望大家再思考，創(chuàng)造出同樣優(yōu)秀的算法。_另外，這道題目雖然簡單，但是在當時卻害了不少

20、人。有很多同學沒有看清楚題目要求，把這個題目做成了石子合并，敗的很慘-_-b包括本人。希望大家吸取教訓。合唱隊形 N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學排成合唱隊形。 合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2，K，他們的身高分別為T1，T2，TK，則他們的身高滿足T1.Ti+1TK(1=i=K)。 你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。輸入輸出樣例輸入： chorus.in8186 186 150 200 160 130 197 220輸出：chorus.out4樣例分析186

21、186 150 200 160 130 197 220 ans=4186 186 150 200 160 130 197 220 ans=4186 186 150 200 160 130 197 220 ans=4算法分析題目要求出列的人數(shù)最少，也就是等價于使隊列中的人數(shù)盡可能的多。考慮站在“中心位置”的同學，如果他確定了，怎樣使得隊列中的人數(shù)盡可能的多呢？顯然，必需使得他左邊的那部分隊列盡量長，同時他右邊的那部分隊列盡量長。那么怎樣使得他左邊的隊列盡量長呢？算法框架最長不下降序列！利用這個思想我們得到了算法的主框架如下:1.用動態(tài)規(guī)劃求出以每個人結尾的左邊和右邊的最大隊列長度。2.枚舉每個人

22、為“中心位置”，計算出滿足題目要求的隊列長度，記錄最大值。算法分析我們用lefti表示從左邊起到第i個人結束的最長上升隊列的人數(shù)，那么得到狀態(tài)轉(zhuǎn)移方程：lefti=maxmax(leftk)+1,1 1=k=i-1 heighkheighi同樣的，用righti表示從右邊起到第i個人結束的最大上升隊列的人數(shù)，得到：righti=maxmax(rightk)+1,1 i+1=k=n heighkheighi算法分析對于樣例，得到的left,right值如下表：數(shù)據(jù)186186150200160130197220left11122134right33232111算法實現(xiàn)(pascal版)Proce

23、dure Main;begin for i:=1 to n do begin lefti:=1; for j:=1 to i-1 do if (datajlefti) then lefti:=leftj+1; end; for i:=n downto 1 do begin righti:=1; for j:=n downto i+1 do if (datajrighti) then righti:=rightj+1; end; ans:=0; for i:=1 to n do if (lefti+righti-1)ans then ans:=lefti+righti-1;end;算法效率分析時

24、間復雜度 o(n2)空間復雜度 o(n)編程復雜度：簡單結論：這種算法足以應對所有的測試數(shù)據(jù)那么有沒有更好的算法呢算法小結答案是肯定的！如果換一種狀態(tài)表示，我們可以在二分查找的幫助下以nlogn的時間復雜度解決本題。請有興趣的同學自己進行研究學習。由于本題數(shù)據(jù)規(guī)模比較小，所以算法多種多樣。在比賽的時候有人用枚舉過了80%的數(shù)據(jù)，也是很好的。這就提醒我們要放開思路，對于每一題都要嘗試著用不同的算法去解決，分析。蟲食算所謂蟲食算，就是原先的算式中有一部分被蟲子啃掉了，需要我們根據(jù)剩下的數(shù)字來判定被啃掉的字母。來看一個簡單的例子： 43#9865#045+ 8468#6633 4444 5 506

25、978其中#號代表被蟲子啃掉的數(shù)字。根據(jù)算式，我們很容易判斷：第一行的兩個數(shù)字分別是5和3，第二行的數(shù)字是5。 蟲食算 現(xiàn)在，我們對問題做兩個限制： 首先，我們只考慮加法的蟲食算。這里的加法是N進制加法，算式中三個數(shù)都有N位，允許有前導的0。 其次，蟲子把所有的數(shù)都啃光了，我們只知道哪些數(shù)字是相同的，我們將相同的數(shù)字用相同的字母表示，不同的數(shù)字用不同的字母表示。如果這個算式是N進制的，我們就取英文字母表的前N個大寫字母來表示這個算式中的0到N-1這N個不同的數(shù)字(但是這N個字母并不一定順序地代表0到N-1)。輸入數(shù)據(jù)保證N個字母分別至少出現(xiàn)一次。 蟲食算 BADC+ CRDA DCCC上面的算

26、式是一個4進制的算式。很顯然，我們只要讓ABCD分別代表0123，便可以讓這個式子成立了。你的任務是，對于給定的N進制加法算式，求出N個不同的字母分別代表的數(shù)字，使得該加法算式成立。輸入數(shù)據(jù)保證有且僅有一組解，輸入輸出樣例輸入： alpha.in5ABCEDBDACEEBBAA輸出：alpha.out1 0 3 4 2算法分析看到題目我們的第一想法是：窮舉每一個字母所有可能的取值，然后判斷等式是否成立。然而這樣的時間復雜度是o(n!)，當n=26時顯然會超時。所以我們要改進方法。那么怎樣的方法才好呢？DFS+強剪枝！算法分析我們首先要確定的是搜索的順序。那么是按照A，B,這樣的順序搜索，還是按

27、照字母在算式中出現(xiàn)的順序計算呢？顯然后者比較好，因為它可以幫助我們在搜索的過程中進行剪枝。因此我們確定了程序的第一步，構造出一個搜索順序。按照從右到左字母在算式中的出現(xiàn)次序構造seq。算法實現(xiàn)構造搜索序列seqProcedure Creat_seq;begin seq:=; Fillchar(fz,sizeof(fz),true); for i:=n downto 1 do begin if fzs1i then begin fzs1i:=false; seq:=x+seq;end; if fzs2i then begin fzs2i:=false; seq:=x+seq;end; if fz

28、s3i then begin fzs3i:=false; seq:=x+seq;end; end;end;算法實現(xiàn)數(shù)據(jù)定義ans A.Z 表示最終答案s1,s2,s3 string 表示輸入的三個字符串x1,x2,x3 1.26 表示對應的算式number 1.26 of boolean 表示對應的數(shù)字是否出現(xiàn)finish 表示搜索是否結束算法實現(xiàn)程序框架這樣我們就得到了我們的主程序框架.Procedure search(dep:integer);var j:integer;begin if check then exit; /判斷當前的算式是否出現(xiàn)矛盾 if finish then exit

29、; if dep=0 then begin /輸出答案 finish:=true; Print; exit; end else begin for j:=n-1 downto 0 do if numberj then begin numberj:=false; ansseqdep:=j; paint(seqdep,j); search(dep-1); numberj:=true; ansseqdep:=0; paint(seqdep,-1); end; end;end;算法實現(xiàn)剪枝那么怎樣利用判斷算式是否合法來剪枝呢？我們看下面一個算式，其中?表示未知的字母. 例如 n=8,當前的算式為 4?3?7?1 + 5?3?5 ?5?5?7 1.末尾數(shù)15顯然不等于7，程序便可以剪枝 2.3+?=4 ?只可能是1或者2，但是它們都已經(jīng)出現(xiàn)過了，所以可以剪枝。 3.首位4+5=n，可以剪枝。算法實現(xiàn)剪枝(1)Function check:boolean;var p1,p2 : integer;begin check:=false; for i:=n downto 1 do begin /case one a + b = c if (x1i-1) and (x2i-1) and (x3i-1) then begin