1、金華一中信息學奧林匹克聯賽（NOIP2009）復賽模擬試題（三）一、題目概覽中文題目名稱遙控車車展拉力賽舞臺設置英文題目名稱carexhibitrallystage可執行文件名carexhibitrallystage輸入文件名car.inexhibit.inrally.instage.in輸出文件名car.outexhibit.outrally.outstage.out每個測試點時限1秒1秒1秒1秒測試點數目10101010每個測試點分值10101010比較方式全文比較全文比較全文比較全文比較二、運行內存限制運行內存上限512 M512 M512 M512 M第一題：遙控車【題目描述】平平帶著

2、韻韻來到了游樂園，看到了n輛漂亮的遙控車，每輛車上都有一個唯一的名字namei。韻韻早就迫不及待地想玩名字是s的遙控車。可是韻韻畢竟還小，她想象的名字可能是一輛車名字的前綴（也就是說能確定一個i，使s是namei的前綴），這時她就能玩第i輛車；或者是一個無中生有的名字，即s不是任何一輛車名字的前綴，這時候她什么也不能玩。你需要完成下面的任務：1.韻韻想了m個她想要的名字，請告訴她能玩多少次。2.由于管理員粗心的操作，導致每輛車的擺放位置都可能出現微小的差錯，原來第i輛車現在的位置可能是i-1、i、i+1中的任意一個（第1輛車的位置不可能是0，第n輛車的位置不可能是n+1）。請你計算出共有多少種

3、可能的排列。注：數據保證當s是namei的前綴時，i是唯一確定的。一輛車可以玩多次。【輸入格式】第一行是2個正整數n、m。接下來n行，每行1個字符串namei，表示第i輛車的名字。接下來m行，每行1個字符串s，表示韻韻想要的名字。【輸出格式】第一行輸出韻韻能玩的次數。第二行輸出共有多少種可能的排列。【輸入樣例】4 4AbcdDeFAAaaBcccAbAAAbCaBcc【輸出樣例】35對于題目涉及到的字符串嚴格區分大小寫，且長度小于255。對于20的數據 n10,m10；對于40的數據 n1000，m1000；對于100的數據 n10000，m10000。第二題：車展【題目描述】遙控車是在是太漂

4、亮了，韻韻的好朋友都想來參觀，所以游樂園決定舉辦m次車展。車庫里共有n輛車，從左到右依次編號為1，2，n，每輛車都有一個展臺。剛開始每個展臺都有一個唯一的高度hi。主管已經列好一張單子：L1 R1L2 R2Lm Rm單子上的(Li,Ri表示第i次車展將要展出編號從Li到Ri的車。為了更加美觀，展覽時需要調整展臺的高度，使參展所有展臺的高度相等。展臺的高度增加或減少1都需花費1秒時間。由于管理員只有一個人，所以只好對每個展臺依次操作。每次展覽結束后，展臺高度自動恢復到初始高度。請告訴管理員為了舉辦所有展覽，他最少需要花多少時間將展臺調整好。【輸入格式】第一行為兩個正整數n、m。第二行共n個非負整

5、數，表示第i輛車展臺的高度hi。接下來m行每行2個整數Li、Ri（LiRi）。【輸出格式】一個正整數，調整展臺總用時的最小值。【輸入樣例】6 44 1 2 13 0 91 52 63 42 2【輸出樣例】48【數據范圍】對于50的數據 n500，m1000；對于80的數據 n1000，m100000；對于100的數據n1000，m200000；答案在264以內。第三題：拉力賽【題目描述】車展結束后，游樂園決定舉辦一次盛大的山道拉力賽，平平和韻韻自然也要來參加大賽。賽場上共有n個連通的計時點，n-1條賽道（構成了一棵樹）。每個計時點的高度都不相同（父結點的高度必然大于子結點），相鄰計時點間由賽道

6、相連。由于馬力不夠，所以韻韻的遙控車只能從高處駛向低處。而且韻韻的車跑完每條賽道都需花費一定的時間。舉辦方共擬舉辦m個賽段的比賽，每次從第u個計時點到第v個計時點，當然其中有不少比賽韻韻的遙控車是不能參加的（因為要上坡）。平平想知道他能參加多少個賽段的比賽，并且想知道他完成這些賽段的總用時。【輸入格式】第一行兩個整數n，m。接下來n-1行每行3個整數a、b、t。表示韻韻的遙控車可以花t秒從第a個計時點到第b個計時點。接下來m行每行2個整數u、v，意義如描述所示。【輸出格式】第一行輸出一個正整數，表示能參加的賽段數。第二行輸出一個正整數，表示總用時。【輸入樣例】6 21 2 12 4 12 5

7、15 6 11 3 12 64 5【輸出樣例】12【提示及范圍】第一個計時點的高度是最高的；uv；對于50的數據 n1000 m1000；對于100的數據 n10000 m100000；答案小于264。第四題：舞臺設置【題目描述】游樂園決定在一個n×m的廣場上舉辦一次頒獎晚會，總管要你幫忙搭建一個舞臺。現在給你廣場的布置圖（規定地圖的上方為正北），有些位置需要布置為觀眾席（記為1），另一些是空地（記為0）。舞臺只能在空地上搭建。為了使晚會更加吸引人，平平覺得舞臺應該是朝北的h金字塔形。h金字塔形舞臺是由h個矩形舞臺相接而成的，其中后方的矩形舞臺的兩端必須超出在其前面的矩形舞臺，且最小矩形面對的朝向為舞臺的方向。下面給出幾個實例:舞臺的面積應該盡量大，輸出面積最大的朝北h金字塔形舞臺的面積。【輸入格式】第一行3個整數 n、m、h。接下來n行，每行m個0或1，中間用一個空格隔開。【輸出格式】一個整數，表示最大的朝北的h金字塔形舞臺的面積。如果沒有符合題意的h金字塔形舞臺輸出0。【輸入樣例】4 6