NOIP2016提高组复赛试题

《NOIP2016提高组复赛试题》由会员分享，可在线阅读，更多相关《NOIP2016提高组复赛试题（29页珍藏版）》请在装配图网上搜索。

1、第22届全国青少年信息学奥林匹克联赛2016提高组（复赛）第一试竞赛时间：2016年11月19日8:3012:00题目名称玩具谜题天天爱跑步换教室题目类型传统型传统型传统型目录可执行文件名输入文件名输出文件名每个测试点时限1.0秒2.0秒1.0秒内存限制512512512测试点数目202025每个测试点分值554提交源程序文件名对于语言对于C 语言对于语言编译选项对于语言对于C 语言对于语言注意事项：1. 文件名（程序名和输入输出文件名）必须使用英文小写。2. 除非特殊说明，结果比较方式均为忽略行末空格及文末回车的 全文比较。3. 中函数（）的返回值类型必须是，程序正常结束时的返回值 必须是0

2、。4. 全国统一评测时采用的机器配置为：（）x2 240，2.8， 内存4G，上述时限以此配置为准。5. 只提供 格式附加样例文件。6. 评测在下进行。7. 编译时不打开任何优化选项。玩具谜题（）【问题描述】小南有一套可爱的玩具小人，它们各有不同的职业。有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小 人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。如下图：这时告诉小南一个谜题：“眼镜藏在我左数第3个玩具小人的 右数第1个玩具小人的左数第2个玩具小人那里。”小南发现，这个谜题中玩具小人的朝向非常关键，因为朝内和朝 外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边 是顺时针

3、方向，右边是逆时针方向；而面向圈外的玩具小人，它的左 边是逆时针方向，右边是顺时针方向。小南一边艰难地辨认着玩具小人，一边数着：“朝内，左数第3个是。“朝外，右数第1个是。“朝外，左数第2个是。“所以眼镜藏在 这里！”虽然成功找回了眼镜，但小南并没有放心。如果下次有更多的玩 具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。 所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描 述为：有n个玩具小人围成一圈，己知它们的职业和朝向。现在第 1 个玩具小人告诉小南一个包含m条指令的谜题，其中第i条指令形如“左数/右数第 个玩具小人”。你需要输出依次数完这些指令后，到 达的玩具小

4、人的职业。【输入格式】从文件中读入数据。输入的第一行包含两个正整数，表示玩具小人的个数和指令的 条数。接下来n行，每行包含一个整数和一个字符串，以逆时针为顺 序给出每个玩具小人的朝向和职业。其中0表示朝向圈内，斥示 朝向圈外。保证不会出现其他的数。字符串长度不超过10且仅由小 写字母构成，字符串不为空，并且字符串两两不同。整数和字符串之 间用一个空格隔开。接下来m行，其中第i行包含两个整数，表示第i条指令。 若二0，表示向左数 个人；若二1，表示向右数 个人。保证 不会出现其他的数，1 W n。【输出格式】输出到文件 中。输出一个字符串，表示从第一个读入的小人开 始，依次数完m条指令后到达的小

5、人的职业。【样例1输入】7 300011010 31 10 2【样例1输出】【样例1说明】这组数据就是【题目描述】中提到的例子。【样例2输入】 10 10 1 c 0 r 0 p 1 d 1 e 1 m 1 t 1 y 1 u 0 v 1 7 1 1 1 4 0 5 0 3 0 1 1 6 1 2 0 8 0 4【样例2输出】 y【子任务】子任务会给出部分测试数据的特点。如果你在解决题目中遇到了 困难，可以尝试只解决一部分测试数据。每个测试点的数据规模及特点如下表：测试点nm全朝内全左数=1职业长度为11=20103寸寸寸寸2X3寸X4X5寸寸X6X7寸X8X9寸寸寸X10X11寸X12X13

