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）

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

3、BBRRBBBB-R 顺序BBBRRBBBRRBBBRRBBBRRBBBRRBBBRR放置的方法总数为 12 种。 数据输入的方式为： N P1（颜色，为一个字母） N1（灯的数量） P2 N2 Q（结束标记，Q 本身不是灯的颜色） 程序要求：求出一种顺序的放置（排列）方案及放置（排列）方案总数。程序要求：求出一种顺序的放置（排列）方案及放置（排列）方案总数。3、积木块上的数字、积木块上的数字 设有一个四层的积木块，14 层积木块的数量依次为：5，6，7，8，如下图所示放置：815851691423414326其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。

4、计算的方法是：第三层的某个数据 A 是由第四层相邻的两个数据 B，C 经过某种计算后产生的：计算所用到的计算符为：+，-，且无优先级之分（自左向右计算） ，运算符最多为 2 个。 如： 3+45=35 54+3=23 可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的： A=BC+B 也就是：8=23+2，15=34+3，14=26+2 程序要求：程序要求： 给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的 积木图及计算公式。 输入数据不存在出错的情况，同时也不会超过整数的范围。 计算时可允许出现以下情况：A=B （即可理解为运算符的个数为

5、零）A=BB+B （即全部由 B 产生）ABC第二届第二届全国信息学奥林匹克分区联赛（全国信息学奥林匹克分区联赛（NOIP1996）复赛试题）复赛试题（提高组提高组 竞赛用时：竞赛用时：3 小时小时）1、比赛安排、比赛安排 设有有 2 n（np，其中 m 为数字串（长度8，其意义为：将 10 进制数 48，转换成 8 进制数输出。 输出结果为：48=603、挖地雷、挖地雷 在一个地图上有 N 个地窖（N 从 取 3 张牌放到 （9 11 10 10）- 从 取 1 张牌放到（10 10 10 10）。 输输 入入 键盘输入文件名。文件格式： N（N 堆纸牌，1 B1$A2$ - B2$ 规则的

6、含义为：在 A中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ 。 例如：A$abcd B$xyz 变换规则为：abc-xu ud-y y-yz 则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：abcd-xud-xy-xyz 共进行了三次变换，使得 A$ 变换为 B$。 输入输入 : 键盘输人文件名。文件格式如下：A$ B$A1$ B1$ A2$ B2$ |- 变换规则. . / 所有字符串长度的上限为 20。 输出输出 : 输出至屏幕。格式如下： 若在 10 步（包含 10 步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出“NO ANSWER!

7、“ 输入输出样例输入输出样例 b.in:abcd wyzabc xuud yy yz屏幕显示：33、自由落体（存盘名、自由落体（存盘名:NOIPG3） 问题描述问题描述 :在高为 H 的天花板上有 n 个小球，体积不计，位置分别为 0，1，2，n-1。在地面上有一个 小车（长为 L，高为 K，距原点距离为 S1）。已知小球下落距离计算公式为 d1/2*g*(t2)，其 中 g=10，t t 为下落时间。地面上的小车以速度为下落时间。地面上的小车以速度 V V 前进。前进。如下图如下图：小车与所有小球同时开始运动，当小球距小车的距离 Ti+1TK(180） ，并且在本学期内发表 1 篇或 1 篇

8、以上论文的学生均可获得； 2) 五四奖学金，每人 4000 元，期末平均成绩高于 85 分（85） ，并且班级评议成绩高于 80 分 （80）的学生均可获得； 3) 成绩优秀奖，每人 2000 元，期末平均成绩高于 90 分（90）的学生均可获得； 4) 西部奖学金，每人 1000 元，期末平均成绩高于 85 分（85）的西部省份学生均可获得； 5) 班级贡献奖，每人 850 元，班级评议成绩高于 80 分（80）的学生干部均可获得； 只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖 学金。例如姚林的期末平均成绩是 87 分，班级评议成绩 82 分，同时他还是

9、一位学生干部，那么他 可以同时获得五四奖学金和班级贡献奖，奖金总数是 4850 元。 现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获 得奖学金的条件） 。 【输入文件】 输入文件 scholar.in 的第一行是一个整数 N（1 0，表示该物品为附件，q 是所属主件的编号） 【输出文件输出文件】输出文件 budget.out 只有一个正整数，为不超过总钱数的物品的价格与重要度乘 积的总和的最大值（=0） 3）n 根火柴棍必须全部用上【输入】输入文件 matches.in 共一行，又一个整数 n（n当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，

