历届noip提高组复赛精彩试题

《历届noip提高组复赛精彩试题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档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）程序要求解决以下问题：①给出

2、数组A后，求出其编码。②给出数组A的编码后，求出A中的原数据。<2>灯的排列问题：设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……Nk（k表示不同颜色灯的个数）。放灯时要遵守下列规则：①同一种颜色的灯不能分开；②不同颜色的灯之间至少要有一个空位置。例如：N=8（格子数）R=2（红灯数）B=3（蓝灯数）放置的方法有：R-B顺序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBB文案大全实用文档B-R顺序BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR放置的总数为12种。数据输入的方式为：NP1（

3、颜色，为一个字母）N1（灯的数量）P2N2……Q（结束标记，Q本身不是灯的颜色）程序要求：求出一种顺序的排列方案及排列总数。<3>设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，8如下图所示放置：815851691423414326其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的：ABC计算所用到的计算符为：+，-，，且无优先级之分（自左向右计算），运算符最多为2个。如：3+45=3554+3=23可以看出，上图中的第三层的数据是

4、由第四层的数据用以下计算公式计算出来的：A=BC+B也就是：8=23+2，15=34+3，……14=26+2程序要求：给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。①输入数据不存在出错的情况，同时也不会超过整数的范围。文案大全实用文档①计算时可允许出现以下情况：A=B（即可理解为运算符的个数为零）A=BB+B（即全部由B产生）第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题（高中组竞赛用时：3小时）1．比赛安排（20分）设有有2n（n<=6）个球队进行单循环比赛，计划在2n–1天内完成，每个队每

5、天进行一场比赛。设计一个比赛的安排，使在2n–1天内每个队都与不同的对手比赛。例如n=2时的比赛安排：队1234比赛1==23==4一天1==32==4二天1==42==3三天2．数制转换（20分）设有一个字符串A$的结构为：A$=’mp’其中m为数字串（长度<=20），而n,p均为1或2位的数字串（其中所表达的内容在2-10之间）。程序要求：从键盘上读入A$后（不用正确性检查），将A$中的数字串m(n进制)，以p进制的形式输出。例如：A$=’48<10>8’其意义为：将10进制数48，转换成8进制数输出。输出结果为：48<10>=60<8>4．挖地雷（

6、30分）在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。V1V2V3V4V5例如：[题目要求]当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。输入格式：N：（表示地窖的个数）　　　Ｗ1，W2，W3，……WN（表示每个地窖中埋藏的地雷数量）文案大全实用文档地窖之间连接路径（其中Ａij=1表示地窖i,j之间是否有通路：通Aij=1,不通Aij==0）A12…………….A1NA23………

7、…..A2N……..AN-1N输出格式：K1--K2--……….KV（挖地雷的顺序）MAX（挖地雷的数量）例如：　　　　⑩--------⑧④-----⑦-------⑥其输入格式为：输出：51–3-4-510，8，4，7，6max=2711100001114．砝码称重（30分）设有1g、2g、3g、5g、10g、20g的砝码各若干枚（其总重<=1000），要求：输入方式：a1a2a3a4a5a6（表示1g砝码有a1个，2g砝码有a2个，…，20g砝码有a6个）输出方式：Total=N（N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）如输

8、入：1_1_0_0_0_0（注：下划线