6、寸寸X14X15寸X16X17105105寸寸18X19寸X20X其中一些简写的列意义如下：全朝内：若为“J”，表示该测试点保证所有的玩具小人都朝向 圈内；全左数：若为“J”，表示该测试点保证所有的指令都向左数，即 对任意的1 W i W m, = 0 ； = 1 ：若为“”，表示该测试点保证所有的指令都只数1个， 即对任意的1 W i W m， = 1 ；职业长度为1：若为“”，表示该测试点保证所有玩具小人的职 业一定是一个长度为1的字符串。天天爱跑步（）【问题描述】小C同学认为跑步非常有趣，于是决定制作一款叫做天天爱跑 步的游戏。天天爱跑步是一个养成类游戏，需要玩家每天按时上线，完成打 卡

7、任务。这个游戏的地图可以看作一棵包含n个结点和n - 1条边的树， 每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上 结点编号为从1到n的连续正整数。现在有m个玩家，第i个玩家的起点为，终点为。每天打 卡任务开始时，所 有玩家在第0秒同时从自己的起点出发，以每 秒跑一条边的速度，不间断地沿着 最短 路径向着自己的终点跑去， 跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以 每个人的路径是唯一的）小C想知道游戏的活跃度，所以在每个结点上都放置了一个观 察员。在结点j的观察员会选择在第 秒观察玩家，一个玩家能 被这个观察员观察到当且仅当该玩家 在第 秒也正好到达了结点 j。

8、小c想知道每个观察员会观察到多少人？ 一注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏， 他不能等待一段时间后再被观察员观察到。即对于把结点j作为终 点的玩家：若他在第 秒前到达 终点，则在结点j的观察员不能观 察到该玩家；若他正好在第秒到达终点，则在结点j的观察顽 以观察到这个玩家【输入格式】从文件中读入数据。第一行有两个整数n和m。其中n代表树的结点数量，同时也是 观察员的数量，m代表玩家的数量。接下来n - 1行每行两个整数u和v，表示结点u到结点v有 一条边。接下来一行n个整数，其中第j个整数为，表示结点j出现观 察员的时间。接下来m行，每行两个整数和，表示一个玩家的起点和终

9、点。对于所有的数据，保证1 W , W n，0 W W n。【输出格式】输出到文件中。输出1行n个整数，第j个整数表示结点j的观察员可以观察到 多少人。【样例1输入】6 32 31 21 44 54 60 2 5 1 2 31 51 32 6【样例1输出】2 0 0 1 1 1【样例1说明】对于1号点，W = 0 ,故只有起点为1号点的玩家才会被观察 到，所以玩家1和玩家2被观察到，共2人被观察到。对于2号点，没有玩家在第2秒时在此结点，共0人被观察到。对于3号点，没有玩家在第5秒时在此结点，共0人被观察到。对于4号点，玩家1被观察到，共1人被观察到。对于5号点，玩家1被观察到，共1人被观察到

10、。对于6号点，玩家3被观察到，共1人被观察到。【样例2输入】5 31 22 32 41 50 1 0 3 03 11 45 5【样例2输出】1 2 1 0 1【子任务】每个测试点的数据规模及特点如下表所示。提示：数据范围的个 位上的数字可以帮助判断是哪一种数据类型。测试点编1fnm约定号1=991=991所有人的起点等于自己的终点，即=23=992=992=045=993=993无6=99994=99994树退化成一条链，其中1与2有 边，2与3有边，.，n - 1与n有边789=99995=99995所有的=110111213=99996=99996所有的=114151617=99997=9

11、9997无181920=299998=299998【提示】如果你的程序需要用到较大的栈空间（这通常意味着需要较深层 数的递归），请务必仔细阅读选手目录下的文档，以了解在最终评 测时栈空间的限制 与在当前工作环境下调整栈空间限制的方法。换教室()【问题描述】对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际 情况申请合适的课程。在可以选择的课程中，有2n节课程安排在n个时间段上。在第 i (1 W i W n )个时间段上，两节内容相同的课程同时在不同的地 点进行，其中，牛牛预先被安排在教室上课，而另一节课程在教室 进行。在不提交任何申请的情况下，学生们需要按时间段的顺序依次完 成所有的n

