学科竞赛NOIP提高组复赛试题.doc

《学科竞赛NOIP提高组复赛试题.doc》由会员分享，可在线阅读，更多相关《学科竞赛NOIP提高组复赛试题.doc（118页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、优质文本目 录NOI95 “同创杯全国青少年信息学计算机奥林匹克竞赛2第二届全国青少年信息学计算机奥林匹克分区联赛复赛试题4第三届全国青少年信息学计算机奥林匹克分区联赛复赛试题5第四届全国青少年信息学计算机奥林匹克分区联赛复赛试题7第五届全国青少年信息学计算机奥林匹克分区联赛复赛试题82000年102001年152002年17第九届全国青少年信息学奥林匹克联赛N0IP200321第十届全国青少年信息学奥林匹克联赛复赛试题252005年31NOIP2006提高组复赛试题352007年44全国信息学奥林匹克联赛NOIP2016复赛502016年562010年602011年61NOI95 “同创杯全

2、国青少年信息学计算机奥林匹克竞赛分区联赛复赛试题高中组 上机编程，完成时间：210分钟 编码问题： 设有一个数组A:ARRAY0.N-1 OF INTEGER； 数组中存放的元素为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后，求出其编码。 给出数组A的编码后，求出A中的原数据。 灯的排列问题： 设在一排上有N个格子N20，假设在格子中放置有

3、不同颜色的灯，每种灯的个数记为N1，N2，Nkk表示不同颜色灯的个数。 放灯时要遵守以下规那么： 同一种颜色的灯不能分开； 不同颜色的灯之间至少要有一个空位置。 例如：N=8格子数 R=2红灯数 B=3蓝灯数 放置的方法有： R-B顺序RRBBBRRBBBRRBBBRRBBBRRBBBRRBBB B-R顺序BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR 放置的总数为12种。 数据输入的方式为：NP1颜色，为一个字母 N1灯的数量P2 N2 Q结束标记，Q本身不是灯的颜色 程序要求：求出一种顺序的排列方案及排列总数。 设有一个四层的积木块，14层积木块的数量依次为：5，6，7，8

4、如以下图所示放置：815851691423414326 其中，给出第三层及第四层所标示的数字，并第三层的数据是由第四层的数据计算出来的。 计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的：ABC 计算所用到的计算符为：+，-，且无优先级之分自左向右计算，运算符最多为2个。 如：3+45=35 54+3=23 可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的：A=BC+B 也就是：8=23+2，15=34+3，14=26+2 程序要求： 给出第四层及第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。 输

5、入数据不存在出错的情况，同时也不会超过整数的范围。 计算时可允许出现以下情况： A=B 即可理解为运算符的个数为零 A=BB+B 即全部由B产生第二届全国青少年信息学计算机奥林匹克分区联赛复赛试题 高中组 竞赛用时：3小时1比赛安排20分 设有有2 nn=6个球队进行单循环比赛，方案在2 n 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n 1天内每个队都及不同的对手比赛。例如n=2时的比赛安排： 队 1 23 4 比赛 1=23=4 一天 1=32=4 二天 1=4 2=3 三天2数制转换20分 设有一个字符串A$的结构为： A$=mp 其中m为数字串长度=20，而n,p均

6、为1或2位的数字串其中所表达的内容在2-10之间。 程序要求：从键盘上读入A$后不用正确性检查，将A$中的数字串m(n进制)，以p进制的形式输出。 例如：A$=488 其意义为：将10进制数48，转换成8进制数输出。 输出结果为：48=604挖地雷30分 在一个地图上有N个地窖N=20，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。V1 V 2 V3 V4 V5 例如：题目要求当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖仅能选择一条路径，当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。 输入格式： N： 表示地窖的

7、个数 1，W2，W3，WN 表示每个地窖中埋藏的地雷数量地窖之间连接路径其中ij=1表示地窖i,j之间是否有通路：通Aij=1,不通Aij=0 A12 . A1N A23.A2N . AN-1 N 输出格式： K1-K2-.KV 挖地雷的顺序 MAX 挖地雷的数量例如： - -其输入格式为： 输出： 51 3 -4 -510，8，4，7，6max=27 1 1 1 0 0 0 0 1 1 14砝码称重30分设有1g、2g、3g、5g、10g、20g的砝码各假设干枚其总重=1000，要求： 输入方式：a1 a2 a3 a4 a5 a6 表示1g砝码有a1个，2g砝码有a2个，20g砝码有a6个

