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

《NOIP历年复赛提高组试题-.doc》由会员分享，可在线阅读，更多相关《NOIP历年复赛提高组试题-.doc（55页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、|全国信息学奥林匹克分区联赛（NOIP）复赛提高组试题|第一届全国信息学奥林匹克分区联赛（NOIP1995）复赛试题（提高组 竞赛用时：3.5 小时）1、编码问题设有一个数组 A:ARRAY0.N-1OFINTEGER；数组中存放的元素为 0N-1 之间的整数，且 AiAj（当 ij 时） 。例如：N=6 时，有：A= （4，3，0，5，1，2）此时，数组 A 的编码定义如下：A0的编码为 0；Ai的编码为：在 A0，A1，Ai-1 中比 Ai的值小的个数（i=1 ，2，N-1 ）上面数组 A 的编码为：B=（0，0，0，3，1，2）程序要求解决以下问题： 给出数组 A 后，求出其编码。 给出

2、数组 A 的编码后，求出 A 中的原数据。2、灯的排列问题设在一排上有 N 个格子（N20） ，若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N 2，N k（k 表示不同颜色灯的个数） 。放灯时要遵守下列规则：同一种颜色的灯不能分开；不同颜色的灯之间至少要有一个空位置。例如：N=8 （格子数） ；R=2（红灯数） ；B=3（蓝灯数） ，放置的方法有：R-B 顺序R R B B BR R B B BR R B B BR R B B BR R B B BR R B B BB-R 顺序B B B R RB B B R RB B B R RB B B R RB B B R RB B B R R|

3、放置的方法总数为 12 种。数据输入的方式为：NP1（颜色，为一个字母） N1（灯的数量）P2 N2Q（结束标记，Q 本身不是灯的颜色）程序要求：求出一种顺序的放置（排列）方案及放置（排列）方案总数。3、积木块上的数字设有一个四层的积木块，14 层积木块的数量依次为：5，6，7，8，如下图所示放置：8 15 8 5 16 9 142 3 4 1 4 3 2 6其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。计算的方法是：第三层的某个数据 A 是由第四层相邻的两个数据 B，C 经过某种计算后产生的：计算所用到的计算符为：+，- ， ，且无优先级之分（自左向右计

4、算） ，运算符最多为 2 个。如：3+4 5=35 5 4+3=23可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的：A=B C+B也就是：8=2 3+2，15=3 4+3，14=2 6+2程序要求：给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。 输入数据不存在出错的情况，同时也不会超过整数的范围。 计算时可允许出现以下情况：A=B （即可理解为运算符的个数为零）A=B B+B （即全部由 B 产生）AB C|第二届全国信息学奥林匹克分区联赛（NOIP1996）复赛试题（提高组 竞赛用时：3 小时）1、比赛安排设有有

5、2 n（np，其中 m 为数字串（长度8，其意义为：将 10 进制数 48，转换成 8 进制数输出。输出结果为：48=603、挖地雷在一个地图上有 N 个地窖（ N=20） ，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。例如：【题目要求】当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径） ，当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。【输入格式】N （表示地窖的个数） 1 W2 W3， WN （表示每个地窖中埋藏的地雷数量）A12 A1N A23 A2N AN-1 NV1 V 2 V3 V4 V

6、5 |【输出格式】K1-K2-KV （挖地雷的顺序）MAX （挖地雷的数量）例如： 其输入格式为：510，8，4，7，61 1 1 00 0 01 1 1输出为：1 3 -4 -5max=274砝码称重设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重=1000） ，问可以称为多少种不同的重量。输入方式：a1 a2 a3 a4 a5 a6（分别表示 1g 砝码有 a1 个，2g 砝码有 a2 个，20g 砝码有 a6 个）输出方式：Total=N（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）如输入：1_1_0_0_0_0 （注：下划线表示空格）则输

7、出：TOTAL=3 （表示可以称出 1g，2g， 3g 三种不同的重量。 ）|第三届全国信息学奥林匹克分区联赛（NOIP1997）复赛试题（提高组 竞赛用时：3 小时）1、 棋盘上的素数在 N*N 的棋盘上（1N10） ，填入 1，2，N*N 共 N*N 个数，使得任意两个相邻的数之和为素数。 （30%）例如：当 N=2 时，有：1 24 3当 N=4 时，一种可以填写的方案如下：1 2 11 1216 15 8 513 4 9 146 7 10 3在这里我们约定：左上角的格子里必须填数字 1。【程序要求】输入：N输出：如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO

