NOIP竞赛模拟试题 5页

兴华中学模拟赛BYZSNOIP2016普及组复赛模拟赛试卷普及组（请选手务必仔细阅读本页内容）一．题目概况River中文题目名称BigSquareBadHairDayTallestCowHopscotch英文题目与子目录名jumpbigsqbadhairtallest可执行文件名jumpbigsqbadhairtallest输入文件名jump.inbigsq.inbadhair.intallest.in输出文件名jump.outbigsq.outbadhair.outtallest.out每个测试点时限1秒1秒1秒1秒测试点数目10101010每个测试点分值10101010附加样例文件有有有有结果比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统传统二．提交源程序文件名对于pascal语言jump.pasbigsq.pasbadhair.pastallest.pas对于c语言jump.cbigsq.cbadhair.ctallest.c对于c++语言jump.cppbigsq.cppbadhair.cpptallest.cpp三．编译命令（不包含任何优化开关）对于pascal语言fpcjump.pasfpcbigsq.pasfpcbadhair.pasfpctallest.pasgcc-ojumpgcc-obigsqgcc-obadhairgcc-otallest对于c语言jump.c-lmbigsq.c-lmbadhair.c-lmtallest.c-lmg++-ojumpg++-obigsqg++-obadhairg++-otallest对于c++语言jump.cpp-lmbigsq.cpp-lmbadhair.cpp-lmtallest.cpp-lm四．运行内存限制内存上限128M128M128M128M注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3、统一评测时采用的机器配置为：CPUP43.0GHz，内存2G，上述时限以此配置为准。4、特别提醒：评测在Windows下进行，评测软件为cena8.0。第1页共5页\n兴华中学模拟赛BYZSRiverHopscotch(jump.pas/c/cpp)【问题描述】每年，奶牛们都举办一种特殊的跳房子游戏，在这个游戏中，大家小心翼翼地在河中的岩石上跳。这个游戏在一条笔直的河中进行，以一块岩石表示开始，以另一块距离起点L单位长度的岩石表示结束。在这两块岩石中间还有N块岩石，每块的位置距离起点是Di个单位长度。玩这个游戏的时候，每头牛从开始的那块岩石想办法要跳到表示结束的那块岩石上。中间只能在从某块岩石跳跃到另一块岩石，反复的这样跳。当然，不够敏捷的牛永远跳不到终点，最终只能落入河中。农民John为他的牛感到自豪，每年都观看比赛。随着时间的推移，他对于那些胆小的只能跳过很短距离的牛感到厌烦。为了那些牛，其他农民会把岩石的间距弄得很小。他计划移除一些岩石，从而增加奶牛在跳跃时需要的最短距离。他不能移除开始和结束的两块岩石。但是除此之外他可以移除M块岩石。FJ希望知道他能够增加多少最短跳跃距离。求当他移除了M块岩石后，奶牛从开始跳到结束的岩石，每次跳跃的最短距离至多可以增加到多少。【输入格式】第1行:三个用空格分开的整数，分别是L,N和M。第2..N+1行:每行一个整数，表示中间N块岩石的位置，没有两块岩石处于同一位置。【输出格式】输出共一行一个整数，表示移除某M块岩石后，相邻岩石间距最小值的最大可能情况。【输入样例】2552214112117【输出样例】4【输入说明】中间有5块岩石，坐标2,11,14,17和21。开始岩石在0，结束岩石在25。【输出解释】没有移除任何岩石之前，最少需要跳2个单位长度，从0到2。当移除了位于2和14的两块岩石后,需要的最短跳跃距离就变成了4。(从17到21或从21到25)。【数据规模】对于30%的数据：0≤N≤100；对于50%的数据：0≤N≤5,000；对于100%的数据：1≤L≤1,000,000,000；0≤N≤50,000；0==============123456第3页共5页\n兴华中学模拟赛BYZS牛#1可以看到的凌乱发型#2,3,4牛#2不能看到任何牛的发型牛#3可以看到的凌乱发型#4牛#4不能看到任何牛的发型牛#5可以看到的凌乱发型#6牛#6不能看到任何牛的发型！c[i]表示第i头牛可以看到发型的牛的数量；请输出c[1]至c[N]的和。如上面的这个例子，正确解是3+0+1+0+1+0=5。【输入格式】第1行:牛的数量N。第2..N+1行:第i+1是一个整数，表示第i头牛的高度。【输出格式】输出共一行一个整数，表示c[1]至c[N]的和。【输入样例】610374122【输出样例】5【数据规模】对于40%的数据：1≤N≤1,000；对于100%的数据：1≤N≤80,000；1≤h[i]≤1,000,000,000；TallestCow(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号奶牛的最大可能身高。第4页共5页\n兴华中学模拟赛BYZS【输入样例】93551353433798【输出样例】545344555【输入说明】共计9头奶牛，第3头奶牛的最大身高为5.【数据规模】对于40%的数据：1≤N≤100；1≤H≤1,000；0≤R≤100；对于70%的数据：1≤N≤1000；1≤H≤5,000；0≤R≤1,000；对于100%的数据：1≤N≤10,000；1≤H≤1,000,000；0≤R≤10,000；a≠b；第5页共5页