NOIP竞赛模拟试题.pdf

兴华中学兴华中学 模拟赛模拟赛 BY ZS 第 1 页 共 5 页 NOIP201NOIP2016 6普及组复赛模拟赛试卷普及组复赛模拟赛试卷 普及组普及组 （请选手务必仔细阅读本页内容）（请选手务必仔细阅读本页内容） 一题目概况一题目概况 中文题目名称 River Hopscotch Big Square Bad Hair Day Tallest Cow 英文题目与子目录名 jump bigsq badhair tallest 可执行文件名 jump bigsq badhair tallest 输入文件名 jump.in bigsq.in badhair.in tallest.in 输出文件名 jump.out bigsq.out badhair.out tallest.out 每个测试点时限 1 秒 1 秒 1 秒 1 秒 测试点数目 10 10 10 10 每个测试点分值 10 10 10 10 附加样例文件 有 有 有 有 结果比较方式 全文比较（过滤行末空格及文末回车） 题目类型 传统 传统 传统 传统 二提交源程序文件名二提交源程序文件名 对于 pascal 语言 jump.pas bigsq.pas badhair.pas tallest.pas 对于 c 语言 jump.c bigsq.c badhair.c tallest.c 对于 c+ 语言 jump.cpp bigsq.cpp badhair.cpp tallest.cpp 三编译命令（不包含任何优化开关）三编译命令（不包含任何优化开关） 对于 pascal 语言 fpc jump.pas fpc bigsq.pas fpc badhair.pas fpc tallest.pas 对于 c 语言 gcc -o jump jump.c -lm gcc -o bigsq bigsq.c -lm gcc -o badhair badhair.c -lm gcc -o tallest tallest.c -lm 对于 c+ 语言 g+ -o jump jump.cpp -lm g+ -o bigsq bigsq.cpp -lm g+ -o badhair badhair.cpp -lm g+ -o tallest tallest.cpp -lm 四运行内存限制四运行内存限制 内存上限 128M 128M 128M 128M 注意事项：注意事项： 1、文件名（程序名和输入输出文件名）必须使用英文小写。 2、C/C+中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3、统一评测时采用的机器配置为：CPU P4 3.0GHz，内存 2G，上述时限以此配置为准。 4 4、特别提醒：评测、特别提醒：评测在在 WindowsWindows 下进行，评测下进行，评测软件为软件为 cena8.0cena8.0。 兴华中学兴华中学 模拟赛模拟赛 BY ZS 第 2 页 共 5 页 River Hopscotch (jump.pas/c/cpp) 【问题描述】【问题描述】 每年，奶牛们都举办一种特殊的跳房子游戏，在这个游戏中，大家小心翼翼地在河中的岩石上跳。 这个游戏在一条笔直的河中进行， 以一块岩石表示开始， 以另一块距离起点L单位长度的岩石表示结束。 在这两块岩石中间还有 N 块岩石，每块的位置距离起点是 Di 个单位长度。 玩这个游戏的时候，每头牛从开始的那块岩石想办法要跳到表示结束的那块岩石上。中间只能在从 某块岩石跳跃到另一块岩石， 反复的这样跳。 当然， 不够敏捷的牛永远跳不到终点， 最终只能落入河中。 农民 John 为他的牛感到自豪，每年都观看比赛。随着时间的推移，他对于那些胆小的只能跳过很 短距离的牛感到厌烦。为了那些牛，其他农民会把岩石的间距弄得很小。他计划移除一些岩石，从而增 加奶牛在跳跃时需要的最短距离。他不能移除开始和结束的两块岩石。但是除此之外他可以移除 M 块 岩石。 FJ 希望知道他能够增加多少最短跳跃距离。求当他移除了 M 块岩石后，奶牛从开始跳到结束的岩 石，每次跳跃的最短距离至多可以增加到多少。 【输入格式】【输入格式】 第 1 行: 三个用空格分开的整数，分别是 L, N 和 M。 第 2N+1 行: 每行一个整数，表示中间 N 块岩石的位置，没有两块岩石处于同一位置。 【输出格式】【输出格式】 输出共一行一个整数，表示移除某 M 块岩石后，相邻岩石间距最小值的最大可能情况。 【输入样例】【输入样例】 25 5 2 2 14 11 21 17 【输出样例】【输出样例】 4 【输入说明】【输入说明】中间有 5 块岩石，坐标 2, 11, 14, 17 和 21。开始岩石在 0，结束岩石在 25。 【输出解释】【输出解释】没有移除任何岩石之前，最少需要跳 2 个单位长度，从 0 到 2。当移除了位于 2 和 14 的 两块岩石后, 需要的最短跳跃距离就变成了 4。(从 17 到 21 或 从 21 到 25)。 【数据规模】【数据规模】 对于 30%的数据： 0N100； 对于 50%的数据： 0N5,000； 对于 100%的数据：1L1,000,000,000；0N50,000；0Di = = = = = = = = = = = = = = 1 2 3 4 5 6 兴华中学兴华中学 模拟赛模拟赛 BY ZS 第 4 页 共 5 页 牛#1 可以看到的凌乱发型 #2, 3, 4 牛#2 不能看到任何牛的发型 牛#3 可以看到的凌乱发型 #4 牛#4 不能看到任何牛的发型 牛#5 可以看到的凌乱发型 #6 牛#6 不能看到任何牛的发型！ ci 表示第 i 头牛可以看到发型的牛的数量；请输出 c1 至 cN的和。 如上面的这个例子，正确解是 3 + 0 + 1 + 0 + 1 + 0 = 5。 【输入格式】【输入格式】 第 1 行: 牛的数量 N。 第 2N+1 行: 第 i+1 是一个整数，表示第 i 头牛的高度。 【输出格式】【输出格式】 输出共一行一个整数，表示 c1 至 cN的和。 【输入样例】【输入样例】 6 10 3 7 4 12 2 【输出样例】【输出样例】 5 【数据规模】【数据规模】 对于 40%的数据： 1N1,000； 对于 100%的数据：1N80,000；1hi 1,000,000,000； Tallest Cow (tallest.pas/c/cpp) 【问题描述】【问题描述】 约翰的 N 只奶牛正站在一条直线上接受检阅，她们由 1 到 N 编号，每一只奶牛都有一个用正整数 表示的身高，你被告知最高奶牛的编号 I 和身高 H，但是其它奶牛的身高就不得而知了。 约翰提供了 R 条信息，每条信息用两个整数 a 和 b 表示，意味着 a 能看到 b。也就是说，b 的身高 不会小于 a，而且两只奶牛之间所有奶牛的身高均严格小于 a 的身高。 对每只奶牛，请计算最大的可能身高。使之不违反给出的信息，数据保证合理的身高一定存在。 【输入格式】【输入格式】 第 1 行输入 4 个整数.分别表示 N,I,H,R； 接下来 R 行每行输入两个整数 a 和 b。 【输出格式】【输出格式】 输出共 N 行，第 i 行表示第 i 号奶牛的最大可能身高。 兴华中学兴华中学 模拟赛模拟赛 BY ZS 第 5 页 共 5 页 【输入样例】【输入样例】 9 3 5 5 1 3 5 3 4 3 3 7 9 8 【输出样例】【输出样例】 5 4 5 3 4 4 5 5