noip歷年復賽提高組試題

《noip歷年復賽提高組試題》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、全國信息學奧林匹克分區(qū)聯(lián)賽（NOIP）復賽提高組試題第28頁共55頁第一屆全國信息學奧林匹克分區(qū)聯(lián)賽（NOIP1995）復賽試題（提高組競賽用時：3.5小時）1、編碼問題設有一個數組A:ARRAY[0..N-1]OFINTEGER；數組中存放的元素為0～N-1之間的整數，且A[i]≠A[j]（當i≠j時）。例如：N=6時，有：A=（4，3，0，5，1，2）此時，數組A的編碼定義如下：A[0]的編碼為0；A[i]的編碼為：在A[0]，A[1]，…，A[i-1]中比A[i]的值小的個數（i=1，2，…，N-1）∴上面數組A的

2、編碼為：B=（0，0，0，3，1，2）程序要求解決以下問題：①給出數組A后，求出其編碼。②給出數組A的編碼后，求出A中的原數據。2、燈的排列問題設在一排上有N個格子（N≤20），若在格子中放置有不同顏色的燈，每種燈的個數記為N1，N2，……Nk（k表示不同顏色燈的個數）。放燈時要遵守下列規(guī)則：①同一種顏色的燈不能分開；②不同顏色的燈之間至少要有一個空位置。例如：N=8（格子數）；R=2（紅燈數）；B=3（藍燈數），放置的方法有：R-B順序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBBB-R順序BBBRRBB

3、BRRBBBRRBBBRRBBBRRBBBRR第28頁共55頁放置的方法總數為12種。數據輸入的方式為：NP1（顏色，為一個字母）N1（燈的數量）P2N2……Q（結束標記，Q本身不是燈的顏色）程序要求：求出一種順序的放置（排列）方案及放置（排列）方案總數。3、積木塊上的數字設有一個四層的積木塊，1～4層積木塊的數量依次為：5，6，7，8，如下圖所示放置：815851691423414326其中，給出第三層與第四層所標示的數字，并已知第三層的數據是由第四層的數據計算出來的。計算的方法是：第三層的某個數據A是由第四層相鄰的兩

4、個數據B，C經過某種計算后產生的：ABC計算所用到的計算符為：+，-，，且無優(yōu)先級之分（自左向右計算），運算符最多為2個。如：3+45=3554+3=23可以看出，上圖中的第三層的數據是由第四層的數據用以下計算公式計算出來的：A=BC+B也就是：8=23+2，15=34+3，……14=26+2程序要求：給出第四層與第三層的數據后，將第一、二層的每塊積木標上相應的數據，并輸出整個完整的積木圖及計算公式。①輸入數據不存在出錯的情況，同時也不會超過整數的范圍。②計算時可允許出現以下情況：A=B（即可理解為運算符的個數為零）A=

5、BB+B（即全部由B產生）第28頁共55頁第二屆全國信息學奧林匹克分區(qū)聯(lián)賽（NOIP1996）復賽試題（提高組競賽用時：3小時）1、比賽安排設有有2n（n<=6）個球隊進行單循環(huán)比賽，計劃在2n–1天內完成，每個隊每天進行一場比賽。設計一個比賽的安排，使在2n–1天內每個隊都與不同的對手比賽。例如n=2時的比賽安排：隊1234比賽1==23==4一天1==32==4二天1==42==3三天2、數制轉換設有一個字符串A$的結構為：A$=’mp’，其中m為數字串（長度<=20），而n,p均為1或2位的數字串（其中所表達

6、的內容在2-10之間）。程序要求：從鍵盤上讀入A$后（不用正確性檢查），將A$中的數字串m(n進制)，以p進制的形式輸出。例如：A$=’48<10>8’，其意義為：將10進制數48，轉換成8進制數輸出。輸出結果為：48<10>=60<8>3、挖地雷在一個地圖上有N個地窖（N<=20），每個地窖中埋有一定數量的地雷。同時，給出地窖之間的連接路徑。V1V2V3V4V5例如：【題目要求】當地窖及其連接的數據給出之后，某人可以從任一處開始挖地雷，然后可以沿著指出的連接往下挖（僅能選擇一條路徑），當無連接時挖地雷工作結束。設計一個

7、挖地雷的方案，使某人能挖到最多的地雷?！据斎敫袷健縉（表示地窖的個數）Ｗ1W2W3，……WN（表示每個地窖中埋藏的地雷數量）A12……A1NA23……A2N……AN-1N第28頁共55頁【輸出格式】K1--K2--……KV（挖地雷的順序）MAX（挖地雷的數量）例如：　　　?、猗啖堍撷奁漭斎敫袷綖椋?10，8，4，7，61110000111輸出為：1–3-4-5max=274．砝碼稱重設有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重<=1000），問可以稱為多少種不同的重量。輸入方式：a1a2a3a4a5a

8、6（分別表示1g砝碼有a1個，2g砝碼有a2個，…，20g砝碼有a6個）輸出方式：Total=N（N表示用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不用的情況）如輸入：1_1_0_0_0_0（注：下劃線表示空格）則輸出：TOTAL=3（表示可以稱出1g，2g，3g三種不同的重量。）第28頁共55頁第三屆全國信