12、节安排好的课程。如果学生想更换第i节课程的教室， 则需要提出申请。若申请通过，学生就可以在第i个时间段去教室 上课，否则仍然在教室上课。由于更换教 室的需求太多，申请不一定能获得通过。通过计算， 牛牛发现申请更换第i节课程的教室时，申请被通过的概率是一个 己知的实数，并且对于不同课程的申请，被通过的概率是互相独立 的。学校规定，所有的申请只能在学期开始前一次性提交，并且每个 人只能选择至多m节课程进行申请。这意味着牛牛必须一次性决定 是否申请更换每节课的教室，而 不能根据某些课程的申请结果来决 定其他课程是否申请；牛牛可以申请自己最希望更 换教室的m门课 程，也可以不用完这山个申请的机会，甚至

13、可以一门课程都不申请。因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要 利用课间时间从一间教室赶到另一间教室。牛牛所在的大学有v个教室，有e条道路。每条道路连接两间 教室，并且是可 以双向通行的。道路的长度和拥堵程度不同，通过不同的道路耗费的体力可 能会有所不同。当第i ( 1 W i W n 1 )节课结束后，牛牛就 会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课 的教室。现在牛牛想知道，申请哪几门课程可以使他因在教室间移动 耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费 的体力值的总和的期望值最小，请你

14、帮他求出这个最小值。【输入格式】从文件中读入数据。第一行四个整数n, m, v, e。n表示这个学期内的时间段的数 量；m表示牛牛最多可以申请更换多少节课程的教室；v表示牛 牛学校里教室的数量；e表示牛牛的学校 里道路的数量。第二行n个正整数，第i ( 1 W i W n )个正整数表示，即 第i个时间段牛牛被安 排上课的教室；保证1 W W v。第三行n个正整数，第i ( 1 W i W n )个正整数表示， 即第i个时间段另一间上同样课程的教室；保证1 W W v。第四行n个实数，第i ( 1 W i W n )个实数表示，即牛 牛申请在第i个时间段更 换教室获得通过的概率。保证0 W W

15、1。接下来e行，每行三个正整数，表示有一条双向道路连 接教室，通过这条道路需要耗费的体力值是；保证1 W , W v， 1 W W 100。保证 1 W n W 2000，0 W m W 2000，1 W v W 300，0 W e W 90000 。保证通过学校里的道路，从任何一间教室出发，都能到达其他所有 的教室。保证输入的实数最多包含3位小数。【输出格式】输出到文件中。输出一行，包含一个实数，四舍五入精确到小数点后恰好2位， 表示答案。你的输出必须和标准输蛀全一样才算正确。测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 4X10-3。(如果你不知道什么是浮点误差，这段话可以理解

16、为：对 于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊 的处理)【样例1输入】3 2 3 32 1 21 2 10.8 0.2 0.51 2 51 3 32 3 1【样例1输出】2.80【样例1说明】所有可行的申请方案和期望收益如下表:申请更换教室 的时间段申请通过的时 间段出现的概率耗费的体力值耗费的体力值 的期望无无1.088.0110.844.8无0.28220.206.4无0.88330.546.0无0.581、21、20.1644.4810.64420.040无0.1681、31、30.402.810.4430.14无0.182、32、30.145.220.1030.4

17、4无0.48【样例2】见选于目录下的2与2。【提示】1. 道路中可能会有多条双向道路连接相同的两间教室。也有可能有道 路两端连接的是同一间教室。2. 请注意区分n, m, v, e的意义，n不是教室的数量，m不是道路 的数量。【子任务】测试点nmV特殊性质特殊性质1 1 1 30022 2 0 203 1 1004 2 3005 3 0 20寸寸6 1 100X7 2 300X8 10 0寸寸9 1 20X10 2 100X11 10 300寸12 20 0 20寸X13 1 100X14 2 300寸15 20X寸16 300 0 20X17 1 10018 2 300寸寸19 300X20

