NOIP2007提高組試題及解析.doc

NOIP2007提高組試題及解析 1.統(tǒng)計數(shù)字（count.pas/c/cpp）【問題描述】 某次科研調(diào)查時得到了n個自然數(shù)，每個數(shù)均不超過1500000000（1.5*109）。已知不相同的數(shù)不超過10000個，現(xiàn)在需要統(tǒng)計這些自然數(shù)各自出現(xiàn)的次數(shù)，并按照自然數(shù)從小到大的順序輸出統(tǒng)計結(jié)果?！据斎搿?輸入文件count.in包含n+1行； 第一行是整數(shù)n，表示自然數(shù)的個數(shù)； 第2n+1每行一個自然數(shù)。【輸出】 輸出文件count.out包含m行（m為n個自然數(shù)中不相同數(shù)的個數(shù)），按照自然數(shù)從小到大的順序輸出。每行輸出兩個整數(shù)，分別是自然數(shù)和該數(shù)出現(xiàn)的次數(shù)，其間用一個空格隔開。【輸入輸出樣例】count.in 8242451002100count.out2 34 25 1100 2【限制】 40%的數(shù)據(jù)滿足：1=n=1000 80%的數(shù)據(jù)滿足：1=n=50000 100%的數(shù)據(jù)滿足：1=n=200000，每個數(shù)均不超過1500 000 000（1.5*109）【解題思想1】顯然，此題可以用排序的方法來解決，根據(jù)n的范圍，可以看出，O(nlogn)的算法是可以接受的。【解題思想2】維護一個二叉樹，以數(shù)的大小作為節(jié)點的權(quán)值，以數(shù)的重復(fù)次數(shù)作為節(jié)點的附加信息。之后中序遍歷即可。 看起來，樹內(nèi)的節(jié)點個數(shù)應(yīng)該不到n，所以可能表現(xiàn)不錯，其算法復(fù)雜度依然為O(nlogn)【實際數(shù)據(jù)規(guī)?！客π〉模乙矝]有傳說中的卡Qsort的數(shù)據(jù)，全部都很溫柔?！痉?析】這個題目實在不能說是一道TG組的好題。實際上，個人認為題目最大的意義在于：提供了10個測試排序算法的不怎么特別好的數(shù)據(jù)。話說回來，此題是送分 題，但是送分題送的這么水，考察的也就只有OIers的細心程度了。在考試的時候，要相信有簡單的題目，要相信有直接的算法。在我的身邊就有幾個同學(xué)因為 這個題目與一等失之交臂，這是最可惜的事情。var a:array1.200001 of longint;i,j,k,m,n:longint;procedure qsort(s,t:longint);var i,j,mid,temp:longint;begini:=s;j:=t;mid:=a(s+t) div 2;while i=j dobegin while aimid do dec(j); if i=j then begin temp:=ai;ai:=aj;aj:=temp; inc(i);dec(j); end;end;if is then qsort(s,j);end;beginreadln(n);for i:=1 to n do readln(ai);qsort(1,n);an+1:=maxlongint;k:=1;for i:=2 to n+1 doif aiai-1 then begin writeln(ai-1, ,k); k:=1;endelse k:=k+1;end. 2.字符串的展開（expand.pas/c/cpp）【問題描述】 在初賽普及組的“閱讀程序?qū)懡Y(jié)果”的問題中，我們曾給出一個字符串展開的例子：如果在輸入的字符串中，含有類似于“d-h”或者“4-8”的字串，我們就 把它當作一種簡寫，輸出時，用連續(xù)遞增的字母獲數(shù)字串替代其中的減號，即，將上面兩個子串分別輸出為“defgh”和“45678”。在本題中，我們通過 增加一些參數(shù)的設(shè)置，使字符串的展開更為靈活。具體約定如下： (1) 遇到下面的情況需要做字符串的展開：在輸入的字符串中，出現(xiàn)了減號“-”，減號兩側(cè)同為小寫字母或同為數(shù)字，且按照ASCII碼的順序，減號右邊的字符嚴格大于左邊的字符。 (2) 參數(shù)p1：展開方式。p1=1時，對于字母子串，填充小寫字母；p1=2時，對于字母子串，填充大寫字母。這兩種情況下數(shù)字子串的填充方式相同。p1=3時，不論是字母子串還是數(shù)字字串，都用與要填充的字母個數(shù)相同的星號“*”來填充。 (3) 參數(shù)p2：填充字符的重復(fù)個數(shù)。p2=k表示同一個字符要連續(xù)填充k個。例如，當p2=3時，子串“d-h”應(yīng)擴展為“deeefffgggh”。減號兩邊的字符不變。 (4) 參數(shù)p3：是否改為逆序：p3=1表示維持原來順序，p3=2表示采用逆序輸出，注意這時候仍然不包括減號兩端的字符。例如當p1=1、p2=2、p3=2時，子串“d-h”應(yīng)擴展為“dggffeeh”。 (5) 如果減號右邊的字符恰好是左邊字符的后繼，只刪除中間的減號，例如：“d-e”應(yīng)輸出為“de”，“3-4”應(yīng)輸出為“34”。如果減號右邊的字符按照 ASCII碼的順序小于或等于左邊字符，輸出時，要保留中間的減號，例如：“d-d”應(yīng)輸出為“d-d”，“3-1”應(yīng)輸出為“3-1”。【輸入】 輸入文件expand.in包括兩行： 第1行為用空格隔開的3個正整數(shù)，一次表示參數(shù)p1，p2，p3。 第2行為一行字符串，僅由數(shù)字、小寫字母和減號“-”組成。行首和行末均無空格?！据敵觥?輸出文件expand.out只有一行，為展開后的字符串。【輸入輸出樣例1】expand.in 1 2 1expand.outabcs-w1234-9s-4zz abcsttuuvvw1234556677889s-4zz【輸入輸出樣例2】expand.in 2 3 2expand.outa-d-d aCCCBBBd-d【輸入輸出樣例3】expand.in 3 4 2expand.outdi-jkstra2-6 dijkstra2*6【限制】 40%的數(shù)據(jù)滿足：字符串長度不超過5 100%的數(shù)據(jù)滿足：1=p1=3，1=p2=8，1=p3=2。字符串長度不超過100解題思路:也是個水題，考察對語言的運用能力，字符串處理的技巧和仔細讀題的能力,測試數(shù)據(jù)已經(jīng)包括所有情況了，但是有些細節(jié)要想清楚，而且一些特殊的情況也要單獨測試一下，如9-a-a，-a-1;需要注意的是：首尾-的情況，要用ansistringVar p1, p2, p3, ii, jj, i, ch1, ch2: longint;s: string;procedure print(st, en: longint);begin if p3 = 1 then for ii := st to en do begin for jj := 1 to p2 do write(chr(ii); end else for ii := en downto st do begin for jj := 1 to p2 do write(chr(ii); end; end;procedure print0(st, en: longint);begin for ii := st to en do for jj := 1 to p2 do write(*);end;procedure judge;beginch1 := ord(si-1);ch2 := ord(si+1);if ch1 = 48) and (ch1 = 48) and (ch2 = 97) and (ch1 = 97) and (ch2 = 122) then begin case p1 of 1: print(ch1+1, ch2-1); 2: print(ch1-31, ch2-33); 3: print0(ch1+1, ch2-1); end; exit; end;end;write(-);end;beginreadln(p1, p2, p3);readln(s);write(s1);for i := 2 to length(s)-1 do if si = - then judgeelse write(si);writeln(slength(s);end. 3.矩陣取數(shù)游戲（game.pas/c/cpp）【問題描述】帥帥經(jīng)常更同學(xué)玩一個矩陣取數(shù)游戲：對于一個給定的n*m的矩陣，矩陣中的每個元素aij據(jù)為非負整數(shù)。游戲規(guī)則如下： 1. 每次取數(shù)時須從每行各取走一個元素，共n個。m次后取完矩陣所有的元素； 2. 每次取走的各個元素只能是該元素所在行的行首或行尾； 3. 每次取數(shù)都有一個得分值，為每行取數(shù)的得分之和；每行取數(shù)的得分 = 被取走的元素值*2i，其中i表示第i次取數(shù)（從1開始編號）； 4. 游戲結(jié)束總得分為m次取數(shù)得分之和。帥帥想請你幫忙寫一個程序，對于任意矩陣，可以求出取數(shù)后的最大得分。【輸入】 輸入文件game.in包括n+1行； 第一行為兩個用空格隔開的整數(shù)n和m。 第2n+1行為n*m矩陣，其中每行有m個用單個空格隔開【輸出】 輸出文件game.out僅包含1行，為一個整數(shù)，即輸入矩陣取數(shù)后的最大的分。【輸入輸出樣例1】game.in 2 31 2 43 4 2 game.out82【輸入輸出樣例1解釋】 第1次：第一行取行首元素，第二行取行尾元素，本次的氛圍1*21+2*21=6 第2次：兩行均取行首元素，本次得分為2*22+3*22=20 第3次：得分為3*23+4*23=56。總得分為6+20+56=82【輸入輸出樣例2】game.in 1 44 5 0 5 game.out122【輸入輸出樣例3】game.in 2 1096 56 54 46 86 12 23 88 80 4316 95 18 29 30 53 88 83 64 67 game.out316994【限制】 60%的數(shù)據(jù)滿足：1=n, m=30，答案不超過1016 100%的數(shù)據(jù)滿足：1=n, m=80，0=aijb0 then c0:=a0 else c0:=b0;x:=0;for i:=1 to c0 dobegin x:=ai+bi+x; ci:=x mod one; x:=x div one;end;if x0 then begin inc(c0); cc0:=x; end;end;procedure time(var a:num;k:longint);var i,x:longint;beginx:=0;for i:=1 to a0 do begin x:=ai*k+x; ai:=x mod one; x:=x div one; end;while x0 do begin inc(a0);aa0:=x mod one;x:=x div one;end;end;function compare(a,b:num):boolean;var i:longint;beginif a0b0 then exit(true);if b0a0 then exit(false);for i:=a0 downto 1 dobegin if aibi then exit(true); if biai then exit(false);end;exit(false);end;procedure plus(var c:num;a:num;k:longint);var i,j:longint;beginc:=a;i:=1; inc(ci,k);while ci=one dobegin ci+1:=ci+1+ci div one; ci:=ci mod one; inc(i); if c0i then c0:=i;end;end;procedure dp;var i,j:longint; max,temp:num;beginfillchar(f,sizeof(f),0);for i:=1 to m do begin fi,i0:=1; fi,i1:=ai*2; end;for i:=m-1 downto 1 dofor j:=i+1 to m do begin plus(max,fi+1,j,ai); time(max,2); plus(temp,fi,j-1,aj); time(temp,2); if compare(temp,max) then max:=temp; fi,j:=max; end;add(ans,ans,f1,m);end;procedure init;var i,j:longint;beginreadln(n,m);for i:=1 to n do begin for j:=1 to m do read(aj); readln; dp; end;end;procedure outs;var i:longint;beginwrite(ansans0);for i:=ans0-1 downto 1 dobegin write(ansi div 1000 mod 10); write(ansi div 100 mod 10); write(ansi div 10 mod 10); write(ansi mod 10);end;end;begininit;outs;end. 4.樹網(wǎng)的核（core.pas/c/cpp）【問題描述】設(shè)T=(V, E, W) 是一個無圈且連通的無向圖（也稱為無根樹），每條邊到有正整數(shù)的權(quán)，我們稱T為樹網(wǎng)（treebetwork），其中V，E分別表示結(jié)點與邊的集合，W表示各邊長度的集合，并設(shè)T有n個結(jié)點。路徑：樹網(wǎng)中任何兩結(jié)點a，b都存在唯一的一條簡單路徑，用d(a, b)表示以a, b為端點的路徑的長度，它是該路徑上各邊長度之和。我們稱d(a, b)為a, b兩結(jié)點間的距離。 D(v, P)=mind(v, u), u為路徑P上的結(jié)點。 樹網(wǎng)的直徑：樹網(wǎng)中最長的路徑成為樹網(wǎng)的直徑。對于給定的樹網(wǎng)T，直徑不一定是唯一的，但可以證明：各直徑的中點（不一定恰好是某個結(jié)點，可能在某條邊的內(nèi)部）是唯一的，我們稱該點為樹網(wǎng)的中心。 偏心距ECC(F)：樹網(wǎng)T中距路徑F最遠的結(jié)點到路徑F的距離，即 ECC(F)=maxd(v, F)，vV 任務(wù)：對于給定的樹網(wǎng)T=(V, E, W)和非負整數(shù)s，求一個路徑F，他是某直徑上的一段路徑（該路徑兩端均為樹網(wǎng)中的結(jié)點），其長度不超過s（可以等于s），使偏心距ECC(F)最小。我 們稱這個路徑為樹網(wǎng)T=(V, E, W)的核（Core）。必要時，F(xiàn)可以退化為某個結(jié)點。一般來說，在上述定義下，核不一定只有一個，但最小偏心距是唯一的。 下面的圖給出了樹網(wǎng)的一個實例。圖中，A-B與A-C是兩條直徑，長度均為20。點W是樹網(wǎng)的中心，EF邊的長度為5。如果指定s=11，則樹網(wǎng)的核為路 徑DEFG（也可以取為路徑DEF），偏心距為8。如果指定s=0（或s=1、s=2），則樹網(wǎng)的核為結(jié)點F，偏心距為12?！据斎搿?輸入文件core.in包含n行： 第1行，兩個正整數(shù)n和s，中間用一個空格隔開。其中n為樹網(wǎng)結(jié)點的個數(shù)，s為樹網(wǎng)的核的長度的上界。設(shè)結(jié)點編號以此為1，2，n。 從第2行到第n行，每行給出3個用空格隔開的正整數(shù)，依次表示每一條邊的兩個端點編號和長度。例如，“2 4 7”表示連接結(jié)點2與4的邊的長度為7。 所給的數(shù)據(jù)都是爭取的，不必檢驗?！据敵觥?輸出文件core.out只有一個非負整數(shù)，為指定意義下的最小偏心距。【輸入輸出樣例】【輸入輸出樣例1】core.in 5 21 2 52 3 22 4 42 5 3 Core.out5【輸入輸出樣例2】core.in 8 61 3 22 3 2 3 4 64 5 34 6 44 7 27 8 3 core.out5【限制】 40%的數(shù)據(jù)滿足：5=n=15 70%的數(shù)據(jù)滿足：5=n=80 100%的數(shù)據(jù)滿足：5=n=300，0=s=1000。邊長度為不超過1000的正整數(shù)解題思路:可以證明的是，如果圖中存在多條路徑，則在任何一條直徑上都存在一條core（反證法，用到直徑的距離最大性）。因此只需討論一條直徑上的core的情況即可。接著，如果一條路徑包括了一條子路徑的所有邊，那么子路徑的解不會比父路徑更優(yōu)。這一點后面將用到。 下面是算法：先尋找一條直徑：任取一點u，遍歷得到到它的最遠點u，再對u尋找一個到它的最遠點v，則路徑u-v一定是一條直徑（想想為什么），在剛才 遍歷u-v的時候記錄遍歷到每一個點的時候的前繼，那么從v出發(fā)一直尋找前繼到u，就能記錄下這一條直徑。這里復(fù)雜度是O(n)。 然后枚舉core：注意剛才說到了路徑是越長越好，因此枚舉的時候，每枚舉一個初始點，向后都盡量延伸到不超過s的距離。這樣每個初始點只確定一個枚舉對 象。對于終止點的選定可以采用一個游標的方式，當初始點從u到v掃過一遍時，游標也從u掃到了v（回想怎么求解凸多邊形最遠點對的），因此這里復(fù)雜度是O (n)。 最后求ECC：暫時刪除枚舉對象（那條路徑）上的所有邊，然后以那條路徑上的那些頂點作為源點開始遍歷圖，找到的最大距離就是該路徑的ECC。這里復(fù)雜度也將是O(n)。 因此總復(fù)雜度為O(n)+O(n)*O(n) = O(n2)，ac。線性算法： 同樣只要考慮一條直徑。先對于直徑上的頂點賦值：與該頂點連通的最遠點的距離。這樣可以構(gòu)成一個線性模型，點（記為vi）有一個值（記為fi），邊有一個值（即原來圖中vi和vi+1之間的距離，記為ei）。這一步可以O(shè)(n)完成。 接著考慮這個線性模型。枚舉過程還是和剛才一樣。假設(shè)枚舉的是va到vb這一段路徑，那么，這一段路徑的ECC應(yīng)當是以下幾個值的最大值：1) max(va,va+1.,vb); 2)max(vi+ei+ei+1+.+ea-1,ib);如果以上3個值能夠在O(1)內(nèi)回答，那么總復(fù)雜度就將是O(n)對 于1，顯然這是個RMQ模型，有一個O(n)算法（當然st的O(nlogn)也可以接受）?；蛘呖紤]到這個問題的特殊性，所有(a,b)類的詢問區(qū)間都 不是嚴格包含的（即任取詢問(a,b)(c,d)都不存在ab&cd），單調(diào)隊列也是可以采用的（而且常數(shù)小，推薦使 用） 對于2，設(shè)一個數(shù)組a1.n，ak表示max(vi+ei+.+ek-1,i fi, k + fk, j then fi, j := fi, k + fk, j;fillchar(p, sizeof(p), 0);tou := 0;max := 0;for i := 1 to n-1 do