noip歷年復(fù)賽提高組試題

《noip歷年復(fù)賽提高組試題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

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

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

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

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

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

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

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