全國賽師大附中集訓(xùn)測驗

1、1 網(wǎng)絡(luò)改造(network)【背景描述】HURRICANE 小組原來構(gòu)建的網(wǎng)絡(luò)由網(wǎng)絡(luò)上的交換機(jī)及其間的網(wǎng)路。交換機(jī)分級連接，的為頂級的網(wǎng)關(guān)交換機(jī)，其他交換機(jī)分級相連到該網(wǎng)關(guān)交換機(jī)上。但值得注意的是，任一臺非網(wǎng)關(guān)交換機(jī)與一臺高一級的交換機(jī)直接相連。而任一臺交換機(jī)均可以與幾臺低一級的交換機(jī)直接相連。但最近，由于原來架設(shè)的網(wǎng)絡(luò)服務(wù)有限，需要把網(wǎng)絡(luò)中的一些交換機(jī)（包括網(wǎng)關(guān)交換機(jī)）升級為 交換機(jī)。由于改造的時間所限，只來得及把不超過 p臺（含 p 臺）交換機(jī)升級為 交換機(jī)，而所有剩下的交換機(jī)則需要通過改造網(wǎng)路的方法和這幾臺 交換機(jī)直接連接。但是無論是升級交換機(jī)還是改造網(wǎng)絡(luò)都需要花費一定的?，F(xiàn)在請你給出

2、一個改造網(wǎng)絡(luò)的方案。使得按照該方案升級后每一個交換機(jī)要么是交換機(jī)，要么直接和交換機(jī)相連。并且要求提供的方案使改造所用的總費用最小?！救蝿?wù)描述】你的程序必須根據(jù)給定的輸入，給出符合題意的輸出：輸入包括網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，升級網(wǎng)絡(luò)中每臺交換機(jī)的費用，以及改造網(wǎng)絡(luò)的費用，還有可以升級的交換機(jī)的最大數(shù)目p；你必須根據(jù)輸入，找出一個升級的方案，滿足升級后的交換機(jī)的數(shù)目不超過給定的可升級交換機(jī)最大值 p，且使得總費用最少；其中總費用的計算包括兩個部分：一部分是升級交換機(jī)為交換機(jī)所需要的費用，該部分的費用按照所有的需要升級的交換機(jī)所需的費用之和來計算；另一部分是改造網(wǎng)絡(luò)所需要的費用，該部分的費用按照所有未升級的

3、交換機(jī)到最近的交換機(jī)的網(wǎng)絡(luò)路徑距離之和來計算；注意：當(dāng)網(wǎng)絡(luò)中沒有任何交換機(jī)升級到交換機(jī)的時候，由于也沒有交換機(jī)可以連接到交換機(jī)，所以無窮大。定義此時的總費用為【輸入格式】：(network.in)第一行為兩個正整數(shù) n（n 400）和 p，分別表示網(wǎng)絡(luò) 換機(jī)的數(shù)目（交換機(jī)按照 1 到 n 標(biāo)號）和可升級交換機(jī)的最大值。接下來的 n 行每行一個正整數(shù)ci，表示把標(biāo)號為 i 的交換機(jī)升級為交換機(jī)所需要的費用。接下來的 n-1 行每行三個正整數(shù) i、j、di,j（dij 20000），表示為 j 的交換機(jī)為為 i 的交換機(jī)的上層交換機(jī)，而di,j 表示兩臺交換機(jī)之間的網(wǎng)路距離。【輸入樣例】【輸出格式

4、】：(network.out)你的輸出第一行為一個整數(shù) M，表示你的方案的最小總費用。接下來一行包括一個整數(shù) p0，表示你的方案所需要升級為交換機(jī)的交換機(jī)數(shù)目?！据敵鰳永俊具\行限制】【評分方法】本題目一共有十個測試點，每個測試點的分?jǐn)?shù)為總分?jǐn)?shù)的 10%。對于每個測試點來說，如果你的分。正確，那么你將得到該測試點全部的分?jǐn)?shù)，否則得 0注意，本題目的測試數(shù)據(jù)中有 8 個數(shù)據(jù)的 n 不超過。每點運行時間1 秒內(nèi)存使用128M30222 1 23 2 46 5 27 5 9542 月亮森林【問題描述】一天早晨，一個小在森林里玩耍時看到一顆神奇的，光芒四射，還散發(fā)著一股淡淡的清香。很喜歡這顆，便把它捧

