1995-2008-历届NOIP试题及详解

1995-2008NOIP复赛试题第1页|共209页提示：文档已分节，可用word跳转节功能本文为本人将1995-2008年历届NOIP试题、研究成果整理而成，由于“年代久远”所以有不少资料没有找到。但本人都尽量整理最有价值的信息记录于此。资料来源皆为网络，若引用请注明出处一不注意就208页了呢~其实最初只是想方便自己，看着一下午的成果，就忍不住放到了网络上。由于赶时间，质量不太好，而且历届NOIP的排版也不一样，只是做了粗略的整理、排版，若有错误之处，敬请谅解。回首历届NOIP，甚至比我自己出生的还早的老题，一代代OIer就从这条路上走过，作为一个不大努力的OIer，我甚至为自己感到愧疚。总之，为了报答一代代出题人、教师、主办方以及OIer们，在努力一把也不迟啊。By2014年8月15日（农历二〇一四年七月二十）星期五东营市胜利一中梅如歌NOIP1995普及组复赛测试数据第2页|共209页OI’95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（初中组）（上机编程，完成时间：210分钟）1设有下列的算式：809-------------□□)□□□□□□-------------□□□□□□-------------1求出□中的数字，并打印出完整的算式来。2方阵填数：在一个NN的方阵中，填入1，2，……NN个数，并要求构成如下的格式：例：3若将一个正整数化为二进制数，在此二进制数中，我们将数字1的个数多于数字0的个数的这类二进制数称为A类数，否则就称其为B类数。例如：（13）10=（1101）2其中1的个数为3，0的个数为1，则称此数为A类数；（10）10=（1010）2其中1的个数为2，0的个数也为2，称此数为B类数；（24）10=（11000）2其中1的个数为2，0的个数为3，则称此数为B类数；程序要求：求出1～1000之中（包括1与1000），全部A、B两类数的个数。4编码问题：设有一个数组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；N=513141516112232417211222518310212019498765N=6161718192011530313221214293633223132835342341227262524511109876NOIP1995普及组复赛测试数据第3页|共209页A[i]的编码为：在A[0]，A[1]，……A[i-1]中比A[i]的值小的个数（i=1，2……N-1）∴上面数组A的编码为：B=（0，0，0，3，1，2）程序要求解决以下问题：①给出数组A后，求出其编码；②给出数组A的编码后，求出A中的原数据。5灯的排列问题：设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……Nk（k表示不同颜色灯的个数）。放灯时要遵守下列规则：①同一种颜色的灯不能分开；②不同颜色的灯之间至少要有一个空位置。例如：N=8（格子数）R=2（红灯数）B=3（蓝灯数）放置的方法有：R-B顺序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBBB-R顺序BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR放置的总数为12种。数据输入的方式为：NP1（颜色，为一个字母）N1（灯的数量）P2N2……Q（结束标记，Q本身不是灯的颜色）程序要求：求出一种顺序的排列方案及排列总数。NOIP1995普及组复赛测试数据第4页|共209页NOI’95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛测试数据（初中组）1正确算式如下：8分809①打印格式占4%9709②算式不对不给分9610910812本题18分（4%+6%+8%）①输入N=1（4%）②输入N=3（6%）结果：结果：1781692543③输入N=10（8%）结果：2829303132333435361275859606162636437226578081828384653832556799495968566394245578931009786674052354779299988768416225376919089886942721527574737271704382051504948474645449191817161514131211103本题14分输出结果为：A类=538B类=4624本题30分（15%+15%）①由数组求编码：共15分（5%+5%+5%）a输入：N=6A=（0，1，2，3，4，5）输出：B=（0，1，2，3，4，5）12）NOIP1995普及组复赛测试数据第5页|共209页b输入：N=6A=（5，4，3，2，1，0）输出：B=（0，0，0，0，0，0）c输入：N=8A=（1，0，3，2，5，4，7，6）输出：B=（0，0，2，2，4，4，6，6）②由编码求原数组：共15分（5%+5%+5%）a输入：N=5B=（0，0，0，0，0）输出：A=（4，3，2，1，0）b输入：N=10B=（0，1，2，3，4，5，6，7，8，9）输出：A=（0，1，2，3，4，5，6，7，8，9）c输入：N=7B=（0，0，0，0，4，5，6）输出：A=（3，2，1，0，4，5，6）5本题共30分（10%+10%+10%）①数据输入：N=6P1=RN1=1Q②数据输入：N=6P1=RN1=2P2=YN2=1QRRRRRR排列方案：排列总数=6RRYRRYRRYRRYRRYRRY排列方案：排列总数=12NOIP1995普及组复赛测试数据第6页|共209页③数据输入：N=12P1=RN1=3P2=BN2=2P3=YN3=1QRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBY排列方案：排列总数：105×2=210NOIP1995提高组复赛试题第7页|共209页NOI’95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（高中组）（上机编程，完成时间：210分钟）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的编码为：B=（0，0，0，3，1，2）程序要求解决以下问题：③给出数组A后，求出其编码。④给出数组A的编码后，求出A中的原数据。2灯的排列问题：设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……Nk（k表示不同颜色灯的个数）。放灯时要遵守下列规则：③同一种颜色的灯不能分开；④不同颜色的灯之间至少要有一个空位置。例如：N=8（格子数）R=2（红灯数）B=3（蓝灯数）放置的方法有：R-B顺序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBBNOIP1995提高组复赛试题第8页|共209页B-R顺序BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR放置的总数为12种。数据输入的方式为：NP1（颜色，为一个字母）N1（灯的数量）P2N2……Q（结束标记，Q本身不是灯的颜色）程序要求：求出一种顺序的排列方案及排列总数。3设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，8如下图所示放置：815851691423414326其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的：ABC计算所用到的计算符为：+，-，，且无优先级之分（自左向右计算），运算符最多为2个。如：3+45=3554+3=23可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的：A=BC+B也就是：8=23+2，15=34+3，……14=26+2程序要求：给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。①输入数据不存在出错的情况，同时也不会超过整数的范围。NOIP1995提高组复赛试题第9页|共209页②计算时可允许出现以下情况：A=B（即可理解为运算符的个数为零）A=BB+B（即全部由B产生）NOIP1996普及组复赛试题第10页|共209页NOI’95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛测试数据（高中组）6本题30分（15%+15%）③由数组求编码：共15分（5%+5%+5%）a输入：N=6A=（0，1，2，3，4，5）输出编码：B=（0，1，2，3，4，5）b输入：N=6A=（5，4，3，2，1，0）输出编码：B=（0，0，0，0，0，0）c输入：N=8A=（1，0，3，2，5，4，7，6）输出编码：B=（0，0，2，2，4，4，6，6）④由编码求原数组：共15分（5%+5%+5%）a输入：N=5B=（0，0，0，0，0）输出编码：A=（4，3，2，1，0）b输入：N=10B=（0，1，2，3，4，5，6，7，8，9）输出编码：A=（0，1，2，3，4，5，6，7，8，9）c输入：N=7B=（0，0，0，0，4，5，6）输出编码：A=（3，2，1，0，4，5，6）7本题共30分（10%+10%+10%）④数据输入：N=6P1=RN1=1Q⑤数据输入：N=6P1=RN1=2P2=YN2=1QRRRRRR排列方案：排列总数=6RRYRRYRRYRRYRRYRRY排列方案：排列总数=12NOIP1996普及组复赛试题第11页|共209页⑥数据输入：N=12P1=RN1=3P2=BN2=2P3=YN3=1Q8本题共40分（12%+14%+14%）①输入344443412222213应打印出完整的图形：（12分）151616154788877344443412222213公式：A=B+CRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBYRRRBBY排列方案：排列总数：105×2=210NOIP1996普及组复赛试题第12页|共209页②输入101010121212121应打印出完整的图形（14分）1-11-110–10-10-1101010121212121公式：A=B×C-C⑤输入242424221212121应打印出完整的图形：（14分）8192163948192163948192321632163216242424221212121公式：A=B×C×C或：8168168848484242424221212121公式：A=B+BNOIP1996普及组复赛试题第13页|共209页第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题（初中组竞赛用时：3小时）1．编制一个乘法运算的程序（20分）从键盘读入2个100以内的