《NOIP历年复赛提高组试题(2004-2013).pdf》由会员分享，可在线阅读，更多相关《NOIP历年复赛提高组试题(2004-2013).pdf（73页珍藏版）》请在金锄头文库上搜索。
1、文档鉴赏 第十届全国信息学奥林匹克分区联赛 NOIP2004 复赛试题 提高组竞赛用时 3 小时 1 津津的储蓄计划 Save pas dpr c cpp 问题描述 津津的零花钱一直都是自己管理 每个月的月初妈妈给津津300 元钱 津津会预算这个月的花 销 并且总能做到实际花销和预算的相同 为了让津津学习如何储蓄 妈妈提出 津津可以随时把整百的钱存在她那里 到了年末她会加 上 20 还给津津 因此津津制定了一个储蓄计划 每个月的月初 在得到妈妈给的零花钱后 如果 她预计到这个月的月末手中还会有多于100 元或恰好100 元 她就会把整百的钱存在妈妈那里 剩 余的钱留在自己手中 例如 11 月初
2、津津手中还有83 元 妈妈给了津津300 元 津津预计11 月的花销是180 元 那么 她就会在妈妈那里存200 元 自己留下183 元 到了11 月月末 津津手中会剩下3 元钱 津津发现这个储蓄计划的主要风险是 存在妈妈那里的钱在年末之前不能取出 有可能在某个 月的月初 津津手中的钱加上这个月妈妈给的钱 不够这个月的原定预算 如果出现这种情况 津 津将不得不在这个月省吃俭用 压缩预算 现在请你根据2004 年 1 月到 12 月每个月津津的预算 判断会不会出现这种情况 如果不会 计算到 2004 年年末 妈妈将津津平常存的钱加上20 还给津津之后 津津手中会有多少钱 输入文件 输入文件sav
3、e in 包括 12 行数据 每行包含一个小于350 的非负整数 分别表示1 月到 12 月津 津的预算 输出文件 输出文件save out 包括一行 这一行只包含一个整数 如果储蓄计划实施过程中出现某个月钱 不够用的情况 输出 X X 表示出现这种情况的第一个月 否则输出到2004 年年末津津手中会有多 少钱 样例输入1 290 230 280 200 300 170 340 50 90 80 200 60 文档鉴赏 样例输出1 7 样例输入2 290 230 280 200 300 170 330 50 90 80 200 60 样例输出2 1580 文档鉴赏 2 合并果子 fruit p
4、as dpr c cpp 问题描述 在一个果园里 多多已经将所有的果子打了下来 而且按果子的不同种类分成了不同的堆 多 多决定把所有的果子合成一堆 每一次合并 多多可以把两堆果子合并到一起 消耗的体力等于两堆果子的重量之和 可以看 出 所有的果子经过n 1 次合并之后 就只剩下一堆了 多多在合并果子时总共消耗的体力等于每 次合并所耗体力之和 因为还要花大力气把这些果子搬回家 所以多多在合并果子时要尽可能地节省体力 假定每个 果子重量都为1 并且已知果子的种类数和每种果子的数目 你的任务是设计出合并的次序方案 使多多耗费的体力最少 并输出这个最小的体力耗费值 例如有 3 种果子 数目依次为1 2
5、 9 可以先将1 2 堆合并 新堆数目为3 耗费体力为3 接着 将新堆与原先的第三堆合并 又得到新的堆 数目为12 耗费体力为12 所以多多总共耗费 体力 3 12 15 可以证明15 为最小的体力耗费值 输入文件 输入文件fruit in包括两行 第一行是一个整数n 1 n 10000 表示果子的种类数 第二行 包含 n 个整数 用空格分隔 第i 个整数 ai 1 ai 20000 是第 i 种果子的数目 输出文件 输出文件fruit out 包括一行 这一行只包含一个整数 也就是最小的体力耗费值 输入数据保 证这个值小于231 样例输入 3 129 样例输出 15 数据规模 对于 30 的
6、数据 保证有n 1000 对于 50 的数据 保证有n 5000 对于全部的数据 保证有n 10000 文档鉴赏 3 合唱队形 chorus pas dpr c cpp 问题描述 N位同学站成一排 音乐老师要请其中的 N K 位同学出列 使得剩下的K位同学排成合唱队形 合唱队形是指这样的一种队形 设K位同学从左到右依次编号为1 2 K 他们的身高分别 为 T1 T2 TK 则他们的身高满足T1 Ti 1 TK 1 i K 你的任务是 已知所有N位同学的身高 计算最少需要几位同学出列 可以使得剩下的同学排 成合唱队形 输入文件 输入文件chorus in的第一行是一个整数N 2 N 100 表示
7、同学的总数 第一行有n 个整数 用空格分隔 第i 个整数 Ti 130 Ti 230 是第 i 位同学的身高 厘米 输出文件 输出文件chorus out包括一行 这一行只包含一个整数 就是最少需要几位同学出列 样例输入 8 186 186 150 200 160 130 197 220 样例输出 4 数据规模 对于50 的数据 保证有n 20 对于全部的数据 保证有n 100 文档鉴赏 4 虫食算 alpha pas dpr c cpp 问题描述 所谓虫食算 就是原先的算式中有一部分被虫子啃掉了 需要我们根据剩下的数字来判定被啃 掉的字母 来看一个简单的例子 43 9865 045 8468
8、 6633 44445509678 其中 号代表被虫子啃掉的数字 根据算式 我们很容易判断 第一行的两个数字分别是5 和 3 第二行的数字是5 现在 我们对问题做两个限制 首先 我们只考虑加法的虫食算 这里的加法是N进制加法 算式中三个数都有N位 允许有 前导的 0 其次 虫子把所有的数都啃光了 我们只知道哪些数字是相同的 我们将相同的数字用相同的 字母表示 不同的数字用不同的字母表示 如果这个算式是N进制的 我们就取英文字母表午的前 N个大写字母来表示这个算式中的0 到 N 1 这 N个不同的数字 但是这N个字母并不一定顺序地代 表 0到 N 1 输入数据保证N个字母分别至少出现一次 BAD
9、C CBDA DCCC 上面的算式是一个4 进制的算式 很显然 我们只要让ABCD 分别代表0123 便可以让这个式 子成立了 你的任务是 对于给定的N进制加法算式 求出N个不同的字母分别代表的数字 使得 该加法算式成立 输入数据保证有且仅有一组解 输入文件 输入文件alpha in包含 4 行 第一行有一个正整数N N 26 后面的3 行每行有一个由大写 字母组成的字符串 分别代表两个加数以及和 这3 个字符串左右两端都没有空格 从高位到低位 并且恰好有N位 输出文件 输出文件alpha out包含一行 在这一行中 应当包含唯一的那组解 解是这样表示的 输出 N个数字 分别表示A B C 所
10、代表的数字 相邻的两个数字用一个空格隔开 不能有多余的空 格 样例输入 5 ABCED BDACE EBBAA 样例输出 10342 数据规模 对于30 的数据 保证有N 10 对于 50 的数据 保证有N 15 对于全部的数 据 保证有N80 并且在本学期内发表1 篇或 1 篇以上论文的学生均可获得 2 五四奖学金 每人 4000 元 期末平均成绩高于85 分 85 并且班级评议成绩高于80 分 80 的学生均可获得 3 成绩优秀奖 每人2000 元 期末平均成绩高于90 分 90 的学生均可获得 4 西部奖学金 每人1000 元 期末平均成绩高于85 分 85 的西部省份学生均可获得 5
11、班级贡献奖 每人850 元 班级评议成绩高于80 分 80 的学生干部均可获得 只要符合条件就可以得奖 每项奖学金的获奖人数没有限制 每名学生也可以同时获得多项奖 学金 例如姚林的期末平均成绩是87 分 班级评议成绩82 分 同时他还是一位学生干部 那么他 可以同时获得五四奖学金和班级贡献奖 奖金总数是4850 元 现在给出若干学生的相关数据 请计算哪些同学获得的奖金总数最高 假设总有同学能满足获 得奖学金的条件 输入文件 输入文件scholar in 的第一行是一个整数N 1 N 100 表示学生的总数 接下来的N 行 每行是一位学生的数据 从左向右依次是姓名 期末平均成绩 班级评议成绩 是
12、否是学生干部 是否是西部省份学生 以及发表的论文数 姓名是由大小写英文字母组成的长度不超过20 的字符串 不含空格 期末平均成绩和班级评议成绩都是0 到 100 之间的整数 包括0 和 100 是否是学 生干部和是否是西部省份学生分别用一个字符表示 Y 表示是 N 表示不是 发表的论文数是0 到 10 的整数 包括0 和 10 每两个相邻数据项之间用一个空格分隔 输出文件 输出文件scholar out 包括三行 第一行是获得最多奖金的学生的姓名 第二行是这名学生获得 的奖金总数 如果有两位或两位以上的学生获得的奖金最多 输出他们之中在输入文件中出现最早 的学生的姓名 第三行是这N 个学生获得
13、的奖学金的总数 样例输入 4 YaoLin 87 82 Y N 0 ChenRuiyi 88 78 N Y 1 LiXin 92 88 N N 0 ZhangQin 83 87 Y N 1 样例输出 ChenRuiyi 9000 28700 文档鉴赏 2 过河 river pas c cpp 问题描述 在河上有一座独木桥 一只青蛙想沿着独木桥从河的一侧跳到另一侧 在桥上有一些石子 青 蛙很讨厌踩在这些石子上 由于桥的长度和青蛙一次跳过的距离都是正整数 我们可以把独木桥上 青蛙可能到达的点看成数轴上的一串整点 0 1 L 其中 L 是桥的长度 坐标为 0 的点表 示桥的起点 坐标为L 的点表示桥
14、的终点 青蛙从桥的起点开始 不停的向终点方向跳跃 一次跳 跃的距离是S到 T 之间的任意正整数 包括S T 当青蛙跳到或跳过坐标为L 的点时 就算青蛙已 经跳出了独木桥 题目给出独木桥的长度L 青蛙跳跃的距离范围S T 桥上石子的位置 你的任务是确定青蛙要 想过河 最少需要踩到的石子数 输入文件 输入文件river in 的第一行有一个正整数L 1 L 10 9 表示独木桥的长度 第二行有三个 正整数 S T M 分别表示青蛙一次跳跃的最小距离 最大距离 及桥上石子的个数 其中1 S T 10 1 M 100 第三行有 M 个不同的正整数分别表示这M 个石子在数轴上的位置 数 据保证桥的起点和
15、终点处没有石子 所有相邻的整数之间用一个空格隔开 输出文件 输出文件river out 只包括一个整数 表示青蛙过河最少需要踩到的石子数 样例输入 10 2 3 5 2 3 5 6 7 样例输出 2 数据规模 对于 30 的数据 L 10000 对于全部的数据 L 10 9 文档鉴赏 3 篝火晚会 fire pas c cpp 问题描述 佳佳刚进高中 在军训的时候 由于佳佳吃苦耐劳 很快得到了教官的赏识 成为了 小教官 在军训结束的那天晚上 佳佳被命令组织同学们进行篝火晚会 一共有n 个同学 编号从1 到 n 一开始 同学们按照1 2 n 的顺序坐成一圈 而实际上每个人都有两个最希望相邻的同学
16、 如何下命令调整同学的次序 形成新的一个圈 使之符合同学们的意愿 成为摆在佳佳面前的一大 难题 佳佳可向同学们下达命令 每一个命令的形式如下 b1 b2 bm 1 bm 这里 m 的值是由佳佳决定的 每次命令m 的值都可以不同 这个命令的作用是移动编号是b1 b2 bm 1 bm的这 m 个同学的位置 要求b1换到 b2的位置上 b2换到 b3的位置上 要 求 bm换到 b1的位置上 执行每个命令都需要一些代价 我们假定如果一个命令要移动m 个人的位置 那么这个命令的 代价就是m 我们需要佳佳用最少的总代价实现同学们的意愿 你能帮助佳佳吗 输入文件 输入文件fire in的第一行是一个整数n 3 n 50000 表示一共有n 个同学 其后n 行每 行包括两个不同的正整数 以一个空格隔开 分别表示编号是1 的同学最希望相邻的两个同学的编 号 编号是2 的同学最希望相邻的两个同学的编号 编号是n 的同学最希望相邻的两个同学 的编号 输出文件 输出文件fire out 包括一行 这一行只包含一个整数 为最小的总代价 如果无论怎么调整都不 能符合每个同学的愿望 则输出 1 样例输入 4 3 4
