NOIP历年复赛提高组试题.doc

全国信息学奥林匹克分区联赛（NOIP）复赛提高组试题
第一届全国信息学奥林匹克分区联赛（NOIP1995）复赛试题
（提高组 竞赛用时：）
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顺序
R
R
B
B
B
R
R
B
B
B
R
R
B
B
B
R
R
B
B
B
R
R
B
B
B
R
R
B
B
B
B-R顺序
B
B
B
R
R
B
B
B
R
R
B
B
B
R
R
B
B
B
R
R
B
B
B
R
R
B
B
B
R
R
放置的方法总数为12种。
数据输入的方式为：
N
P1（颜色，为一个字母） N1（灯的数量）
P2 N2
……
Q（结束标记，Q本身不是灯的颜色）
程序要求：求出一种顺序的放置（排列）方案及放置（排列）方案总数。
3、积木块上的数字
设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，8，如下图所示放置：
8
15
8
5
16
9
14
2
3
4
1
4
3
2
6
其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。
计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的：
A
B
C
计算所用到的计算符为：+，-，，且无优先级之分（自左向右计算），运算符最多为2个。如：
3+45=35 54+3=23
可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的：
A=BC+B
也就是：8=23+2，15=34+3，……14=26+2
程序要求：
给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。
输入数据不存在出错的情况，同时也不会超过整数的范围。
计算时可允许出现以下情况：
A=B （即可理解为运算符的个数为零）
A=BB+B （即全部由B产生）
第二届全国信息学奥林匹克分区联赛（NOIP1996）复赛试题
（提高组 竞赛用时：3小时）
1、比赛安排
设有有2 n（n<=6）个球队进行单循环比赛，计划在2 n – 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n – 1天内每个队都与不同的对手比赛。
例如n=2时的比赛安排：
队 1 2 3 4
比赛 1==2 3==4 一天
1==3 2==4 二天
1==4 2==3 三天
2、数制转换
设有一个字符串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>
3、挖地雷
在一个地图上有N个地窖（N<=20），每