信息學第一輪noi07山東省選

1、2007 年山東省信息學奧賽省隊選拔賽第一試一、 兔子p 時間限制 1s 內(nèi)存限制 2MB)(rabbit.pas/【問題描述】兔子有極強的繁殖能力，一對成年兔子每月能生一對幼兔， M 個月后幼兔長大成為成年兔子。M = 2 時，各月中兔子的數(shù)量就是熟悉的 Fibonacci 數(shù)列。當 M 2 時，問題會有點兒麻煩。給出 M ( 1 = M = 10 )和 D ( 1 = D= 100 ) ，求 D 個月后共有多少對兔子，假設最初只有一對兔子，并且在整個過程中沒有兔子【輸入】(rabbit.in)。一行，用空格隔開的兩個數(shù) M 和 D ，出生的幼兔經(jīng) M 個月才能長大成為成年兔子?！据敵觥?r

2、abbit.out)一個數(shù)，表示 D 個月后有多少對兔子?！緲永斎搿? 5【樣例輸出】9二、小組隊列p 時間限制 1s 內(nèi)存限制 2MB)(teas/【問題描述】隊列和優(yōu)先隊列（用堆實現(xiàn)）是常用的數(shù)據(jù)結(jié)構(gòu)，但是有一種小組隊列卻很少有人知道，盡管在生活中經(jīng)常使用。在人們素質(zhì)不是很高的地方排隊其實不是使用隊列，而是小組隊列。在人們不是很高的地方，排隊往往是這樣的：每個人都屬于一個小組，并且該小組的人非常團結(jié)。每當一個人來排隊的時候，他會先看一下前邊有沒有自己小組的成員，如果有的話，他會站到自己小組最后一個成員的后邊，如果沒有的話，是他最倒霉的時候，他必須站到整個隊列的最后。現(xiàn)在，要求寫一種數(shù)據(jù)結(jié)

3、構(gòu)來模擬小組隊列。具體問題：有 m 個小組， n 個元素(0.n-1 ) ，每個元素屬于一個小組，當元素 k進入隊列時，如果前邊有 k 所屬小組的元素，k 會排到自己小組最后一個元素的下一個位置，否則 k 排到整個隊列最后的位置。出隊的方式和普通的隊列相同，即排先出隊。邊的元素注：每個元素可能進出隊列多次。進出隊列【輸入】(team.in)第一行 m (m= 300)令最多 100 000 個。以下 m 行，每行表示一個小組。每行開始有一個 k 表示該組的元素個數(shù)(1 = k =總元素個數(shù))，接下來 k 個數(shù)，每個數(shù)表示該組的一個元素的。以下若干行（以STOP結(jié)束），每行有“ENQUEUE k

4、” 或“DEQUEUE”,前者表示元素 k 進隊,后者表示隊頭的元素出隊?！据敵觥?team.out)對應每個出隊命令，按出隊順序依次輸出出隊的元素，每個一行?！緲永斎搿?4 0 1 2 34 4 5 6 74 8 9 10 114 12 13 14 15ENQUEUE 6ENQUEUE 14ENQUEUE 1ENQUEUE 11ENQUEUE 2ENQUEUE 4ENQUEUE 13ENQUEUE 15ENQUEUE 12ENQUEUE 7ENQUEUE 9ENQUEUE 10 DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE

5、DEQUEUE ENQUEUE 8ENQUEUE 12ENQUEUE 6ENQUEUE 3ENQUEUE 5ENQUEUE 1ENQUEUE 4ENQUEUE 15 DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUE DEQUEUEDEQUEUE STOP【樣例輸出】64711191081215654范圍說明：前 30% 1=n=100 1=m=10全部 1=n=100 000 1=m=300進出隊命令=50命令=100 000三、旅行問題（trip.pas/p 時間限制 1s 內(nèi)存限制