8、输出方式：Total=N N表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况如输入：1_1_0_0_0_0 注：下划线表示空格 输出：TOTAL=3 表示可以称出1g，2g，3g三种不同的重量。第三届全国青少年信息学计算机奥林匹克分区联赛复赛试题 高中组 竞赛用时：3小时1在N*N的棋盘上1N10，填入1，2，N*N共N*N个数，使得任意两个相邻的数之和为素数。30%其相邻数的和为素数的有：1+2，1+4，4+3，2+3 例如：当N=2时，有：1243 当N=4时，一种可以填写的方案如下： 12111216158513491467103 在这里我们约定：左上角的格子里必须填数

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

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

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

12、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程序输入：n n个数程序输出：联接成的多位数 40%3著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。 例如： 40%+LKVELLK

13、VEKKVEKLVVEKLKKEEKLKK KV其含义为：L+L=L，L+K=K，L+V=V，L+E=EK+L=K，K+K=V，K+V=E，K+E=KL E+E=KV 根据这些规那么可推导出：L=0，K=1，V=2，E=3 同时可以确定该表表示的是4进制加法程序输入： nn9表示行数。以下n行，每行包括n个字符串，每个字串间用空格隔开。字串仅有一个为+号，其它都由大写字母组成程序输出： 各个字母表示什么数，格式如：L=0，K=1， 加法运算是几进制的。 假设不可能组成加法表，那么应输出“ERROR！第五届全国青少年信息学计算机奥林匹克分区联赛复赛试题 提 高 组 竞赛用时：3小时第一题 拦截导

14、弹(28分) 某国为了防御敌国的导弹袭击，开展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度雷达给出的高度数据是不大于30000的正整数，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 样例： INPUT OUTPUT 389 207 155 300 299 170 158 65 6最多能拦截的导弹数 2要拦截所有导弹最少要配备的系统数第二题 回

15、文数(25分)假设一个数首位不为零从左向右读及从右向左读都一样，我们就将其称之为回文数。 例如：给定一个10进制数56，将56加65即把56从右向左读，得到121是一个回文数。 又如：对于10进制数87： STEP1：87+78 = 165 STEP2：165+561 = 726 STEP3：726+627 = 1353 STEP4：1353+3531 = 4884 在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。 写一个程序，给定一个N2=N=10或N=16进制数M，求最少经过几步可以得到回文数。 如果在30步以内包含30步不可能得到回文数，那么输出“Imposs

16、ible！ 样例： INPUT OUTPUT N = 9 M= 87 STEP=6第三题 旅行家的预算(27分) 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市假设出发时油箱是空的。给定两个城市之间的距离D1、汽车油箱的容量C以升为单位、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数NN可以为零，油站i离出发点的距离Di、每升汽油价格Pii=1，2，N。计算结果四舍五入至小数点后两位。如果无法到达目的地，那么输出“No Solution。 样例： INPUT D1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站号I离出发点的距离Di每升汽油价格Pi1102

17、.02.92220.02.2 OUTPUT26.95该数据表示最小费用第四题 邮票面值设计(40分)给定一个信封，最多只允许粘贴N张邮票，计算在给定KN+K40种邮票的情况下假定所有的邮票数量都足够，如何设计邮票的面值，能得到最大值MAX，使在1MAX之间的每一个邮资值都能得到。 例如，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 OUTPU

18、T N=3 K=2 1 3 MAX=72000年 题一 进制转换 18分 问题描述 我们可以用这样的方式来表示一个十进制数： 将每个阿拉伯数字乘以一个以该数字所处位置的值减为指数，以为底数的幂之和的形式。例如：可表示为 这样的形式。 及之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的值为指数，以为底数的幂之和的形式。一般说来，任何一个正整数或一个负整数都可以被选来作为一个数制系统的基数。如果是以或为基数，那么需要用到的数码为 ，。例如，当时，所需用到的数码是，和，这及其是或无关。如果作为基数的数绝对值超过，那么为了表示这些数码，通常使用英文字母来表示那些大于的数码。

19、例如对进制数来说，用表示，用表示，用表示，用表示，用表示，用表示。在负进制数中是用 作为基数，例如十进制相当于进制，并且它可以被表示为的幂级数的和数： 问题求解 设计一个程序，读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数： ， 输 入 输入的每行有两个输入数据。 第一个是十进制数3276832767； 第二个是负进制数的基数。 输 出 结果显示在屏幕上，相对于输入，应输出此负进制数及其基数，假设此基数超过，那么参照进制的方式处理。 样 例 输入输出 提高组 题二 乘积最大 22分 问题描述 今年是国际数学联盟确定的“2000世界数学年，又恰逢我国著名数学家华罗庚先

20、生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个局部，找出一种分法，使得这K+1个局部的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312， 当N=3，K=1时会有以下两种分法：1） 3*12=362） 31*2=62 这时，符合题目要求的结果是：31*2=62 现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 输 入 程序的输入共有两行： 第一行共有2

