《noip提高组复赛试题汇编(1998-2010)》由会员分享，可在线阅读，更多相关《noip提高组复赛试题汇编(1998-2010)（39页珍藏版）》请在金锄头文库上搜索。
1、1 NOIP 1998 1火车从始发站（称为第 1 站）开出，在始发站上车的人数为 a，然后到达第 2 站，在第 2 站有人上、 下车，但上、下车的人数相同，因此在第 2 站开出时（即在到达第 3 站之前）车上的人数保持为 a 人。从第 3 站起（包括第 3 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和， 而下车人数等于上一站上车人数，一直到终点站的前一站（第 n-1 站） ，都满足此规律。现给出的 条件是：共有 N 个车站，始发站上车的人数为 a，最后一站下车的人数是 m（全部下车） 。试问 x 站 开出时车上的人数是多少？ 2设有 n 个正整数（n20） ，将它们联接成一
2、排，组成一个最大的多位整数。 例如：n=3 时，3 个整数 13，312，343 联接成的最大整数为：34331213 又如：n=4 时，4 个整数 7，13，4，246 联接成的最大整数为：7424613 3著名科学家卢斯为了检查学生对进位制的理解，他给出了如下的一张加法表，表中的字母代表数字。 例如： 其含义为： L+L=L，L+K=K，L+V=V，L+E=E K+L=K，K+K=V，K+V=E，K+E=KL E+E=KV 根据这些规则可推导出：L=0，K=1，V=2，E=3 同时可以确定该表表示的是 4 进制加法 NOIP 1999 第一题拦截导弹第一题拦截导弹 某国为了防御敌国的导弹袭
3、击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽 然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕 捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000 的正整数） ，计算这套系统最多能 拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 样例： INPUTOUTPUT 389 207 155 300 299 170 158 656（最多能拦截的导弹数） 2（要拦截所有导弹最少要配备的系统数） 输入：a，n，m 和 x输
4、出：从 x 站开出时车上的人数。 程序输入：n n 个数 程序输出：联接成的多位数 程序输入： n（n9）表示行数。 以下 n 行，每行包括 n 个字符串，每个字串间 用空格隔开。 （字串仅有一个为+号，其它都 由大写字母组成） 程序输出： 各个字母表示什么数，格式如：L=0， K=1， 加法运算是几进制的。 若不可能组成加法表， 则应输出“ERROR！ ” +LKVE LLKVE KKVEKL VVEKLKK EEKLKKKV 2 第二题回文数第二题回文数 若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。 例如：给定一个 10 进制数 56，将 56 加 65（即
5、把 56 从右向左读） ，得到 121 是一个回文数。 又如：对于 10 进制数 87： STEP1：87+78= 165STEP2：165+561 = 726 STEP3：726+627 = 1353STEP4：1353+3531 = 4884 在这里的一步是指进行了一次 N 进制的加法，上例最少用了 4 步得到回文数 4884。 写一个程序，给定一个 N（2=1。 要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 2 位。 提示：记方程 f(x)=0，若存在 2 个数 x1 和 x2，且 x1 从 取 3 张牌放到 （9 11 10 10）- 从 取 1 张牌
6、放到（10 10 10 10）。 输入输出样例输入输出样例 题二 字串变换题二 字串变换 问题描述问题描述: 已知有两个字串 A$, B$ 及一组字串变换的规则（至多 6 个规则）: A1$ - B1$ A2$ - B2$ 规则的含义为：在 A中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ 。 例如：A$abcdB$xyz 变换规则为： abc-xuud-yy-yz 则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为： abcd-xud-xy-xyz 共进行了三次变换，使得 A$ 变换为 B$。 输入输出样例输入输出样例 输 入输 入： 键盘输入文件名。文件格式：
7、N（N 堆纸牌，1 变换规则 . . / 所有字符串长度的上限为 20。 输出输出: 输出至屏幕。格式如下： 若在 10 步（包含 10 步）以内能将 A$ 变换 为 B$ ，则输出最少的变换步数；否则输出“NO ANSWER!“ abcd wyz abc xu ud y y yz 3 8 题三 自由落体题三 自由落体 问题描述问题描述: 在高为 H 的天花板上有 n 个小球，体积不计，位置分别为 0，1，2，n-1。在地面上有一个 小车（长为 L，高为 K，距原点距离为 S1）。已知小球下落距离计算公式为 d1/2*g*(t2)，其 中 g=10，t 为下落时间。地面上的小车以速度 V 前进
8、。如下图： 小车与所有小球同时开始运 动，当小球距小车的距离 Ti+1TK(180） ，并且在本学期内发表 1 篇或 1 篇以上论文的学生均可获得； 2)五四奖学金，每人 4000 元，期末平均成绩高于 85 分（85） ，并且班级评议成绩高于 80 分 （80）的学生均可获得； 3)成绩优秀奖，每人 2000 元，期末平均成绩高于 90 分（90）的学生均可获得； 4)西部奖学金，每人 1000 元，期末平均成绩高于 85 分（85）的西部省份学生均可获得； 5)班级贡献奖，每人 850 元，班级评议成绩高于 80 分（80）的学生干部均可获得； 只要符合条件就可以得奖，每项奖学金的获奖人数
9、没有限制，每名学生也可以同时获得多项奖学金。例 如姚林的期末平均成绩是 87 分，班级评议成绩 82 分，同时他还是一位学生干部，那么他可以同时获 得五四奖学金和班级贡献奖，奖金总数是 4850 元。 现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金 的条件） 。 【输入文件】 输入文件 scholar.in 的第一行是一个整数 N（1 时，第i 颗珠子的尾标记应该等于第 i+1 颗珠子的头标记。第 N 颗珠子的尾标记应该等 于第 1 颗珠子的头标记。 至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然 后按顺时针方
10、向确定其他珠子的顺序。 【输出文件】 输出文件 energy.out 只有一行，是一个正整数 E（E2.1*109），为一个最优聚合顺序所释放 的总能量。 【输入样例】 4 23510 【输出样例】 710 19 2金明的预算方案金明的预算方案 (budget.pas/c/cpp) 【问题描述】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更 让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于 某个主件的，下表就是一些主件
11、与附件的例子： 如果要买归类为附件的物品， 必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附件。 附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的 N 元。于是，他把每件物 品规定了一个重要度，分为 5 等：用整数 15 表示，第 5 等最重要。他还从因特网上查到了每件物品 的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格 与重要度的乘积的总和最大。 设第 j 件物品的价格为 vj， 重要度为 wj， 共选中了 k 件物品， 编号依次为 j1， j2， ，jk， 则所求的总和为： vj1*wj1+vj
12、2*wj2+vjk*wjk。（其中*为乘号） 请你帮助金明设计一个满足要求的购物单。 【输入文件】 输入文件 budget.in 的第 1 行，为两个正整数，用一个空格隔开： N m （其中 N（0，表示该物品为附件，q 是所属主件的编号） 【输出文件】 输出文件 budget.out 只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值 （30000）是事先给定的。 问：满足上述条件的不同的 r 共有多少个？ 我们再从另一角度作些解释：设 S 是长度为 w 的 01 字符串（即字符串 S 由 w 个“0”或“1”组成） ， S 对应于上述条件（3）中的 q。将 S 从右起划分
13、为若干个长度为 k 的段，每段对应一位 2k进制的数， 如果 S 至少可分成 2 段，则 S 所对应的二进制数又可以转换为上述的 2k进制数 r。 例：设 k=3，w=7。则 r 是个八进制数（23=8）。由于 w=7，长度为 7 的 01 字符串按 3 位一段分， 可分为 3 段（即 1，3，3，左边第一段只有一个二进制位），则满足条件的八进制数有： 2 位数：高位为 1：6 个（即 12，13，14，15，16，17），高位为 2：5 个，高位为 6：1 个 （即 67）。共 6+5+1=21 个。 3 位数：高位只能是 1，第2 位为 2： 5 个（即 123， 124， 125， 12
14、6， 127），第2 位为 3：4 个， ， 第 2 位为 6：1 个（即 167）。共 5+4+1=15 个。 所以，满足要求的 r 共有 36 个。 【输入文件】 输入文件 d i g i t a l . i n 只有 1 行，为两个正整数，用一个空格隔开： kW 【输出文件】 输出文件 d i g i t a l . o u t 为 1 行，是一个正整数，为所求的计算结果，即满足条件的不同的 r 的个数 （用十进制数表示），要求最高位不得为 0，各数字之间不得插入数字以外的其他字符（例如空格、换 行符、逗号等）。 （提示：作为结果的正整数可能很大，但不会超过 200 位） 【输入样例】
15、37 【输出样例】 36 22 NOIP2007 1统计数字统计数字 (count.pas/c/cpp) 【问题描述】 某次科研调查时得到了 n 个自然数，每个数均不超过 1500000000（1.5* 109） 。已知不相同的数不超 过 10000 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。 【输入输出样例】 【限制】 40%的数据满足：1=0） 3.n 根火柴棍必须全部用上 【输入】输入文件 matches.in 共一行，又一个整数 n（n 当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，是另外一个可行 的操作序列。Tom 希望知道其中
16、字典序最小的操作序列是什么。 【输入】 输入文件 twostack.in 的第一行是一个整数 n。 第二行有 n 个用空格隔开的正整数，构成一个1n 的排列。 【输出】 输出文件 twostack.out 共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字 典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。 【输入输出样例1】 【输入输出样例2】 【输入输出样例3】 【限制】 30%的数据满足：n2-3-5，并在 2 号城市以 3 的价格买入水晶球，在 3 号城市以 5 的价格卖出水晶球，赚取的旅费数为 2。 阿龙也可以选择如下一条线路： 1-4-5-4-5， 并在第 1 次到达 5 号城市时以 1 的价格买入水晶球， 在第 2 次到达 4 号城市时以 6 的价格卖出水晶球，赚取的旅费数为 5。 现在给出 n 个城市的水晶球价格，m 条道路的信息（
