NOIP2007題目

全國信息學奧林匹克聯賽(NOIP2007)複賽

 

提高組

題目一覽

題目名稱

統計數字

字符串的展開

矩陣取數遊戲

樹網的核

代號

count

expand

game

core

輸入文件

count.in

expand.in

game.in

core.in

輸出文件

count.out

expand.out

game.out

core.out

時限

1秒

1秒

1秒

1秒

(20071117 3小時完成)

說明:

1. 文件名(程序名和輸入輸出文件名)必須使用小寫

2. C/C++中函數main()的返回值類型必須是int,程序正常結束時的返回值必須是0。

3. 全國統一評測時採用的機器參考配置爲:CPU 2.0GHz,內存256M。

 

1統計數字

(count.pas/c/cpp)

【問題描述】

某次科研調查時得到了n個自然數,每個數均不超過1500000000(1.5109)。已知不相同的數不超過10000個,現在需要統計這些自然數各自出現的次數,並按照自然數從小到大的順序輸出統計結果。

【輸入】 輸入文件count.in包含n+1行: 第1行是整數n,表示自然數的個數。 第2~n+1行每行一個自然數。 【輸出】 輸出文件count.out包含m行(mn個自然數中不相同數的個數),按照自然數從小到大的順序輸出。每行輸出兩個整數,分別是自然數和該數出現的次數,其間用一個空格隔開。 【輸入輸出樣例】
count.in count.out
8 2 4 2 4 5 100 2 100 2 3 4 2 5 1 100 2
【限制】 40%的數據滿足:1<=n<=1000 80%的數據滿足:1<=n<=50000 100%的數據滿足:1<=n<=200000,每個數均不超過1 500 000 000(1.5
109

2.字符串的展開

(expand.pas/c/cpp)

【問題描述】

在初賽普及組的“閱讀程序寫結果”的問題中, 我們曾給出一個字符串展開的例子:如果在輸入的字符串中,含有類似於“d-h”或“4-8”的子串,我們就把它當作一種簡寫,輸出時,用連續遞增的字母或 數字串替代其中的減號,即,將上面兩個子串分別輸出爲“defgh”和“45678”。在本題中,我們通過增加一些參數的設置,使字符串的展開更爲靈活。 具體約定如下:

(1)遇到下面的情況需要做字符串的展開:在輸入的字符串中,出現了減號“-”,減號兩側同爲小寫字母或同爲數字,且按照ASCII碼的順序,減號右邊的字符嚴格大於左邊的字符。

(2)參數p1:展開方式。p1=1時,對於字母子串,填充小寫字母;p1=2時,對於字母子串,填充大寫字母。這兩種情況下數字子串的填充方式相同。p1=3時,不論是字母子串還是數字子串,都用與要填充的字母個數相同的星號“*”來填充。

(3)參數p2:填充字符的重複個數。p2=k表示同一個字符要連續填充k個。例如,當p2=3時,子串“d-h”應擴展爲“deeefffgggh”。減號兩側的字符不變。

(4)參數p3:是否改爲逆序:p3=1表示維持原有順序,p3=2表示採用逆序輸出,注意這時仍然不包括減號兩端的字符。例如當p1=1、p2=2、p3=2時,子串“d-h”應擴展爲“dggffeeh”。

(5)如果減號右邊的字符恰好是左邊字符的後 繼,只刪除中間的減號,例如:“d-e”應輸出爲“de”,“3-4”應輸出爲“34”。如果減號右邊的字符按照ASCII碼的順序小於或等於左邊字符, 輸出時,要保留中間的減號,例如:“d-d”應輸出爲“d-d”,“3-1”應輸出爲“3-1”。

【輸入】

輸入文件expand.in包括兩行:

第1行爲用空格隔開的3個正整數,依次表示參數p1,p2,p3。

第2行爲一行字符串,僅由數字、小寫字母和減號“-”組成。行首和行末均無空格。

【輸出】

輸出文件expand.out只有一行,爲展開後的字符串。

 

【輸入輸出樣例1】

expand.in

expand.out

1 2 1

abcs-w1234-9s-4zz

abcsttuuvvw1234556677889s-4zz

 

【輸入輸出樣例2】

expand.in

expand.out

2 3 2

a-d-d

aCCCBBBd-d

 

【輸入輸出樣例3】

expand.in

expand.out

3 4 2

di-jkstra2-6

dijkstra2**6

 

【限制】

40%的數據滿足:字符串長度不超過5

100%的數據滿足:1<=p1<=3, 1<=p2<=8, 1<=p3<=2。字符串長度不超過100

3. 矩陣取數遊戲

(game.pas/c/cpp)

【問題描述】 帥帥經常跟同學玩一個矩陣取數遊戲:對於一個給定的nm的矩陣,矩陣中的每個元素aij均爲非負整數。遊戲規則如下:

1. 每次取數時須從每行各取走一個元素,共n個。m次後取完矩陣所有元素;

2. 每次取走的各個元素只能是該元素所在行的行首或行尾;

3. 每次取數都有一個得分值,爲每行取數的得分之和,每行取數的得分 = 被取走的元素值2i,其中i表示第i次取數(從1開始編號);

4. 遊戲結束總得分爲m次取數得分之和。

帥帥想請你幫忙寫一個程序,對於任意矩陣,可以求出取數後的最大得分。

【輸入】

輸入文件game.in包括n+1行:

第1行爲兩個用空格隔開的整數nm

第2~n+1行爲nm矩陣,其中每行有m個用單個空格隔開的非負整數。

【輸出】

輸出文件game.out僅包含1行,爲一個整數,即輸入矩陣取數後的最大得分。

【輸入輸出樣例1】
game.in game.out
2 3 1 2 3 3 4 2 82

 

【輸入輸出樣例1解釋】 第1次:第1行取行首元素,第2行取行尾元素,本次得分爲1
21+221=6 第2次:兩行均取行首元素,本次得分爲222+322=20 第3次:得分爲323+4*23=56。總得分爲6+20+56=82

 

【輸入輸出樣例2】
game.in game.out
1 4 4 5 0 5 122

 

【輸入輸出樣例3】
game.in game.out
2 10 96 56 54 46 86 12 23 88 80 43 16 95 18 29 30 53 88 83 64 67 316994

 

【限制】

60%的數據滿足:1<=n, m<=30, 答案不超過1016

100%的數據滿足:1<=n, m<=80, 0<=aij<=1000

4. 樹網的核

(core.pas/c/cpp)

【問題描述】

T=(V, E, W) 是一個無圈且連通的無向圖(也稱爲無根樹),每條邊帶有正整數的權,我們稱T爲樹網(treenetwork),其中V, E分別表示結點與邊的集合,W表示各邊長度的集合,並設Tn個結點。

路徑:樹網中任何兩結點a,b都存在唯一的一條簡單路徑,用d(a,b)表示以a,b爲端點的路徑的長度,它是該路徑上各邊長度之和。我們稱d(a,b)a,b兩結點間的距離。

一點v到一條路徑P的距離爲該點與P上的最近的結點的距離:

d(vP)=min{d(vu)u爲路徑P上的結點}

樹網的直徑:樹網中最長的路徑稱爲樹網的直徑。對於給定的樹網T,直徑不一定是唯一的,但可以證明:各直徑的中點(不一定恰好是某個結點,可能在某條邊的內部)是唯一的,我們稱該點爲樹網的中心。

偏心距ECC(F):樹網T中距路徑F最遠的結點到路徑F的距離,即

任務:對於給定的樹網T=(V, E,W)和非負整數s,求一個路徑F,它是某直徑上的一段路徑(該路徑兩端均爲樹網中的結點),其長度不超過s(可以等於s),使偏心距ECC(F)最小。我們稱這個路徑爲樹網T=(V,E,W)核(Core。必要時,F可以退化爲某個結點。一般來說,在上述定義下,核不一定只有一個,但最小偏心距是唯一的。

下面的圖給出了樹網的一個實例。圖中,A-B與A-C是兩條直徑,長度均爲20。點W是樹網的中心,EF邊的長度爲5。如果指定s=11,則樹網的核爲路徑DEFG(也可以取爲路徑DEF),偏心距爲8。如果指定s=0(或s=1、s=2),則樹網的核爲結點F,偏心距爲12。

【輸入】

輸入文件core.in包含n行:

第1行,兩個正整數ns,中間用一個空格隔開。其中n爲樹網結點的個數,s爲樹網的核的長度的上界。設結點編號依次爲1, 2, ..., n

從第2行到第n行,每行給出3個用空格隔開的正整數,依次表示每一條邊的兩個端點編號和長度。例如,“2 4 7”表示連接結點2與4的邊的長度爲7。

所給的數據都是正確的,不必檢驗。

【輸出】

輸出文件core.out只有一個非負整數,爲指定意義下的最小偏心距。

 

【輸入輸出樣例1】

core.in

core.out

5 2

1 2 5

2 3 2

2 4 4

2 5 3

5

 

【輸入輸出樣例2】

core.in

core.out

8 6

1 3 2

2 3 2

3 4 6

4 5 3

4 6 4

4 7 2

7 8 3

5

 

【限制】

40%的數據滿足:5<=n<=15

70%的數據滿足:5<=n<=80

100%的數據滿足:5<=n<=300, 0<=s<=1000。邊長度爲不超過1000的正整數

相關日誌