6、 2MB）【問題描述】關于道路問題大家一定很熟悉吧。該問題和問題類似，也是關于旅行問題不同的是，該題不是 NP 問題。的，但是該問題與地球上有 n 個城市，這些城市之間有 m 條單向的道路，這些道路之間不存在回路（環(huán)）?，F(xiàn)在 CHB 先生想進行多次旅行，每次旅行可以在任意城市出發(fā)，當然，可以在任意城市結(jié)束。但是，在所有的旅行過程中，不能經(jīng)過同一城市兩次或多于兩次。問題是：CHB 先生最少需要多少次旅行，才能到達所有的城市？【輸入】(trip.in)第一行 n m。以下 m 行，每行兩個數(shù) u v，表示 u 到 v 之間有一條路。頂點標號為：0 到 n-1【輸出】(trip.out)最少的旅行次

7、數(shù)。【樣例輸入】5 84 33 20 34 24 01 20 21 0【樣例輸出】2范圍：前 30 數(shù)據(jù)，1 =n= 50 m=200全部數(shù)據(jù) 1 = n = 500 m = 50002007 年山東省信息學奧賽省隊選拔賽第二試一、 數(shù)列p 時間限制 1s 內(nèi)存限制 2MB)(shu.pas/【問題描述】有一個數(shù)列，具有這樣的性質(zhì)： a1 = 1，對于數(shù)列中的其他數(shù) ak= ai + aj （1=i=j=n現(xiàn)在給出數(shù)列的最后一個數(shù) an,求使 n 最小的數(shù)列。【輸入】(shu.in)一行，只有一個整數(shù) an ( 1 = n = 1000 )【輸出】(shu.out)第一行輸出 n 。第二行輸出

8、數(shù)列，每兩個數(shù)之間有且僅有一個空格。【樣例輸入】4【樣例輸出】31 2 4），二、邊長最大p時間限制 1s 內(nèi)存限制 2MB)(bian.pas/【問題描述】一天， Alice 想把一個長方形劃分成若干個正方形，現(xiàn)在是：如果要求劃分出來的正方形尺寸相同，那么它的邊長最大是多少？所有的數(shù)據(jù)（包括輸出結(jié)果）均以二進制形式表示?！据斎搿?bian.in)一行，分別為長方形的長 L 和寬 W ( 0 L,W 21000)，中間有一個或多個空格隔開?！据敵觥?bian.out)一行，最大的邊長?！緲永斎搿?00 1000【樣例輸出】100三、01 字符串問題p 時間限制 1s 內(nèi)存限制 2MB)(st

9、r.pas/【問題描述】大家都知道，計算機內(nèi)存中的信息是由若干個二進制位組成的，這些二進制位可以是 1 ,也可以是 0 ?，F(xiàn)在，有一個由 n 個二進制位組成的內(nèi)存，二進制位的從 1 至 n （注意從 1 開始），并給出 m 條關于內(nèi)存中位的描述，求出這些描述中有多少條是錯誤的。描述如下：每個描述是一行，由 x , y , z 三個如果 z =0，表示 x , y 中有偶數(shù)個 1 (包括 x , y )如果 z =1 ，表示x, y 中有奇數(shù)個 1 (同樣包括 x , y )如果一條描述與前邊某些正確的描述例如：，則該描述是錯誤的，否則該描述是正確的第一條 1，1，1第二條 1，1，0顯然第二條

10、是錯誤的。例如第一條 1，8，0第二條 1，4，1第三條 5，8，0也可以推出第三條是錯誤的，因為 1 到 8 之間偶數(shù)個 1，1 到 4 之間奇數(shù)個 1，5 到 8之間也應是奇數(shù)個 1，與第三條【輸入】(str.in)。第一行 n m 。 n= 50000 , m = 200000 。以下 m 行，每行 x , y , Z 三個數(shù)。 1 = x = y = n z = 1 或 0 ?！据敵觥?str.out)一個數(shù)，描述錯誤的總條數(shù)?！緲永斎搿? 10 1114 4 02 4 1【樣例輸出】32007 年山東省信息學奧賽省隊選拔賽第三試一、線性方程組p 時間限制 1s 內(nèi)存限制 2MB)(

11、gaess.pas/【問題描述】已知 n 元線性一次方程組。a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2an1x1+an2x2+annxn=bn其中： n = 50 系數(shù)是整數(shù)，絕對值=100 , bi 的值都是正整數(shù)且300。編程任務：根據(jù)輸入的數(shù)據(jù)，編程輸出方程組的解的情況?！据斎搿?gaess.in)第一行，未知數(shù)的個數(shù)。以下 n 行 n+1 列：分別表示每一格方程的系數(shù)及方程右邊的值。 na11 a12a21 a22a1n b1a2n b2an1 an2ann bn【輸出】(gaess.out)如果方程組無實數(shù)解輸出-1 ;如果有無窮多實數(shù)解，輸出