8、 ！” 。2、 代数表达式正确性判定代数表达式的定义如下：例如，下面的式子是合法的代数表达式：其相邻数的和为素数的有：1+2，1+4，4+3 ，2+3acb字母|a；a+b*(a+c)；a*a/(b+c)；下面的式子是不合法的代数表达式：Ab；a+a*/(b+c)；【程序要求】输入：输入一个字符串，以“；”结束， “；”本身不是代数表达式中字符，仅作为结束） ；输出：若表达式正确，则输出“OK” ；若表达式不正确，则输出 “ERROR”，及错误类型。错误类型约定：1式子中出现不允许的字符；2括号不配对；3其它错误。例如：输入：a+(b); 输出：OK例如：输入：a+(b+c*a; 输出：ERR

9、OR 23、 骑士游历：设有一个 n*m 的棋盘（2n 50，2m 50） ，如下图，在棋盘上左下角有一个中国象棋马。（n,m）(1,1)马走的规则为：1）马走日字；2）马只能向右走即如下图如示：任务 1：当 n,m 输入之后，找出一条从左下角到右上角的路径。例如，输入：n=4，m=4输出：路径的格式：(1,1)(2,3)(4,4) 。若不存在路径，则输出NO 任务 2：当 n，m 给出之后，同时给出马起点的位置和终点的位置，试找出从起点到终点的所有路径的数目。例如：n=10，m=10,马(4,4)(1,1)|（1，5） （起点） ， （3，5） （终点）输出：2 （即表示由（1，5）到（3，

10、5）共有 2 条路径）输入格式：n m x1 y1 x2 y2 (分别表示 n,m,起点坐标，终点坐标)输出格式：路径数目（若不存在从起点到终点的路径，则输出 0）109876543211 2 3 4 5 6 7 8 9 10|第四届全国信息学奥林匹克分区联赛（NOIP1998）复赛试题（提高组 竞赛用时：3 小时）1、火车上的人数火车从始发站（称为第 1 站）开出，在始发站上车的人数为 a，然后到达第 2 站，在第 2 站有人上、下车，但上、下车的人数相同，因此在第 2 站开出时（即在到达第 3 站之前）车上的人数保持为 a 人。从第 3 站起（包括第 3 站）上、下车的人数有一定规律：上车

11、的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 n-1 站） ，都满足此规律。现给出的条件是：共有 N 个车站，始发站上车的人数为 a，最后一站下车的人数是 m（全部下车） 。试问 x 站开出时车上的人数是多少？输入：a，n，m 和 x输出：从 x 站开出时车上的人数。2、数的联接设有 n 个正整数（n20） ，将它们联接成一排，组成一个最大的多位整数。例如：n=3 时，3 个整数 13，312，343 联接成的最大整数为：34331213又如：n=4 时，4 个整数 7，13，4，246 联接成的最大整数为：7424613程序输入：nn 个数 （用空格相

12、隔的 n 个整数）程序输出：联接成的多位数3、进位制著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。 例如：其含义为：L+L=L，L+K=K，L+V=V，L+E=EK+L=K，K+K=V，K+V=E ，K+E=KLE+E=KV根据这些规则可推导出：L=0 ，K=1，V=2，E=3 ；同时可以确定该表表示的是 4 进制加法。程序输入：n（n9）表示行数。以下 n 行，每行包括 n 个字符串，每个字串间用空格隔开。（字串仅有一个为+号，其它都由大写字母组成）程序输出： 各个字母表示什么数，格式如：L=0 ，K=1， 加法运算是几进制的。 若不可能组成加法表，

13、则应输出“ERROR！”+ L K V EL L K V EK K V E KLV V E KL KKE E KL KK KV|第五届全国信息学奥林匹克分区联赛（NOIP1999）复赛试题（提高组 竞赛用时：3 小时）1、 拦截导弹【问题描述】某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数） ，计算这套系

14、统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。【输入样例】389 207 155 300 299 170 158 65【输出样例】6 （最多能拦截的导弹数）2 （要拦截所有导弹最少要配备的系统数）2、回文数【问题描述】若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个 10 进制数 56，将 56 加 65（即把 56 从右向左读） ，得到 121 是一个回文数。又如：对于 10 进制数 87：STEP1：87+78 = 165 STEP2：165+561 = 726STEP3：726+627 = 1353 STEP4：1353+3531 = 4884在这里的一步是指进行了一次 N 进制的加法，上例最少用了 4 步得到回文数 4884。写一个程序，给定一个 N（2=N=10 或 N=16）进制数 M，求最少经过几步可以得到回文数。如果在 30 步以内（包含 30 步）不可能得到回文数，则输出“Impossible！”【输入样例】9 87【输出样例】STEP=6