历届noip提高组复赛考试.doc

NOI’95“同创杯”全国青少年信息学(计算机)奥林匹克竞赛分区联赛复赛试题(高中组)(上机编程,完成时间:210分钟)编码问题:设有一个数组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中的原数据。灯的排列问题:设在一排上有N个格子(N≤20),若在格子中放置有不同颜色的灯,每种灯的个数记为N1,N2,……Nk(k表示不同颜色灯的个数)。放灯时要遵守下列规则:同一种颜色的灯不能分开;不同颜色的灯之间至少要有一个空位置。例如:N=8(格子数)R=2(红灯数)B=3(蓝灯数)放置的方法有:R-B顺序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBBB-R顺序BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR放置的总数为12种。数据输入的方式为:NP1(颜色,为一个字母)N1(灯的数量)P2N2……Q(结束标记,Q本身不是灯的颜色)程序要求:求出一种顺序的排列方案及排列总数。<3>设有一个四层的积木块,1~4层积木块的数量依次为:5,6,7,8如下图所示放置:815851691423414326其中,给出第三层与第四层所标示的数字,并已知第三层的数据是由第四层的数据计算出来的。计算的方法是:第三层的某个数据A是由第四层相邻的两个数据B,C经过某种计算后产生的:ABC计算所用到的计算符为:+,-,,且无优先级之分(自左向右计算),运算符最多为2个。如:3+45=3554+3=23可以看出,上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的:A=BC+B也就是:8=23+2,15=34+3,……14=26+2程序要求:给出第四层与第三层的数据后,将第一、二层的每块积木标上相应的数据,并输出整个完整的积木图及计算公式。输入数据不存在出错的情况,同时也不会超过整数的范围。计算时可允许出现以下情况:A=B(即可理解为运算符的个数为零)A=BB+B(即全部由B产生)第二届全国青少年信息学(计算机)奥林匹克分区联赛复赛试题(高中组竞赛用时:3小时)(20分)设有有2n(n<=6)个球队进行单循环比赛,计划在2n–1天内完成,每个队每天进行一场比赛。设计一个比赛的安排,使在2n–1天内每个队都与不同的对手比赛。例如n=2时的比赛安排:队12 34比赛1==2 3==4 一天1==3 2==4 二天1==4 2==(20分)设有一个字符串A$的结构为:A$=’m<n>p’其中m为数字串(长度<=20),而n,p均为1或2位的数字串(其中所表达的内容在2-10之间)。程序要求:从键盘上读入A$后(不用正确性检查),将A$中的数字串m(n进制),以p进制的形式输出。例如:A$=’48<10>8’其意义为:将10进制数48,转换成8进制数输出。输出结果为:48<10>=60<8>(30分)在一个地图上有N个地窖(N<=20),每个地窖中埋有一定数量的地雷。同时,给出地窖之间的连接路径。V1V2V3V4V5例如:[题目要求]当地窖及其连接的数据给出之后,某人可以从任一处开始挖地雷,然后可以沿着指出的连接往下挖(仅能选择一条路径),当无连接时挖地雷工作结束。设计一个挖地雷的方案,使某人能挖到最多的地雷。输入格式:N:(表示地窖的个数) W1,W2,W3,……WN(表示每个地窖中埋藏的地雷数量)地窖之间连接路径(其中Aij=1表示地窖i,j之间是否有通路:通Aij=1,不通Aij==0)A12…………….A1NA23…………..A2N……..AN-1N输出格式:K1--K2--……….KV(挖地雷的顺序)MAX(挖地雷的数量)例如:⑩--------⑧④-----⑦-------⑥其输入格式为:输出:51–3-4-510,8,4,7,6 max=27**********.砝码称重(30分)设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其总重<=1000),要求:输入方式:a1a2a3a4a5a6(表示1g砝码有a1个,2g砝码有a2个,…,20g砝码有a6个)输出方式:Total=N(N表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况)如输入:1_1_0_0_0_0(注:下划线表示空格)输出:TOTAL=3表示可以称出1g,2g,3g三种不同的重量。第三届全