18、 2000 0 20X21 122 2 10023 200024 30025特殊性质1:图上任意两点，N间，存在一条耗费体 力最少的路径只 包含一条道路。特殊性质2：对于所有的1 W i W n ,= 1。第22届全国青少年信息学奥林匹克联赛2016提高组（复赛）第二试竞赛时间：2016年11月20日8:3012:00题目名称组合数问题蚯蚓愤怒的小鸟题目类型传统型传统型传统型目录可执行文件名输入文件名输出文件名每个测试点时限1.0秒1.0秒2.0秒内存限制512512512测试点数目202020每个测试点分值555提交源程序文件名对于语言对于C 语言对于语言编译选项对于语言对于C 语言对于语言

19、注意事项：1. 文件名（程序名和输入输出文件名）必须使用英文小写。2. 除非特殊说明，结果比较方式均为忽略行末空格及文末回车的 全文比较。3. 中函数（）的返回值类型必须是，程序正常结束时的返回值 必须是0。4. 全国统一评测时采用的机器配置为：（）x2 240， 2.8,内存4G，上述时限以此配置为准。5. 只提供 格式附加样例文件。6. 评测在下进行。7. 编译时不打开任何优化选项。组合数问题()【问题描述】组合数L表示的是从n个物品中选出m个物品的方案数。举 个例子，从(1, 2, 3)三个物品中选择两个物品可以有(1, 2),(1, 3),(2, 3)这三种选择方法。根据组合数的定义，

20、我们可以给出计算 组合数L的一般公式：两！其中 n! = 1 X 2 X Xn。小葱想知道如果给定n, m和k ,对于所有的0 W i W n, 0 W ij W (i, m)有多少对(i, j)满足,一是k的倍数。【输入格式】从文件中读入数据。第一行有两个整数t, k，其中t代表该测试点总共有多少组测试数据，k的意义见【问题描述】。接下来t行每行两个整数n, m，其中n, m的意义见【问题描述】。【输出格式】输出到文件中。t行，每行一个整数代表所有的0 W i W n, 0 Wj W (i, m)中有多少对(i, j)满足匚是k的倍数。【样例1输入】1 23 3【样例1输出】1【样例1说明】

21、在所有可能的情况中，只有=2是2的倍数。【样例2输入】2 54 56 7【样例2输出】07【子任务】测试点nmkt1 3 3=2=12=3 1043 7 7=4=14=5 1045 10 10=6=16=7 1047 20 100=8=18=9 1049 25 2000=10=110=11 10411 60 20=12=112=13 10413 100 25=14=114=15 10415 60=16=116=17 10417 2000 100=18=118=19 10419 2000=20=120=21 104蚯蚓（）【问题描述】本题中，我们将用符号 表示对C向下取整，例如：L3.0J =

22、L3.1J=L3.9J = a岫岫国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，岫 岫国王只好去请神刀手来帮他们消灭蚯蚓。岫岫国里现在共有n只蚯蚓（n为正整数）。每只蚯蚓拥有长度， 我们设第i只蚯蚓的长度为（i=1, 2, . . . , n ），并保证所有 的长度都是非负整数（即：可能存在长度为0的蚯蚓）。每一秒刀手会在所有的蚯蚓中，准确地找到最长的那一只（如 有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数P（是满足0 P 1的有理数）决定，设这只蚯蚓长度为x，神刀手会 将其切成两只长度分别为 和x 的蚯蚓。特殊地，如果这两个数的其 中一个等于0，则这个长度为0的蚯蚓也会被

23、保留。此夕卜，除了刚刚产 生的两只新蚯蚓，其余蚯蚓的长度都会增加q （是一个非负整常数）。岫岫国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会 越来越长。岫 岫国王决定求助于一位有着洪荒之力的神秘人物，但是 救兵还需要m秒才能到来（m为非负整数）岫岫国王希望知道这m秒内的战况。具体来说，他希望知道： m秒内，每一秒被切断的蚯蚓被切断前的长度（有m个数）； m秒后，所有蚯蚓的长度（有n + m个数）。岫岫国王当然知道怎么做啦!但是他想考考你【输入格式】从文件中读入数据。第一行包含六个整数n, m, q, u, v, t，其中：n, m, q的意义见 【问题描述】；u, v, t均 为正整数

