NOIP2010普及组复赛试题.pdf_第1页
NOIP2010普及组复赛试题.pdf_第2页
NOIP2010普及组复赛试题.pdf_第3页
NOIP2010普及组复赛试题.pdf_第4页
NOIP2010普及组复赛试题.pdf_第5页
已阅读5页,还剩2页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

全国信息学奥林匹克联赛 NOIP1010 复赛 普及组 第 1 页 共 7 页 全国信息学奥林匹克联赛 全国信息学奥林匹克联赛 NOIP20NOIP201010 复赛 复赛 普及组 请选手务必仔细阅读本页内容 请选手务必仔细阅读本页内容 一一 题目概览题目概览 中文题目名称 数字统计 接水问题 导弹拦截 三国游戏 英文题目名称 two water missile sanguo 可执行文件名 two water missile sanguo 输入文件名 two in water in missile in sanguo in 输出文件名 two out water out missile out sanguo out 每个测试点时限 1 秒 1 秒 1 秒 1 秒 测试点数目 10 10 10 10 每个测试点分值 10 10 10 10 比较方式 全文比较 过滤行末空格及文末回车 题目类型 传统 传统 传统 传统 二二 提交源程序文件名提交源程序文件名 对于 pascal 语言 two pas water pas missile pas sanguo pas 对于 C 语言 two c water c missilel c sanguo c 对于 C 语言 two cpp water cpp missile cpp sanguo cpp 三三 编译命令 不包含任编译命令 不包含任何优化开关 何优化开关 对于 pascal 语言 fpc two pas fpc water pas fpc missile pas fpc sanguo pas 对于 C 语言 gcc o two Two c lm gcc o water water c lm gcc o missile ball c lm gcc o sanguo sanguo c lm 对于 C 语言 g o two two cpp lm g o seat water cpp lm g o missile missile cpp lm g o sanguo sanguo cpp lm 四四 运行内存限制运行内存限制 运行内存上限 128M 128M 128M 128M 注意事项 注意事项 1 文件名 程序名和输入输出文件名 必须使用英文小写 2 C C 中函数 main 的返回值类型必须是 int 程序正常结束时的返回值必须是 0 3 全国统一评测时采用的机器配置为 CPU P4 3 0GHz 内存 1G 上述时限以此配置为准 各省在自测时可根据具体配置调整时限 全国信息学奥林匹克联赛 NOIP1010 复赛 普及组 第 2 页 共 7 页 1 数字统计 数字统计 two pas c cpp 问题描述 请统计某个给定范围 L R 的所有整数中 数字 2 出现的次数 比如给定范围 2 22 数字 2 在数 2 中出现了 1 次 在数 12 中出现 1 次 在数 20 中出现 1 次 在数 21 中出现 1 次 在数 22 中出现 2 次 所以数字 2 在该范围内一共出现了 6 次 输入 输入文件名为 two in 输入共 1 行 为两个正整数 L 和 R 之间用一个空格隔开 输出 输出文件名为 two out 输出共 1 行 表示数字 2 出现的次数 输入输出样例 1 two in two out 2 22 6 输入输出样例 2 two in two out 2 100 20 数据范围 1 L R 10000 2 接水问题接水问题 water pas c cpp 问题描述 学校里有一个水房 水房里一共装有 m 个龙头可供同学们打开水 每个龙头每秒钟的供水量 相等 均为 1 现在有 n 名同学准备接水 他们的初始接水顺序已经确定 将这些同学按接水顺序从 1 到 n 编号 i 号同学的接水量为 wi 接水开始时 1 到 m 号同学各占一个水龙头 并同时打开水龙头 接水 当其中某名同学 j 完成其接水量要求 wj 后 下一名排队等候接水的同学 k 马上接替 j 同 学的位置开始接水 这个换人的过程是瞬间完成的 且没有任何水的浪费 即 j 同学第 x 秒结束 时完成接水 则 k 同学第 x 1 秒立刻开始接水 若当前接水人数 n 不足 m 则只有 n 个 龙头供水 其它 m n 个龙头关闭 现在给出 n 名同学的接水量 按照上述接水规则 问所有同学都接完水需要多少秒 全国信息学奥林匹克联赛 NOIP1010 复赛 普及组 第 3 页 共 7 页 输入 输入文件名为 water in 第 1 行 2 个整数 n 和 m 用一个空格隔开 分别表示接水人数和龙头个数 第 2 行 n 个整数 w1 w2 wn 每两个整数之间用一个空格隔开 wi 表示 i 号同学 的接水量 输出 输出文件名为 water out 输出只有一行 1 个整数 表示接水所需的总时间 输入输出样例 1 water in water out 5 3 4 4 1 2 1 4 输入输出样例 1 解释 第 1 秒 3 人接水 第 1 秒结束时 1 2 3 号同学每人的已接水量为 1 3 号同学接完水 4 号同学接替 3 号同学开始接水 第 2 秒 3 人接水 第 2 秒结束时 1 2 号同学每人的已接水量为 2 4 号同学的已接水 量为 1 第 3 秒 3 人接水 第 3 秒结束时 1 2 号同学每人的已接水量为 3 4 号同学的已接水 量为 2 4 号同学接完水 5 号同学接替 4 号同学开始接水 第 4 秒 3 人接水 第 4 秒结束时 1 2 号同学每人的已接水量为 4 5 号同学的已接水 量为 1 1 2 5 号同学接完水 即所有人完成接水 总接水时间为 4 秒 输入输出样例 2 water in water out 8 4 23 71 87 32 70 93 80 76 163 数据范围 1 n 10000 1 m 100 且 m n 1 wi 100 3 导弹拦截导弹拦截 missile pas c cpp 问题描述 经过 11 年的韬光养晦 某国研发出了一种新的导弹拦截系统 凡是与它的距离不超过其工 作半径的导弹都能够被它成功拦截 当工作半径为 0 时 则能够拦截与它位置恰好相同的导弹 但该导弹拦截系统也存在这样的缺陷 每套系统每天只能设定一次工作半径 而当天的使用代价 就是所有系统工作半径的平方和 某天 雷达捕捉到敌国的导弹来袭 由于该系统尚处于试验阶段 所以只有两套系统投入工作 如果现在的要求是拦截所有的导弹 请计算这一天的最小使用代价 全国信息学奥林匹克联赛 NOIP1010 复赛 普及组 第 4 页 共 7 页 输入 输入文件名 missile in 第一行包含 4 个整数 x1 y1 x2 y2 每两个整数之间用一个空格隔开 表示这两套导弹拦 截系统的坐标分别为 x1 y1 x2 y2 第二行包含 1 个整数 N 表示有 N 颗导弹 接下来 N 行 每行两个整数 x y 中间用 一个空格隔开 表示一颗导弹的坐标 x y 不同导弹的坐标可能相同 输出 输出文件名 missile out 输出只有一行 包含一个整数 即当天的最小使用代价 提示 两个点 x1 y1 x2 y2 之间距离的平方是 x1 x2 2 y1 y2 2 两套系统工作半径 r1 r2 的平方和 是指 r1 r2 分别取平方后再求和 即 r12 r22 输入输出样例 1 missile in missile out 0 0 10 0 2 3 3 10 0 18 样例 1 说明 样例 1 中要拦截所有导弹 在满足最小使用代价的前提下 两套系统工作半径的平方分别为 18 和 0 输入输出样例 2 missile in missile out 0 0 6 0 5 4 2 2 3 4 0 6 2 9 1 30 样例 2 说明 样例中的导弹拦截系统和导弹所在的位置如下图所示 要拦截所有导弹 在满足最小使用代价 的前提下 两套系统工作半径的平方分别为 20 和 10 全国信息学奥林匹克联赛 NOIP1010 复赛 普及组 第 5 页 共 7 页 数据范围 对于 10 的数据 N 1 对于 20 的数据 1 N 2 对于 40 的数据 1 N 100 对于 70 的数据 1 N 1000 对于 100 的数据 1 N 100000 且所有坐标分量的绝对值都不超过 1000 4 三国游戏三国游戏 sanguo pas c cpp 问题描述 小涵很喜欢电脑游戏 这些天他正在玩一个叫做 三国 的游戏 在游戏中 小涵和计算机各执一方 组建各自的军队进行对战 游戏中共有 N 位武将 N 为偶数且不小于 4 任意两个武将之间有一个 默契值 表示若此两位武将作为一对组合作 战时 该组合的威力有多大 游戏开始前 所有武将都是自由的 称为自由武将 一旦某个自由武 将被选中作为某方军队的一员 那么他就不再是自由武将了 换句话说 所谓的自由武将不属 于任何一方 游戏开始 小涵和计算机要从自由武将中挑选武将组成自己的军队 规则如下 小涵 先从自由武将中选出一个加入自己的军队 然后计算机也从自由武将中选出一个加入计算机方的军 队 接下来一直按照 小涵 计算机 小涵 的顺序选择武将 直到所有的武将被双方均分 完 然后 程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比 武 拥有更高默契值的一对武将组合获胜 表示两军交战 拥有获胜武将组合的一方获胜 已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合 它采取的具体策略 如下 任何时刻 轮到计算机挑选时 它会尝试将对手军队中的每个武将与当前每个自由武将进行 一一配对 找出所有配对中默契值最高的那对武将组合 并将该组合中的自由武将选入自己的军队 下面举例说明计算机的选将策略 例如 游戏中一共有 6 个武将 他们相互之间的默契值如 全国信息学奥林匹克联赛 NOIP1010 复赛 普及组 第 6 页 共 7 页 下表所示 双方选将过程如下所示 小涵想知道 如果计算机在一局游戏中始终坚持上面这个策略 那么自己有没有可能必胜 如 果有 在所有可能的胜利结局中 自己那对用于比武的武将组合的默契值最大是多少 假设整个游戏过程中 对战双方任何时候均能看到自由武将队中的武将和对方军队的武将 为 了简化问题 保证对于不同的武将组合 其默契值均不相同 输入 输入文件名为 sanguo in 共 N 行 第一行为一个偶数 N 表示武将的个数 第 2 行到第 N 行里 第 i 1 行有 N i 个非负整数 每两个数之间用一个空格隔开 表示 i 号武将和 i 1 i 2 N 号武将之间的默契值 0 默契值 1 000 000 000 输出 输出文件 sanguo out 共 1 或 2 行 若对于给定的游戏输入 存在可以让小涵获胜的选将顺序 则输出 1 并另起一行输出所有获 全国信息学奥林匹克联赛 NOIP1010 复赛 普及组 第 7 页 共 7 页 胜的情况中 小涵最终选出的武将组合的最大默契值 如果不存在可以让小涵获胜的选将顺序 则输出 0 输入输出样例 1 sanguo in sanguo out 6 5 28 16 29 27 23 3 20 1 8 32 26 33 11 12 1 32 输入输出样例说明 1 首先小涵拿走 5 号武将 计算机发现 5 号武将和剩下武将中的 4 号默契值最高 于是拿走 4 号 小涵接着拿走 3 号 计算机发现 3 5 号武将之一和剩下的武将配对的所有组合中 5 号和 1 号默契值最高 于是拿走 1 号 小涵接着拿走 2 号 计算机最后拿走 6 号 在小涵手里的 2 3 5 号武

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论