信息學(xué)山東第二試

1、第二試競賽時間：2010 年 4 月 18 日上午 8:00-12:30提交源程序需加后綴注意：最終測試時，所有編譯命令均不打開任何優(yōu)化開關(guān)對于 Pascal 語言goblin.pasu.passtarrace.pas對于 C 語言goblin.csusu.cstarrace.c對于 C+語言goblin.cppsusu.cppstarrace.cpp題目名稱地精部落的書架星際競速提交文件名goblinsusustarrace輸入文件名goblin.insusu.instarrace.in輸出文件名goblin.outsusu.outstarrace.out每個測試點時限1s3s3s內(nèi)存限制1

2、28M512M128M測試點數(shù)目101010每個測試點分值101010是否有部分分無無無題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)第二試 地精部落 goblin地精部落【問題描述】很久以前，大地上居住著一種神秘的生物：地精。地精喜歡住在連綿不絕的山脈中。具體地說，一座長度為 N 的山脈 H 可分為從左到右的 N 段，每段有一個獨一無二的高度 Hi，其中 Hi 是 1 到 N 之間的正整數(shù)。如果一段山脈比所有與它相鄰的山脈都高，則這段山脈是一個山峰。位于邊緣的山脈只有一段相鄰的山脈，其他都有兩段（即左邊和右邊）。類似地，如果一段山脈比所有它相鄰的山脈都低，則這段山脈是一個山谷。地精們有一個共同的飲酒，酒館可以設(shè)立在山

3、谷之中。地精的酒館不論白天黑夜總是人聲鼎沸，地精美酒的香味可以飄到方圓數(shù)里的地方。地精還是一種非常警覺的生物，他們在每座山峰上都可以設(shè)立瞭望臺，并輪流擔(dān)當(dāng)瞭望工作，以確保在第一時間得知外敵的。地精們希望這 N 段山脈每段都可以修建瞭望臺或酒館的其中之一，只有滿足這個條件的整座山脈才可能有地精居住?，F(xiàn)在你希望知道，長度為 N 的可能有地精居住的山脈有多少種。兩座山脈 A和 B 不同當(dāng)且僅當(dāng)存在一個 i，使得 AiBi。由于這個數(shù)目可能很大，你只對它除以 P 的余數(shù)感?！据斎敫袷健枯斎胛募?goblin.in 僅含一行，兩個正整數(shù) N, P?！据敵龈袷健枯敵鑫募?goblin.out 僅含一行，一

4、個非負(fù)整數(shù)，表示你所求的之后的結(jié)果。對 P 取余【樣例輸入輸出】說明：共有 10 種可能的山脈，它們是：1324314214233241214334122314413224134231其中加下劃線的數(shù)位表示可以設(shè)立瞭望臺的山峰，其他表示可以設(shè)立酒館的山谷。【數(shù)據(jù)規(guī)模和約定】對于 20%的數(shù)據(jù)，滿足 N10；對于 40%的數(shù)據(jù)，滿足 N18；對于 70%的數(shù)據(jù)，滿足 N550；對于 100%的數(shù)據(jù)，滿足 3N4200，P109。第 2 頁 共 6 頁goblin.ingoblin.out4 73第二試的書架 susu的書架【問題描述】B29 班的是一個聰明機(jī)靈、乖巧可愛的小朋友，是畫畫和讀書，尤

5、其喜歡 Thomas H. Cormen 的文章。家中有一個 R 行 C 列的巨型書架，書架的每一個位置都擺有一本書，上數(shù)第 i 行、左數(shù)第 j 列擺放的書有 Pi,j 頁厚。每天除了讀書之外，還有一件必不可少的工作就是摘蘋果，她每天必須一個指定的蘋果。家果樹上的蘋果有的高、有的低，但無論如何憑自己的個頭都難以摘到。不過她發(fā)現(xiàn)，如果在腳下放上幾本書，就可以夠著蘋果；她同時注意到，對于第 i 天指定的那個蘋果，只要她腳下放置書的總頁數(shù)之和不低于 Hi，就一定能夠摘到。由于書架內(nèi)的書過多，父母擔(dān)心一天內(nèi)就把所有書看完而耽誤了上幼兒園，于是每天只允許在一個特定區(qū)域內(nèi)拿書。這個區(qū)域是一個矩形，第 i

6、天給定區(qū)域的左上角是上數(shù)第 x1i 行的左數(shù)第 y1i 本書，右下角是上數(shù)第 x2i 行的左數(shù)第 y2i 本書。換句話說，在這一天，只能在這x2ix1i1y2iy1i1本書中挑選若干本墊在腳下，蘋果。每次取書時都放回原位，并且書架不會再撤下書目或換上新書，摘蘋果的任務(wù)會一直持續(xù) M 天。給出每本書籍的頁數(shù)和每天的區(qū)域限制及采摘要求，請你告訴果。，她每天至少拿取多少本書，就可以摘到當(dāng)天指定的蘋【輸入格式】輸入文件 susu.in 第一行是三個正整數(shù) R, C, M。接下來是一個 R 行 C 列的矩陣，從上到下、從左向右依次給出了每本書的頁數(shù) Pi,j。接下來 M 行，第 i 行給出正整數(shù) x1i