24、；你需要自己计算p =（保证0 u v ）； t是输出参数，其含义将会在【输出格式】中解释。第二行包含n个非负整数，为 a、.，即初始时n只蚯 蚓的长度。1 2同一行中相邻的两个数之间，恰好用一个空格隔开。保证 1WnW 105 ， 0WmW 7 X 106 ， 0 uvW109 ， 0 W q W 200 ， 1 W t W 71 ，0 W W 108。【输出格式】输出到文件m第一行输出切个整数，按时间顺序，依次输出第t秒，第2t秒，第3t秒，被切 断蚯蚓（在被切断前）的长度。第二行输出一一个整数，输出m秒后蚯蚓的长度：需要按从 大到小的顺序，依次输出排名第t，第2t，第3t，的长度。同一行

25、中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有 任何数需要输出，你也应输出一个空行。请阅读样例来更好地理解这个格式。【样例1输入】3 7 1 1 3 13 3 2【样例1输出】3 4 4 4 5 5 66 6 6 5 5 4 4 3 2 2【样例1说明】在神刀手到来前：3只蚯蚓的长度为3,3,2。1秒后：一只长度为3的蚯蚓被切成了两只长度分别为1和2的 蚯蚓，其余蚯蚓的长度增加了 1。最终4只蚯蚓的长度分别为(1,2),4,3。 括号表示这个位置刚刚有一只蚯蚓被切断。2秒后：一只长度为4的蚯蚓被切成了 1和3。5只蚯蚓的长度分别 为：2,3,(1,3),4。3秒后：一只长度为4的蚯蚓被

26、切断。6只蚯蚓的长度分别为：3.4.2.4, (1,3)。4秒后：一只长度为4的蚯蚓被切断。7只蚯蚓的长度分别为： 4,(1,3),3,5,2,4。5秒后：一只长度为5的蚯蚓被切断。8只蚯蚓的长度分别为：5.2.4.4, (1,4),3,5。6秒后：一只长度为5的蚯蚓被切断。9只蚯蚓的长度分别为： (1,4),3,5,5,2,5,4,6。7秒后：一只长度为6的蚯蚓被切断。10只蚯蚓的长度分别为： 2,5,4,6,6,3,6,5,(2,4)。所以，7秒内被切断的蚯蚓的长度依次为3,4,4,4,5,5,6。7秒后，所有蚯蚓长度从大到小排序为6,6,6,5,5,4,4,3,2,2。【样例2输入】 3

27、 7 1 1 3 2 3 3 2【样例2输出】4 4 56 5 4 3 2【样例2说明】这个数据中只有t = 2与上个数据不同。只需在每行都改为每两 个数输出一个数即可。虽然第一行最后有一个6没有被输出，但是第二行仍然要重新从 第二个数再开始输出。【样例3输入】3 7 1 1 3 93 3 2【样例3输出】2【样例3说明】这个数据中只有t = 9与上个数据不同。注意第一行没有数要输 出，但也要输出一个空行。【子任务】测试点1 3满足m = 0。测试点4 7满足n, m W 1, 000。测试点8 14满足q = 0 ,其中测试点89还满足mW 105。测试点15 18满足m W 3 X 105

28、。测试点19 20没有特殊的约定，参见原始的数据范围。测试点1 12 , 15 16还满足v W 2 ,这意味着u, v的 唯一可能的取值是u = 1, v = 2 ,即p = 0.5。这可能会对解决 问题有特殊的帮助。每个测试点的详细数据范围见下表。测试点nmtVq1=101 106 202=1033=1054=11035=1036=1 2007=1038=5 x 1045 x 10409=1051052102 x 10621112.5 x 10626123.5 x 10636 107135 x 10651 109147 x 10671 10815=5 x 1045 x 1061 2 200

