NOIP提高组复赛试题DayDay.doc

《NOIP提高组复赛试题DayDay.doc》由会员分享，可在线阅读，更多相关《NOIP提高组复赛试题DayDay.doc（31页珍藏版）》请在三一文库上搜索。

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表示朝向圈内，1表示朝 向圈外。保证不会出现其他的数。字符串长度不超过10且仅由小写字母构成，字符串不为空，并且字符串两两不同。整数和字符串之间 用一个空格隔开。接下来m行，其中第i行包含两个整数，表示第i条指令。若 =0，表示向左数 个人；若=1，表示向右数 个人。保证 不会出 现其他的数，1 n。【输出格式】输出到文件 中。输出一个字符串，表示从第一个读入的小人开 始，依次数完m条指令后

5、到达的小人的职业。【样例1输入】7 300011010 31 10 2【样例1输出】样例 1 说明】这组数据就是【题目描述】中提到的例子。【样例 2 输入】10 101 c0 r0 p1 d1 e1 m1 t1 y1 u0 v1 71 11 40 50 30 11 61 20 80 4【样例 2 输出】y【子任务】 子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。 每个测试点的数据规模与特点如下表：测试nm全朝内全左数=职业长度120103VVVV2X3VX4X5VVX6X7VX8X9VVVX10X11VX12X13VVX14X15VX16X1710

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

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

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

9、0手 W。【输出格式】输出到文件 中。输出 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 号点， W1 = 0 ，故只有起点为 1 号点的玩家才会被观察到， 所以玩家 1 和玩家 2 被观察到，共 2 人被观察到。对于 2 号点，没有玩家在第 2 秒时在此结点，共 0 人被观察到。对于 3 号点，没有玩家在第 5 秒时在此结点，共 0 人被观察到。对于 4 号点，玩家 1 被观察到，共 1 人被观察到。对于

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

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

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

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