12、 0 ;如果有唯一解,則輸出解（小數(shù)點后保留兩位小數(shù)，如果解是 0,則不保留小數(shù)）【樣例輸入】32 -1 1 14 1 -1 51 1 1 0【樣例輸出】 x1=1.00 x2=0 x3=-1.00二、發(fā)電站網(wǎng)絡p 時間限制 1s 內(nèi)存限制 2MB)(electric.pas/【問題描述】網(wǎng)格計算是近年來的熱門話題之一，許多人聽，但并不清楚它的具體內(nèi)容。事實上，這一來源于電力供應網(wǎng)，發(fā)電站和用戶都連接在電力網(wǎng)中。發(fā)電站發(fā)電并把它輸入到電網(wǎng)中，用戶從電網(wǎng)中用電而不需要知道電來自于哪里。網(wǎng)格計算也是類似的工作原理。電力網(wǎng)己經(jīng)有一百多年的使用了，最近正在嘗試一種新型的電力網(wǎng)，它能覆蓋一定范圍內(nèi)的所有

13、城市并提供最大的電量。該電力網(wǎng)具有以下特點：1 所有城市均在電力網(wǎng)內(nèi)；23456一個城市至多有一個發(fā)電站，當然它應該遠離住宅區(qū)；兩個城市間至多有一條電力線路相連；電力網(wǎng)中可能存在圈，但任何一個圈中包含的城市個數(shù)不超過 3 個；基于安全方面的考慮，如果兩個城市直接相連則他們不能同時擁有發(fā)電站；每個城市的發(fā)電站都有各自能提供的最大電量。編寫程序求該電力網(wǎng)能提供的最大電量。【輸入】(electric.in)第一行：一個正整數(shù) N ( 1 = N = 100 ) ，表示電力網(wǎng)內(nèi)城市的總個數(shù)；第二行： N 個正整數(shù)(不超過 1000 ) ，表示各個城市的發(fā)電站能提供的最大電量；第三行：一個正整數(shù) M ，

14、表示電力網(wǎng)中的線路的數(shù)量；以下 M 行：每行兩個數(shù)，中間用空格隔開，表示線路連接的兩個城市?！据敵觥?electric.out)一個數(shù)：電力網(wǎng)所能提供的最大電量?！緲永斎搿?1 2 3 4 561 22 31 33 43 54 5【樣例輸出】7三、超級數(shù)組p 時間限制 1s 內(nèi)存限制 2MB)(arr.pas/【問題描述】一般的數(shù)組大家都經(jīng)常使用，相信很多同學沒有見過下面的超級數(shù)組。超級數(shù)組(1)、的是一些正整數(shù)，它還支持下面的兩個操作一個元素，命令是 i key 。 key 是要的數(shù)。(2)、輸出第 k 大元素并刪除該元素，命令是 d k。輸出第 k 大元素并刪除它?！暗?k 大”是指：現(xiàn)有的數(shù)中，如果從小到大排好序，從最小的開始作為第一大算起，一直數(shù)到第 k 個。現(xiàn)在給出一個開始是空的超級數(shù)組，請【輸入】(arr.in)好該數(shù)組。第一行 n