29、161.5 x 1062171051053 109183 x 1054193.5 x 10636207 x 10671愤怒的小鸟()【问题描述】最近沉迷于一款神奇的游戏无法自拔。简单来说，这款游戏是在一个平面上进行的。有一架弹弓位于(0, 0)处，每次可以用它向第一象限发射一只 红色的小鸟，小鸟们的飞行轨迹均为形如y = 2 +的曲线，其中a, b 是 指定的参数，且必须满足a 0。当小鸟落回地面(即x轴)时，它就会瞬间消失。在游戏的某个关卡里，平面的第一象限中有n只绿色的小猪，其中 第i只小猪所在的坐标为(,)。如果某只小鸟的飞行轨迹经过了 (,)，那么第i只小猪就会被消 灭掉，同时小鸟将会

30、沿着原先的轨迹继续飞行；如果一只小鸟的飞行轨迹没有经过(,)，那么这只小鸟飞行的全 过程就不会对第i只小猪产生任何影响。例如，若两只小猪分别位于(1, 3)和(3, 3)，可以选择发射一 只飞行轨迹为y =X2 + 4x的小鸟，这样两只小猪就会被这只小鸟一起消灭。而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。这款神奇游戏的每个关卡对 来说都很难，所以 还输入了一些神 秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格 式】中详述。假设这款游戏一共有T个关卡，现在 想知道，对于每一个关卡， 至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希 望由你告诉她。【输入格式】

31、从文件中读入数据。第一行包含一个正整数T，表示游戏的关卡总数。下面依次输入这T个关卡的信息。每个关卡第一行包含两个非负整数n, m，分别表示该关卡中的小猪数量和 输入的神秘指令类型。 接下来的n行中，第i行包含两个正实数，表示第i只小猪 坐标为(,)。数据保证同一个关卡中不存在两只坐标完全相同的小 猪。如果m = 0，表示 输入了一个没有任何作用的指令。如果m = 1，则这个关卡将会满足：至多用3 + 1-只小鸟即可消 灭所有小猪。如果m = 2，则这个关卡将会满足：一定存在一种最优解，其中 有一只小鸟消灭了至少3J只小猪。保证 1WnW 18 ， 0WmW 2 ， 0 , 10，输入中 的实

32、数均保留到小数点后两位。上文中，符号C-和 分别表示对c向上取整和向下取整，例如： 2.1-= 2.9-二3.0- = L3.0J = L3.1J = L3.9J = 3。【输出格式】输出到文件中。对每个关卡依次输出一行答案。输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪 最少需要的小鸟数量。【样例1输入】22 01.00 3.003.00 3.005 21.00 5.002.00 8.003.00 9.004.00 8.005.00 5.00【样例1输出】11【样例1说明】这组数据中一共有两个关卡。第一个关卡与【问题描述】中的情形相同，2只小猪分别位于 (1.00,3.00)和(

33、3.00,3.00),只需发射一只飞行轨迹为y = -x2 + 4x的 小鸟即可消灭它们。第二个关卡中有5只小猪，但经过观察我们可以发现它们的坐标都 在抛物线y = -x2 + 6x上，故 只需要发射一只小鸟即可消灭所有小猪。【样例2输入】 32 01.41 2.001.73 3.003 01.11 1.412.34 1.792.98 1.495 02.72 2.722.72 3.143.14 2.723.14 3.145.00 5.00【样例2输出】223【样例3输入】110 07.16 6.282.02 0.388.33 7.787.68 2.097.46 7.865.77 7.448.24 6.724.42 5.115.42 7.798.15 4.99【样例3输出】6【子任务】数据的一些特殊规定如下表:测试点编号n1 223 345 467 58 69 710 811 912 1013 121415 15161718 181920mT=0 10 30 10 30 10 30 10 30=1=2=0 15=1=2=0 5=1=2