21、个自然数N，K6N40，1K6 第二行是一个长度为N的数字串。 输 出 结果显示在屏幕上，相对于输入，应输出所求得的最大乘积一个自然数。 样 例 输入4 21231输出62提高组 题三 单词接龙 27分 问题描述 单词接龙是一个及我们经常玩的成语接龙相类似的游戏，现在我们一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙每个单词都最多在“龙中出现两次，在两个单词相连时，其重合局部合为一局部，例如 beast和astonish，如果接成一条龙那么变为beastonish，另外相邻的两局部不能存在包含关系，例如at 和 atide 间不能相连。 输 入 输入的第一行为一个单独的整数n

22、 (n=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙开头的字母。你可以假定以此字母开头的“龙一定存在. 输 出 只需输出以此字母开头的最长的“龙的长度 样 例 ： 输入5attouchcheatchoosetacta输出23 连成的“龙为atoucheatactactouchoose 提高组 题四 方格取数 33分 问题描述 设有N*N的方格图(N=1。要求由小到大依次在同一行输出这三个实根(根及根之间留有空格)，并精确到小数点后2位。提示：记方程f(x)=0，假设存在2个数x1和x2，且x1x2，f(x1)*f(x2)0，那么在(x1，x2)之间一定有一

23、个 根。样例输入：1 -5 -4 20输出：-2.00 2.00 5.00题二 数的划分(20分)问题描述将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5; 1，5，1; 5，1，1;问有多少种不同的分法。输入：n，k (6n=200，2=k=6)输出：一个整数，即不同的分法。样例输入： 7 3输出：4 四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;题三 统计单词个数(30分)问题描述给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。

24、要求将此字母串分成k份(1k=40)，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以局部重叠。中选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。单词在给出的一个不超过6个单词的字典中。要求输出最大的个数。输入格式去部输入数据放在文本文件input3.dat中，其格式如下：第一行为一个正整数(0n=5)表示有n组测试数据每组的第一行有二个正整数(p，k)p表示字串的行数;k表示分为k个局部。接下来的p行，每行均有20个字符。再接下来有一个正整数s，表示字典中单词个数。(1=s=6)接下来的s行，每行均有一个单词。输出

25、格式结果输出至屏幕，每行一个整数，分别对应每组测试数据的相应结果。样例输入： 11 3thisisabookyouareaoh4isaoksab输出： /说明：(不必输出)7 / this/isabookyoua/reaoh题四 Car的旅行路线(30分) 问题描述又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。图例 机场 高速铁路飞机航线 注意：图中并没有标出所有的铁路及

26、航线。那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。任务找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。输入文件：键盘输入文件名输 出：到屏幕(输出最小费用，小数点后保存1位。)输入格式第一行为一个正整数n(0=n=10)，表示有n组测试数据。每组的第一行有四个正整数s，t，A，B。S(0S=100)表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，(1=A，B 从 取 3 张牌放到 9 11 10 10- 从 取 1 张牌放到10 10 10 10。输 入：键盘输入文件名。

27、文件格式：NN 堆纸牌，1 = N = 100A1 A2 An N 堆纸牌，每堆纸牌初始数，l= Ai B1$A2$ - B2$规那么的含义为：在 A中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ 。例如：A$abcdB$xyz变换规那么为：abc-xuud-yy-yz那么此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：abcd-xud-xy-xyz共进行了三次变换，使得 A$ 变换为B$。输入:键盘输人文件名。文件格式如下：A$ B$A1$ B1$ A2$ B2$ |- 变换规那么. . /所有字符串长度的上限为 20。输出:输出至屏幕。格式如下：假设在 10

28、步包含 10步以内能将 A$ 变换为 B$ ，那么输出最少的变换步数；否那么输出NO ANSWER!输入输出样例b.in:abcd wyzabc xuud yy yz屏幕显示：3题三 自由落体存盘名:NOIPG3问题描述:在高为 H 的天花板上有 n 个小球，体积不计，位置分别为 0，1，2，n-1。在地面上有一个小车长为 L，高为 K，距原点距离为 S1。小球下落距离计算公式为 d1/2*g*(t2)，其中 g=10，t 为下落时间。地面上的小车以速度 V 前进。如以下图：小车及所有小球同时开始运动，当小球距小车的距离 = 0.00001 时，即认为小球被小车接受小球落到地面后不能被接受。请你计算出小车能接受到多少个小球。输入：键盘输人：H，S1，V，L，K，n l=H，S1，V，L，K，n =100000输出：屏幕输出：小车能接受到的小球个数。输入输出样例输入:5.0 9.0 5.0 2.5 1.8 5输出:1题四 矩形覆盖存盘名NOIPG4问