1、青少年信息學(xué)山東省省隊選拔賽 2011 第一輪第一試競賽時間：2011 年 3 月 26 日提交源程序須加后綴注意：最終測試時，所有編譯命令均不打開任何優(yōu)化開關(guān)。對于 Pascal 語言paspaspas對于 C語言ccc對于 C+語言cppcppcpp題目名稱打地鼠計算器染色目錄shrewcalcpa可執(zhí)行文件名shrew.execal.exepa.exe輸入文件名shrew.incalc.inpa.in輸出文件名shrew.oalc.outpa.out每個測試點時限1s1s2s測試點數(shù)目102020每個測試點分值1055內(nèi)存限制512MB512MB512MB是否有部分分無無無題目類型傳統(tǒng)型

2、傳統(tǒng)型傳統(tǒng)型打地鼠【問題描述】打地鼠是這樣的一個：地面上有一些地鼠洞，地鼠們會不時從洞里探出頭來很短時間后又縮回洞中。玩家的目標(biāo)是在地鼠伸出頭時，用錘子砸其頭部，砸到的地鼠越多分?jǐn)?shù)也就越高。中的錘子每次只能打一只地鼠，如果多只地鼠同時探出頭，玩家只能通過多次揮舞錘子的方式打掉所有的地鼠。你認(rèn)為這錘子太沒用了，所以你改裝了錘子，增加了錘子與地面的接觸面積，使其每次可以擊打一片區(qū)域。如果把地面看做的方陣，其每個元素都代表一個地鼠洞，那么錘子可以覆蓋區(qū)域內(nèi)的所有地鼠洞。但是改裝后的錘子有一個缺點：每次揮舞錘子時，對于這的區(qū)域中的所有地洞，錘子會打掉恰好一只地鼠。也就是說錘子覆蓋的區(qū)域中，每個地洞必須

3、至少有 1 只地鼠，且如果某個地洞中地鼠的個數(shù)大于 1，那么這個地洞只會有 1 只地鼠被打掉，因此每次揮舞錘子時，恰好有只地鼠被打掉。由于錘子的結(jié)構(gòu)過于精密，因此在過程中你不能旋轉(zhuǎn)錘子（即不能互換 和 ）。你可以任意更改錘子的規(guī)格（即你可以任意規(guī)定 和 的大?。歉难b錘子的工作只能在打地鼠前進行（即你不可以打掉一部分地鼠后，再改變錘子的規(guī)格）。你的任務(wù)是求出要想打掉所有的地鼠，至少需要揮舞錘子的次數(shù)。H：由于你可以把錘子的大小設(shè)置為 1*1，因此本題總是有解的?！据斎敫袷健康谝恍邪瑑蓚€正整數(shù) 和 ；下面 行每行 個正整數(shù)描述地圖，每個數(shù)字表示相應(yīng)位置的地洞中地鼠的數(shù)量?！据敵龈袷健枯敵鲆?/p>

4、個整數(shù)，表示最少的揮舞次數(shù)?！緲永斎搿?1232 14 21 2 1【樣例輸出】4【樣例說明】使用 2*2 的錘子，分別在左上、左下、右上、右下?lián)]舞一次?！緮?shù)據(jù)規(guī)模和約定】對于 30%的數(shù)據(jù)，；對于 60%的數(shù)據(jù)，；對于 100%的數(shù)據(jù)，其他數(shù)據(jù)不小于 0，不大于。計算器【問題描述】你被要求設(shè)計一個計算器完成以下三項任務(wù)：1、給定、，計算的值；2、給定、，計算滿足的最小非負(fù)整數(shù) ；3、給定、，計算滿足的最小非負(fù)整數(shù) ?！据斎敫袷健枯斎氚嘟M數(shù)據(jù)。第一行包含兩個正整數(shù) 、 ，分別表示數(shù)據(jù)組數(shù)和詢問類型（對于一個測試點內(nèi)的所有數(shù)據(jù)，詢問類型相同）。以下 行每行包含三個正整數(shù) 、 、 ，描述一個

5、詢問?！据敵龈袷健繉τ诿總€詢問，輸出一行。對于詢問類型 2 和 3，如果不存在滿足條件的 ，則輸出“Orz, I cannot find x!”，注意逗號與“I”之間有一個空格?！緲永斎?】3【樣例輸出 1】212【樣例輸入 2】3 22 1 32 2 32 3 3【樣例輸出 2】210【樣例輸入 3】4 32【樣例輸出 3】01Orz, I cannot 0find x!【數(shù)據(jù)規(guī)模和約定】對于 20%的數(shù)據(jù)，；對于 35%的數(shù)據(jù)，；對于 45%的數(shù)據(jù)，；對于 100%的數(shù)據(jù)， 為質(zhì)數(shù)，。染色【問題描述】給定一棵有 個節(jié)點的無根樹和 個操作，操作有 2 類：1、將節(jié)點 到節(jié)點 路徑上所有點都

6、染成顏色 ；2、詢問節(jié)點 到節(jié)點 路徑上的顏色段數(shù)量（連續(xù)相同顏色被認(rèn)為是同一段），如“112221”由 3 段組成：“11”、“222”和“1”。請你寫一個程序依次完成這 個操作?！据斎敫袷健康谝恍邪?2 個整數(shù) 和 ，分別表示節(jié)點數(shù)和操作數(shù)；第二行包含 個正整數(shù)表示 個節(jié)點的初始顏色下面行每行包含兩個整數(shù) 和 ，表示 x 和 y 之間有一條無向邊。下面 行每行描述一個操作：“C a b c”表示這是一個染色操作，把節(jié)點 到節(jié)點 路徑上所有點（包括 和 ）都染成顏色 ；“Q a b”表示這是一個詢問操作，詢問節(jié)點 到節(jié)點 （包括 和 ）路徑上的顏色段數(shù)量?！据敵龈袷健繉τ诿總€詢問操作，輸出一行。【樣例輸入】62112252 1 2 1 123452Q C Q C Q63235351 151 25【樣例輸出】312【數(shù)據(jù)規(guī)模和約定】測試點樹的形態(tài)顏色范圍1鏈234567隨機生成891011無要求1213對于測試點 、 、，樹是這樣生成的：隨機生成一個的排列 ，設(shè)