历届noip提高组复赛试题-.doc

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

1、|NOI95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛复赛试题（高中组） （上机编程，完成时间：210 分钟）编码问题：设有一个数组 A:ARRAY0.N-1 OF INTEGER；数组中存放的元素为 0N-1 之间的整数，且 Ai Aj（当 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 后，求出其编码。 给出数组 A 的编码后

2、，求出 A 中的原数据。灯的排列问题：设在一排上有 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 B|B-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放置的总数为 12 种。数据输

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

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

5、 48，转换成 8 进制数输出。输出结果为：48=604挖地雷（30 分）在一个地图上有 N 个地窖（ N=20） ，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。例如：题目要求当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径） ，当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。V1 V 2 V3 V4 V5 |输入格式： N： （表示地窖的个数） 1，W 2，W 3，W N （表示每个地窖中埋藏的地雷数量）A12 . A1N A23.A2N .AN-1 N输出格式：K1-K2-.KV （挖地雷的顺序

6、 ）MAX （挖地雷的数量）例如：- - 其输入格式为： 输出：5 1 3 -4 -510，8，4，7，6 max=271 1 1 00 0 01 1 14砝码称重（30 分）设有 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 （注：下划线表示空格）输出：TOTAL=3 表示可以称出 1g，2g，3g 三

7、种不同的重量。第三届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （高中组 竞赛用时：3 小时）1在 N*N 的棋盘上（1N10） ，填入 1，2，N*N 共 N*N 个数，使得任意两个相邻的数之和为素数。 （30% ）例如：当 N=2 时，有：1 2地窖之间连接路径（其中 ij=1 表示地窖 i,j之间是否有通路：通 Aij=1,不通 Aij=0）其相邻数的和为素数的有：1+2，1+4，4+3 ，2+3|4 3当 N=4 时，一种可以填写的方案如下：1 2 11 1216 15 8 513 4 9 146 7 10 3在这里我们约定：左上角的格子里必须填数字 1。程序要求：输入：N；输

8、出：如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出“NO！” 。2代数表达式的定义如下：例如，下面的式子是合法的代数表达式：a；a+b*(a+c);a*a/(b+c)下面的式子是不合法的代数表达式：ab;a+a*/(b+c);程序要求：输入：输入一个字符串，以“；”结束， “；”本身不是代数表达式中字符，仅作为结束） ； 输出：若表达式正确，则输出“OK” ；若表达式不正确，则输出 “ERROR”，及错误类型。错误类型约定：1式了中出现不允许的字符；2括号不配对；acb字母|3其它错误。例如：输入：a+(b); 输出：OK例如：输入：a+(b+c*a; 输出：ERROR

9、23骑士游历：设有一个 n*m 的棋盘（ 2n50，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） ， （1，5） （起点） ， （3，5） （终点）输 出：2（即由（1，5）到（3，5）共有 2 条路径）马(

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

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

12、科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。 例如： 40%其含义为：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）表示行数。+ L K V EL L K V EK K V E KLV V E KL KKE E KL KK KV|以下 n 行，每行包括 n 个字符串，每个字串间用空格隔开。 （字串仅有一个为+号，其它都由大写字母组成）程序输出： 各个字母表示什么数，格式如：L=0 ，

13、K=1， 加法运算是几进制的。 若不可能组成加法表，则应输出“ERROR！”第五届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （提 高 组 竞赛用时：3 小时）第一题 拦截导弹(28 分)某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数） ，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配

14、备多少套这种导弹拦截系统。样例：INPUT OUTPUT389 207 155 300 299 170 158 65 6（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）第二题 回文数(25 分)若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个 10 进制数 56，将 56 加 65（即把 56 从右向左读） ，得到 121 是一个回文数。又如：对于 10 进制数 87：STEP1：87+78 = 165 STEP2：165+561 = 726STEP3：726+627 = 1353 STEP4：1353+3531 = 4884在这里的一步是

15、指进行了一次 N 进制的加法，上例最少用了 4 步得到回文数 4884。写一个程序，给定一个 N（2=N=10 或 N=16）进制数 M，求最少经过几步可以得到回|文数。如果在 30 步以内（包含 30 步）不可能得到回文数，则输出“Impossible！”样例：INPUT OUTPUTN = 9 M= 87 STEP=6第三题 旅行家的预算(27 分)一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的） 。给定两个城市之间的距离 D1、汽车油箱的容量 C（以升为单位） 、每升汽油能行驶的距离 D2、出发点每升汽油价格 P 和沿途油站数 N（N 可以为零） ，油站 i

16、 离出发点的距离Di、每升汽油价格 Pi（i=1，2，N） 。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution” 。样例：INPUTD1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站号 I 离出发点的距离 Di 每升汽油价格 Pi1 102.0 2.92 220.0 2.2OUTPUT26.95（该数据表示最小费用）第四题 邮票面值设计(40 分)给定一个信封，最多只允许粘贴 N 张邮票，计算在给定 K（N+K40）种邮票的情况下（假定所有的邮票数量都足够） ，如何设计邮票的面值，能得到最大值 MAX，使在 1MAX之间的每一个邮资值都能得

17、到。例如，N=3，K=2，如果面值分别为 1 分、4 分，则在 1 分6 分之间的每一个邮资值都能得到（当然还有 8 分、9 分和 12 分） ；如果面值分别为 1 分、3 分，则在 1 分7 分之间的每一个邮资值都能得到。可以验证当 N=3，K=2 时，7 分就是可以得到的连续的邮资最大值，所以 MAX=7，面值分别为 1 分、3 分。样例：INPUT OUTPUTN=3 K=2 1 3MAX=7|2000 年题一 进制转换 （18 分）问题描述 我们可以用这样的方式来表示一个十进制数： 将每个阿拉伯数字乘以一个以该数字所处位置的（值减）为指数，以为底数的幂之和的形式。例如：可表示为 这样的

18、形式。与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的（值）为指数，以为底数的幂之和的形式。一般说来，任何一个正整数或一个负整数都可以被选来作为一个数制系统的基数。如果是以或为基数，则需要用到的数码为 ， 。例如，当时，所需用到的数码是，和，这与其是或无关。如果作为基数的数绝对值超过，则为了表示这些数码，通常使用英文字母来表示那些大于的数码。例如对进制数来说，用表示，用表示，用表示，用表示，用表示，用表示。在负进制数中是用 作为基数，例如（十进制）相当于（进制），并且它可以被表示为的幂级数的和数：（） （） （） （） （） （） 问题求解 设计一个程序，读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数： ， ， 输 入 输入的每行有两个输入数据。第一个是十进制数（3276832767） ； 第二个是负进制数的基数。输 出 结果显示在屏幕上，相对于输入，应输出此负进制数及其基数，若此基数超过，则参照进制的方式处理。样 例 输入