7、, y1i, x2i, y2i, Hi，表示第 i 天的指定區(qū)域是x1i, y1i與x2i, y2i間的矩形，總頁數(shù)之和要求不低于 Hi。保證 1x1ix2iR，1y1iy2iC?！据敵龈袷健枯敵鑫募?susu.out 有 M 行，第 i 行回答在第 i 天時為摘到蘋果至少需要拿取多少本書。如果即使取走所有書都無法摘到蘋果，則在該行輸出“Poor QLW”（不含引號）?！緲永斎胼敵?1】第 3 頁 共 6 頁susu.insusu.out5 5 79 7 9 3238 46 26 43 3832 7 9 50 286152Poor QLW 9第二試的書架 susu【樣例輸入輸出 2】【數(shù)據(jù)規(guī)

8、模和約定】對于 10%的數(shù)據(jù)，滿足 R, C10；對于 20%的數(shù)據(jù)，滿足 R, C40；對于 50%的數(shù)據(jù)，滿足 R, C200，M200,000；另有 50%的數(shù)據(jù)，滿足 R1，C500,000，M20,000；對于 100%的數(shù)據(jù)，滿足 1Pi,j1,000，1Hi2,000,000,000。第 4 頁 共 6 頁susu.insusu.out1 10 79 7 9 321 41 1 1 1Poor QLW 128 41 9 75 5 3993 3 4 5 9113第二試 星際競速 starrace星際競速【問題描述】10 年一度的系大賽又要開始了。作為全最盛大的活動之一，奪得這個項目的

9、冠軍無疑是很多人的夢想，來自座 星的悠悠也是其中之一。大賽的賽場由 N 顆行星和 M 條雙向星際航路，其中每顆行星都有一個不同的引力值。大賽要求車手們從一顆與這 N 顆行星之間沒有任何航路的天體出發(fā)，這 N 顆行星每顆恰好一次，首先完成這一目標(biāo)的人獲得勝利。由于賽制非常開放，很多人駕駛著千奇百怪的來參賽。這次悠悠駕駛的名為超能，這是一部凝聚了全最尖端科技結(jié)晶的夢幻。作為最高科技的產(chǎn)物，超能在高速航行模式下，超能有兩種移動模式：高速航行模式和能力爆發(fā)模式。會展開反物質(zhì)引擎，以數(shù)倍于光速的速度沿星際航路高速航行。在能力爆發(fā)模式下，超能脫離時空的，使用超能力進(jìn)行空間跳躍在經(jīng)過一段時間的定位之后，它能

10、瞬間移動到任意一個行星。天不遂人愿，在比賽的前一天，超能在一場離子風(fēng)暴中不幸受損，機(jī)能出現(xiàn)了一些：在使用高速航行模式的時候，只能由每個星球飛往引力比它大的星球，否則就會發(fā)生。盡管心愛的出了問題，但是悠悠仍然堅信自己可以取得勝利。他找到了全最聰明的賢者你，請你為他安排一條比賽的方案，使得他能夠用最少的時間完成比賽?！据斎敫袷健枯斎胛募?starrace.in 的第一行是兩個正整數(shù) N, M。第二行 N 個數(shù) A1AN，其中 Ai 表示使用能力爆發(fā)模式到達(dá)行星 i 所需的定位時間。接下來 M 行，每行 3 個正整數(shù) ui, vi, wi，表示在在一條需要航行 wi 時間的星際航路。為 ui 和 v

11、i 的行星之間存輸入數(shù)據(jù)已經(jīng)按引力值排序，也就是兩顆行星引力值相同。小的行星引力值一定小，且不會有【輸出格式】輸出文件 starrace.out 僅包含一個正整數(shù)，表示完成比賽所需的最少時間?！緲永斎胼敵?1】說明：先使用能力爆發(fā)模式到行星 1，花費時間 1。然后切換到高速航行模式，航行到行星 2，花費時間 10。第 5 頁 共 6 頁starrace.instarrace.out3 31 100 1002 1 101 3 12 3 112第二試 星際競速 starrace之后繼續(xù)航行到行星 3 完成比賽，花費時間 1。 雖然看起來從行星 1 到行星 3 再到行星 2 更優(yōu)，但卻不能那樣做，因為那會導(dǎo)致超能。【樣例輸入輸出 2】說明：這個例子中，始終使用能力爆發(fā)模式完成比賽。【樣例輸入輸出 3】【數(shù)據(jù)規(guī)模和約定】對于 30%的數(shù)據(jù) N20，M50；對于 70%的數(shù)據(jù) N200，M4000；對于100%的數(shù)據(jù)N