信息學(xué)第一輪noi07山東省選

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

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

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

4、” 或“DEQUEUE”,前者表示元素 k 進(jìn)隊(duì),后者表示隊(duì)頭的元素出隊(duì)?！据敵觥?team.out)對應(yīng)每個(gè)出隊(duì)命令，按出隊(duì)順序依次輸出出隊(duì)的元素，每個(gè)一行?！緲永斎搿?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進(jìn)出隊(duì)命令=50命令=100 000三、旅行問題（trip.pas/p 時(shí)間限制 1s 內(nèi)存限制

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

7、數(shù)?！緲永斎搿? 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 年山東省信息學(xué)奧賽省隊(duì)選拔賽第二試一、 數(shù)列p 時(shí)間限制 1s 內(nèi)存限制 2MB)(shu.pas/【問題描述】有一個(gè)數(shù)列，具有這樣的性質(zhì)： a1 = 1，對于數(shù)列中的其他數(shù) ak= ai + aj （1=i=j=n現(xiàn)在給出數(shù)列的最后一個(gè)數(shù) an,求使 n 最小的數(shù)列。【輸入】(shu.in)一行，只有一個(gè)整數(shù) an ( 1 = n = 1000 )【輸出】(shu.out)第一行輸出 n 。第二行輸出

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

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

10、是錯(cuò)誤的。例如第一條 1，8，0第二條 1，4，1第三條 5，8，0也可以推出第三條是錯(cuò)誤的，因?yàn)?1 到 8 之間偶數(shù)個(gè) 1，1 到 4 之間奇數(shù)個(gè) 1，5 到 8之間也應(yīng)是奇數(shù)個(gè) 1，與第三條【輸入】(str.in)。第一行 n m 。 n= 50000 , m = 200000 。以下 m 行，每行 x , y , Z 三個(gè)數(shù)。 1 = x = y = n z = 1 或 0 ?！据敵觥?str.out)一個(gè)數(shù)，描述錯(cuò)誤的總條數(shù)?！緲永斎搿? 10 1114 4 02 4 1【樣例輸出】32007 年山東省信息學(xué)奧賽省隊(duì)選拔賽第三試一、線性方程組p 時(shí)間限制 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。編程任務(wù)：根據(jù)輸入的數(shù)據(jù)，編程輸出方程組的解的情況?！据斎搿?gaess.in)第一行，未知數(shù)的個(gè)數(shù)。以下 n 行 n+1 列：分別表示每一格方程的系數(shù)及方程右邊的值。 na11 a12a21 a22a1n b1a2n b2an1 an2ann bn【輸出】(gaess.out)如果方程組無實(shí)數(shù)解輸出-1 ;如果有無窮多實(shí)數(shù)解，輸出

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

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

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