10、是另外一个可行的操 作序列。Tom 希望知道其中字典序最小的操作序列是什么。【输入】输入文件 twostack.in 的第一行是一个整数 n。第二行有 n 个用空格隔开的正整数，构 成一个 1n 的排列。【输出】输出文件 twostack.out 共一行，如果输入的排列不是“可双栈排序排列” ，输出数字 0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。【输入输出样例 1】twostack.intwostack.out4 1 3 2 4a b a a b b a b【输入输出样例 2】twostack.intwostack.out4 2 3 4 10【输入输出样例 3】

11、twostack.intwostack.out3 2 3 1a c a b b d【限制】30%的数据满足： n2-3-5，并在 2 号城市以 3 的价格买入水晶球，在 3 号城市 以 5 的价格卖出水晶球，赚取的旅费数为 2。 阿龙也可以选择如下一条线路：1-4-5-4-5，并在第 1 次到达 5 号城市时以 1 的价格买入水 晶球，在第 2 次到达 4 号城市时以 6 的价格卖出水晶球，赚取的旅费数为 5。 现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该 条道路的通行情况） 。请你告诉阿龙，他最多能赚钱多少旅费。 【输入】输入文件名为 trade.

12、in。第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别 表示城市的数目和道路的数目。第二行 n 个正整数，每两个正整数之间用一个空格隔开，按标号顺 序分别表示这 n 个城市的商品价格。接下来 m 行，每行有 3 个正整数，x，y，z，每两个整数之间 用一个空格隔开。如果 z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这 条道路为城市 x 和城市 y 之间的双向道路。 【输出】输出文件 trade.out 共 1 行，包含 1 个整数，表示最多能赚取的旅费。如果没有进行贸 易，则输出 0。 【输入输出样例】 Trade.in Trade.out5 5

13、 4 3 5 6 1 1 2 1 1 4 1 2 3 2 3 5 1 4 5 25【数据范围】输入数据保证 1 号城市可以到达 n 号城市。对于 10%的数据，1n6。 对于 30%的数据，1n100。 对于 50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。 对于 100%的数据，1n，1m，1x，yn，1z2，1各城市水晶球价格100。4、靶形数独（、靶形数独（sudoku.pas/c/cpp）【问题描述】小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好 胜的他们想用数独来一比高堤但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教， Z

14、博士拿出了他最近发明的“靶形数独” ，作为这两个孩子比试的题目。 靶形数独的方格同普通数独一样，在 9 格宽9 格高的大九宫格中有 9 个 3 格宽3 格高的小 九宫格（用粗黑色线隔开的） 。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻 辑推理，在其他的空格上填入 1 到 9 的数字。每个数字在每个小九宫格内不能重复出现，每个数字 在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值， 而且如同一个靶子一样，离中心越近则分值越高。 （如下图）上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红色区域） 每个格子为 9 分

15、，再外面一圈（蓝色区域）每个格子为 8 分，蓝色区域外面一圈（棕色区域）每个 格子为 7 分，最外面一圈（白色区域）每个格子为 6 分，如上图所示。比赛的要求是：每个人必须 完成一个给定的数独（每个给定数独有可能有不同的填法） ，而且要争取更高的总分数。而这个总 分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总禾如图，在以下这个 已经填完数字的靶形数独游戏中，总分为 2829。游戏规定，将以总分数的高低决出胜负。由于求胜心切，小城找督了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。 【输入】输入文件名为 sudoku.in。一共 9 行，每行 9 个整数

16、（每个数都在 09 的范围内） ，表 示一个尚未填满的数独方格，未填满的空格用“0”表示。每两个数字之间用一个空格隔开。 【输出】输出文件 sudoku.out 共 1 行。输出可以得到的靶形数独的最高分数。如果这个数独无 解，则输出整数-1。 【输入输出样例 1】sudoku.inSudoku.out7 0 0 9 0 0 0 0 1 1 0 0 0 0 5 9 0 0 0 0 0 2 0 0 0 8 0 0 0 5 0 2 0 0 0 3 0 0 0 0 0 0 6 4 8 4 1 3 0 0 0 0 0 0 0 0 7 0 0 2 0 9 0 2 0 1 0 6 0 8 0 4 0 8 0 5 0 4 0 1 22829【输入输出样例 2】sudoku.inSudoku.out0 0 0 7 0 2 4 5 3 9 0 0 0 0 8 0 0 0 7 4 0 0 0 5 0 1 0 1 9 5 0 8 0 0 0 0 0 7 0 0 0 0 0 2 5 0 3 0 5 7 9 1 0 8 0 0 0 6 0 1 0 0 0 0 6 0 9 0 0 0 0 1 0 0 0 0 0 0 0 0 62852【数据范围】 40%的数据，数独中非 0 数的个数不少于 30。 80%的数据，数独中非 0 数的个数不少于 26。 100%的数据，数独中非 0 数的个数不少于 24。