14、的期望值最小，请你帮他求出这个最小值。【输入格式】从文件 中读入数据。第一行四个整数 n, m, v, e 。 n 表示这个学期内的时间段的数量； m 表示牛牛最多 可以申请更换多少节课程的教室； v 表示牛牛学校 里教室的数量； e 表示牛牛的学校 里道路的数量。第二行n个正整数，第i ( 1 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

15、个时间段更 换教室获得通过的概率。保证 0 w w 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位，表示答案。你的输出必须和标准输出完全二样才算正确。测试数据保证四舍五入后的答案和准确答案的差的绝

16、对值不大于4 X 10-3。(如果你不知道什么是浮点误差，这段话可以理解为：对 于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊 的处理)【样例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.

17、8104430 14无0 182、32、30 1420 105.23044无0.48【样例2】见选手目录下的2与2。【提示】1. 道路中可能会有多条双向道路连接相同的两间教室。也有可能有道 路两端连接的是同一间教室。2请注意区分n, m, v, e的意义，n不是教室的数量，m不是道路的 数量。【子任务】测试点nmv特殊性特殊性1 1 1wXX2 2w 0w 203 1w4w 2w5 3w 0w 20VV6w 1wX7w 2w300X8 10w 0VV9w 1w 20X10w 2wX11w 10wV12 20w 0w 20VX13w 1wX14w 2w300V15w 20XV16300w 0OU

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

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

20、(1, 3),(2,3)这三种选择方法。根据组合数的定义，我们可以给出计算组合数 兰的一般公式：其中 n! = 1 x 2 x x n 。小葱想知道如果给定n, m和k，对于所有的0 w i n, 0 jw (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输

21、入】1 23 3【样例1输出】【样例1说明】在所有可能的情况中，只有-=2是2的倍数【样例2输入】2 54 56 7【样例2输出】07【子任务】测试点nmkt1w 3w 3=2=12=3w3w 7w 7=4=14=5w5w 10w 10=6=16=7w7w 20w 100=8=18=9w9w 25w2000=10=110=11w11w 602000w 20=12=112= 13w13w 100w 25=14=114=15w15w 60=16=116=17w17w2000w 100=18=118=19w19wonnn=20=1120=21w蚯蚓（）【问题描述】本题中，我们将用符号 表示对c向下取

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

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

24、 q的意义见【问 题描述】；u, v, t均为正整数；你需要自己计算 p =（保证0 u v）； t是输出参数，其含义将会在【输出格式】中解释。第二行包含n个非负整数，为a2,.,，即初始时n只蚯蚓的长度。同一行中相邻的两个数之间，恰好用一个空格隔开。保证 1 n 10 5 , 0 m 7 x 10 6 , 0 u v 10 9 ,0 q 200 , 1 w t 71 ,0 w 10 8 o【输出格式】输出到文件一 1-1 、，、 、 第一行输出个整数，按时间顺序，依次输出第t秒，第2t秒，第3t秒，被切 断蚯蚓（在被切断前）的长度。第二行输出L一个整数，输出m秒后蚯蚓的长度：需要按从 大到小

25、的顺序，依次输出排名第 t ,第2t ,第3t , 的长度。同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有 任何数需要输出，你也应输出一个空行。请阅读样例来更好地理解这个格式。【样例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秒后：一只长度为为：2,3,(1,3),4。3秒后：一只长

26、度为3,424,(1,3)。4秒后：一只长度为4,(1,3),3,5,2,4。5秒后：一只长度为5,2,4,4,(1,4),3,5。6秒后：一只长度为(1,4),3,5,525,4,6。的蚯蚓被切成了的蚯蚓被切断。的蚯蚓被切断。的蚯蚓被切断。的蚯蚓被切断。1和3。5只蚯蚓的长度分别只蚯蚓的长度分别为:只蚯蚓的长度分别为:只蚯蚓的长度分别为:只蚯蚓的长度分别为: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,

27、5,5,4,4,3,2,2 。【样例 2 输入】3 7 1 1 3 23 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 。测试点47满足n, mW 1, 000 。测试点814满足q = 0

28、，其中测试点89还满足m W 10 5 测试点1518满足m 3 x 10 5。测试点 19 20 没有特殊的约定，参见原始的数据范围。测试点 1 12 ， 15 16 还满足 v W 2 ，这意味着 u, v 的唯 可能的取值是 u = 1, v = 2 ，即 p = 0.5 。这可能会对解决问题有 特殊的帮助。每个测试点的详细数据范围见下表。愤怒的 小鸟()【问题描述】 最近沉迷于一款神奇的游戏无法自拔。 简单来说，这款游戏是在一个平面上进行的。 有一架弹弓位于 (0, 0) 处，每次 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 y = 2 + 的曲线，其中 a, b

29、是 指 定的参数，且必须满足 a 0 。当小鸟落回地面(即 x 轴)时，它就会瞬间消失。 在游戏的某个关卡里，平面的第一象限中有 n 只绿色的小猪，其中第 i 只小猪所在的坐标为 (, ) 。如果某只小鸟的飞行轨迹经过了 (, ) ，那么第 i 只小猪就会被消灭掉， 同时小鸟将会沿着原先的轨迹继续飞行；如果一只小鸟的飞行轨迹没有经过 (, ) ，那么这只小鸟飞行的全过 程就不会对第 i 只小猪产生任何影响。例如，若两只小猪分别位于 (1, 3) 和(3, 3) ， 可以选择发射一只飞 行轨迹为 y =-x2 + 4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。 而这个游戏的目的，就是通过发射

30、小鸟消灭所有的小猪。 这款神奇游戏的每个关卡对 来说都很难，所以 还输入了一些神秘 的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】 中详述。假设这款游戏一共有 T 个关卡，现在 想知道，对于每一个关卡， 至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希 望由你告诉她。输入格式】从文件 中读入数据。第一行包含一个正整数 T ，表示游戏的关卡总数。下面依次输入这 T 个关卡的信息。每个关卡第一行包含两个非负整 数 n, m ，分别表示该关卡中的小猪数量和输入的神秘指令类型。接下来的 n 行中，第 i 行包含两个正实数 , ，表示第 i 只小猪坐标 为 (, ) 。数

31、据保证同一个关卡中不存在两只坐标完全相同的小猪。如果 m = 0 ，表示 输入了一个没有任何作用的指令。如果 m = 1 ，则这个关卡将会满足：至多用 3 + 1?只小鸟即可消 灭所有小猪。如果 m = 2 ，则这个关卡将会满足：一定存在一种最优解，其中 有一只小鸟消灭了至少 3J 只小猪。保证1 w nw 18, OW mw 2 , 0 , 10,输入中的实数均保留到小数点后两 位。上文中，符号 c? 和 分别表示对 c 向上取整和向下取整，例如： 2.1? = 2.9? = 3.0? =L3.0J = L3.1J = L3.9J = 3。输出格式】输出到文件 中。对每个关卡依次输出一行答案

32、。 输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪 最少需要的小鸟数量。【样例 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) 和(3.00,3.00) ，只需发射一只飞行轨迹为 y = -x2 + 4x 的小 鸟即可消灭它们。第二个关卡中有 5 只小猪，但经过观察我们可以发现它们的坐标都在抛物线 y = -x2 + 6x 上，故 只需

33、要发射一只小鸟即可消灭所有小猪。【样例 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输出】【子任务】数据的一些特殊规定如下表:测试点编号n1 223 345 467 58 69 710 811 912 1013 121415 15161718 181920mT=0w 10w 30w 10w 30w 10w 30w 10w 30=1=2=0w 15=1=9=0w 5=1=2