5、在手里帶回了家。那天晚上，她說，她手里的做了一個夢，夢到一個面目慈祥的老。老對來自一棵月亮之樹，原本只有在月亮上才能見到它，但是機(jī)緣巧合，喜歡這顆悄悄的落在了地球上，無法再回到月亮上了。老發(fā)現(xiàn)兒很種出，就問她是否愿意借助自己的勤勞和智慧，用這顆小小的一片茂密的月亮森林，讓月亮樹在地球上有一個溫暖的新家興奮地點點頭，忙問老具體應(yīng)該怎么做。老人解釋說，這顆非同尋常，種下去的第二天上午就會長成一棵高度為1(一個)的小樹苗。月亮樹的生命力極強，以后還會每天上午長高一個。由于月亮樹不同于地球上的生物，必須使用一種特殊的肥料才能對它施肥，而這種肥料老每天會送給兒一個。每天晚上，她必須給一棵樹或者下午剛種下

6、去的施肥，但不能多施肥，也不能不施肥。被施肥的樹或者在第二天上午將比一般情況下多長高一個，即兩個。月亮樹在成長的過有兩個稱為“收獲點”的特殊高度，分別為 HP1 和 HP2。當(dāng)月亮之樹的高度第一次達(dá)到或者超過 HP1 的那天中午，樹上就會結(jié)出一個果實。同樣，當(dāng)高度第一次達(dá)到或者超過 HP2 的那天中午，樹上也會結(jié)出一個果實。果實里面有一顆種子, 和當(dāng)初撿到的一模一樣。每天下午，都可以選擇一些種下去，種了恰好 M 棵樹，且它們的高度都相同時，這些樹才當(dāng)然也可以不種。當(dāng)能真正的適應(yīng)地球的環(huán)境，的活下去。醒來后的那天下午，兒就按照老的吩咐把種下去了。她把完成老交付給任務(wù)作為一生中最大的心愿，日復(fù)一日

7、，年復(fù)一年辛勤的勞動著。她每天傍晚一坐在門檻上望著遠(yuǎn)方，眼前就會浮現(xiàn)出一片美麗而寬廣的月亮森林。她堅信自己一定能成功，需要再長的時間也不怕。但是這一天何時才會來到呢？【輸入文件】輸入文件forest.in 僅包含三個整數(shù) HP1,HP2,M（2=HP1HP2=20, 2=M=100）,代表兩個收獲點的高度和所需月亮樹的棵數(shù)。【輸出文件】輸出文件forest.out 僅包含一個整數(shù)T，即最少需要的天數(shù)。【輸入輸出樣例 1】【輸入輸出樣例 2】forest.out84forest.in10156forest.out12forest.in4933 家園(HOMELAND.EXE)由于人類對自然的瘋狂

8、破們在大約 2300 年之后，地球不能再居住了，于是在月球上建立了新的綠地，以便在需要時。令人意想不到的是，2177 年冬由于未知的原因，地球環(huán)境發(fā)生了連鎖內(nèi)遷往月球。，人類必須在最短的時間現(xiàn)有n 個太空站處于地球與月球之間（1.n），m 艘公共交通太空船在其中來回穿梭，每個太空站 Si 可容納無限的人，每艘太空船 pi 只可容納 Hpi 人。對于每一艘太空船pi，將周期性地?？恳幌盗械奶照荆⊿i1,Si2Sir），如：（1， 3，4）表示?？刻照?1 3 4 1 3 4 1 3 4 。 任一艘太空船從任一個太空站駛往另一個任意的太空站耗時為 1。人只能在太空船停靠太空站（或地球、月球）時上船或下船。初始時的人全在地球上，太空船全在初始站（太空船 pi 處于Si1），目標(biāo)是讓所有的人盡快地全部轉(zhuǎn)移到月球上。輸入：文件第一行為三個正整數(shù) n（太空站個數(shù)）、 m（太空船個數(shù)）、 k（需要運送的地球上的人的個數(shù)），其中 1=m=13, 1=n=20, 1=k=50。接下來的 n 行給出了太空船的信息，第 i+1 行說明太空船 pi，此行第一個數(shù)表示 pi 可容納的人數(shù) Hpi，第二個數(shù)表示 pi 停靠一個周期的太空站個數(shù) r，1=r=n+2, 隨后r 個數(shù)便是?？康奶照镜?Si1,Si2,Sir), 地球用 0 表示，月球用-