《历届noip提高组复赛试题资料》由会员分享，可在线阅读，更多相关《历届noip提高组复赛试题资料（55页珍藏版）》请在金锄头文库上搜索。
1、 1 / 56 NOI95 “同创杯同创杯”全国青少年信息学（计算机）奥林匹克竞赛全国青少年信息学（计算机）奥林匹克竞赛 分区联赛复赛试题（高中组）分区联赛复赛试题（高中组） （上机编程，完成时间：（上机编程，完成时间：210 分钟）分钟） 编码问题：编码问题： 设有一个数组 A:ARRAY0N-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） 上
2、面数组 A 的编码为： B=（0，0，0，3，1，2） 程序要求解决以下问题：程序要求解决以下问题： 给出数组 A 后，求出其编码。 给出数组 A 的编码后，求出 A 中的原数据。 灯的排列问题：灯的排列问题： 设在一排上有 N 个格子（N20） ，若在格子中放置有不同颜色的灯，每种灯的个数记 为 N1，N2，Nk（k 表示不同颜色灯的个数） 。 放灯时要遵守下列规则：放灯时要遵守下列规则： 同一种颜色的灯不能分开； 不同颜色的灯之间至少要有一个空位置。 例如：N=8（格子数） R=2（红灯数） B=3（蓝灯数） 放置的方法有： R-B 顺序 RRBBB RRBBB RRBBB RRBBB R
3、RBBB RRBBB 2 / 56 B-R 顺序 BBBRR BBBRR BBBRR BBBRR BBBRR BBBRR 放置的总数为 12 种。 数据输入的方式为： N P1（颜色，为一个字母） N1（灯的数量） P2 N2 Q（结束标记，Q 本身不是灯的颜色） 程序要求：求出一种顺序的排列方案及排列总数。程序要求：求出一种顺序的排列方案及排列总数。 设有一个四层的积木块，14 层积木块的数量依次为：5，6，7，8 如下图所示放置： 8158516914 23414326 其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计 算出来的。 计算的方法是：第三层的某个数据
4、A 是由第四层相邻的两个数据 B，C 经过某种计算 后产生的： A BC 计算所用到的计算符为：+，-，且无优先级之分（自左向右计算） ，运算符最多为 2 个。 如：3+45=35 54+3=23 可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的： A=BC+B 也就是：8=23+2，15=34+3，14=26+2 程序要求：程序要求： 给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整 3 / 56 个完整的积木图及计算公式。 输入数据不存在出错的情况，同时也不会超过整数的范围。 计算时可允许出现以下情况： A=B （即可理解为运算符的个数为零）
5、 A=BB+B （即全部由 B 产生） 第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题第二届全国青少年信息学（计算机）奥林匹克分区联赛复赛试题 （高中组（高中组 竞赛用时：竞赛用时：3 小时）小时） 1比赛安排（20 分） 设有有 2 n（np 其中 m 为数字串（长度8 其意义为：将 10 进制数 48，转换成 8 进制数输出。 输出结果为：48=60 4挖地雷（30 分） 在一个地图上有 N 个地窖（N=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有 空格)，并精确到小数点后 2 位。 提示：记方程 f(x)=0，若存在 2 个数 x1 和 x2，且 x1 从 取 3
6、 张牌放到 （9 11 10 10）- 从 取 1 张牌放到（10 10 10 10） 。 输输 入入： 键盘输入文件名。文件格式： N（N 堆纸牌，1 B1$ A2$ - B2$ 规则的含义为：在 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$ |- 变换规则
7、. . / 所有字符串长度的上限为 20。 输出输出 : 输出至屏幕。格式如下： 若在 10 步（包含 10 步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出 “NO ANSWER!“ 输入输出样例输入输出样例 b.in: abcd wyz abc xu ud y y yz 屏幕显示： 3 题三 自由落体（存盘名:NOIPG3） 问题描述问题描述 : 在高为 H 的天花板上有 n 个小球，体积不计，位置分别为 0，1，2，n-1。在地面上 20 / 56 有一个小车（长为 L，高为 K，距原点距离为 S1）。已知小球下落距离计算公式为 d1/2*g*(t2)，其中 g=10，
8、t 为下落时间。地面上的小车以速度 V 前进。 如下图： 小车与所有小球同时开始运动，当小球距小车的距离 Ti+1TK(1，且不存在 Jam 数字 P，使 U）。你的任务是：对于从文件读入的一个 Jam 数字，按顺序输出紧接在后面 的 5 个 Jam 数字，如果后面没有那么多 Jam 数字，那么有几个就输出几个。 【输入文件】 37 / 56 输入文件 counting.in 有 2 行，第 1 行为 3 个正整数，用一个空格隔开： s t w （其中 s 为所使用的最小的字母的序号，t 为所使用的最大的字母的序号。 w 为数字的位数，这 3 个数满足：1s26, 2wt-s ） 第 2 行为
9、具有 w 个小写字母的字符串，为一个符合要求的 Jam 数字。 所给的数据都是正确的，不必验证。 【输出文件】 输出文件 counting.out 最多为 5 行，为紧接在输入的 Jam 数字后面的 5 个 Jam 数字，如果后面没有那么多 Jam 数字，那么有几个就输出几个。每行 只输出一个 Jam 数字，是由 w 个小写字母组成的字符串，不要有多余的空格。 【输入样例】 2 10 5 bdfij 【输出样例】 bdghi bdghj bdgij bdhij befgh 4.数列数列 （sequence.pas/c/cpp） 【问题描述】 38 / 56 给定一个正整数 k(3k15),把所
10、有 k 的方幂及所有有限个互不相等的 k 的方幂之和构成一个递增的序列，例如，当 k=3 时，这个序列是： 1，3，4，9，10，12，13， （该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32， ） 请你求出这个序列的第 N 项的值（用 10 进制数表示）。 例如，对于 k=3，N=100，正确答案应该是 981。 【输入文件】 输入文件 sequence.in 只有 1 行，为 2 个正整数，用一个空格隔开： k N （k、N 的含义与上述的问题描述一致，且 3k15，10N1000）。 【输出文件】 输出文件 sequence.out 为计算结果，
11、是一个正整数（在所有的测试数 据中，结果均不超过 2.1*109）。（整数前不要有空格和其他符号）。 【输入样例】 3 100 【输出样例】 981 2007 年 全国信息学奥林匹克联赛（全国信息学奥林匹克联赛（NOIP2007NOIP2007）复赛）复赛 39 / 56 提高组 题目一览题目一览 题目名称题目名称 统计数字统计数字字符串的展开字符串的展开矩阵取数游戏矩阵取数游戏树网的核树网的核 代号countexpandgamecore 输入文件count.inexpand.ingame.incore.in 输出文件count.outexpand.outgame.outcore.out 时限
12、1 秒1 秒1 秒1 秒 (2007 年年 11 月月 17 日日 3 小时完成小时完成) 说明： 1. 文件名（程序名和输入输出文件名）必须使用小写 2. C/C+中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3. 全国统一评测时采用的机器参考配置为：CPU 2.0GHz，内存 256M。 40 / 56 1统计数字统计数字 (count.pas/c/cpp) 【问题描述】 某次科研调查时得到了 n 个自然数，每个数均不超过 1500000000（1.5*109） 。已知不 相同的数不超过 10000 个，现在需要统计这些自然数各自出现的次数，并按照自然
13、数从小 到大的顺序输出统计结果。 【输入】 输入文件 count.in 包含 n+1 行： 第 1 行是整数 n，表示自然数的个数。 第 2n+1 行每行一个自然数。 【输出】 输出文件 count.out 包含 m 行（m 为 n 个自然数中不相同数的个数） ，按照自然数 从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个 空格隔开。 【输入输出样例】 count.incount.out 8 2 4 2 4 5 100 2 100 2 3 4 2 5 1 100 2 【限制】 40%的数据满足：1=0） 3. n 根火柴棍必须全部用上 【输入】 输入文件 matc
14、hes.in 共一行，又一个整数 n（n 当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，是另外一个 可行的操作序列。Tom 希望知道其中字典序最小的操作序列是什么。 【输入】 输入文件 twostack.in 的第一行是一个整数 n。 第二行有 n 个用空格隔开的正整数，构成一个 1n 的排列。 【输出】 输出文件 twostack.out 共一行，如果输入的排列不是“可双栈排序排列” ，输出数字 0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。 50 / 56 【输入输出样例 1】 twostack.intwostack.out 4 1 3 2 4
15、a b a a b b a b 【输入输出样例 2】 twostack.intwostack.out 4 2 3 4 1 0 【输入输出样例 3】 twostack.intwostack.out 3 2 3 1 a c a b b d 【限制】 30%的数据满足： n2-3-5，并在 2 号城市以 3 的价格 买入水晶球，在 3 号城市以 5 的价格卖出水晶球，赚取的旅费数为 2。 53 / 56 阿龙也可以选择如下一条线路 1-4-5-4-5，并在第 1 次到达 5 号 城市时以 1 的价格买入水晶球，在第 2 次到达 4 号城市时以 6 的价格卖出 水晶球，赚取的旅费数为 5。 现在给出
16、n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的 两个城市的编号以及该条道路的通行情况） 。请你告诉阿龙，他最多能赚取多 少旅费。 Input 第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别 表示城市的数目和道路的数目。 第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。 接下来 m 行， 每行有 3 个正整数， x， y， z， 每两个整数之间用一个空 格隔开。 如果 z=1，表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这条道路为城市 x 和城市 y 之间的双向道路。 Output 共 1 行， 包 含 1 个整数， 表示最多能赚取的旅费。 如果没有进行贸易，则输出
