1、第37届全国青少年信息学奥林匹克竞赛试题第一试第37届全国青少年信息学奥林匹克竞赛CCF NOI 2020第一试时间:2020年8月18日08:0013:00题目名称美食家命运时代的眼泪题冃类生传统型传统型传统型delicacydestinytea rs可执行文件名delicacydestinytears输入文件名delicacy.indestiny intears in输出文件名delicacy.outdestiny.outtears.out每个测试点时限2.0杪2.0秒4.0秒内存限制512 MB512 MB1 GB子任务数冃2()2525測试点是否等分是是是提交源程序文件名对P C+语言
2、delicacy-cppdestiny.cpptearscpp编译选项对于C+语言-lm -02 -std=c+ll注意事项1.选手提交的源文件必须存放在己建立好的带有下发样例的文件夹中（该文件夹与 试题同名）。2.文件名（包括程序名和输入输出文件名）必须使用英文小写。3.C+中函数maiiiO的返回值类型必须是int,值必须为（）。4.対于因未遵守以上规则对成绩造成的影响，相关申诉不予受理。5.若无特殊说明，输入文件中同一行内的多个藥数、浮点数、字符串等均使用一个 空格进行分隔。6.若无特殊说明，结果比较方式为忽略行末空格、文末回车后的全文比较。7.程序可使用的栈空间大小与该题内存空间限制一
3、致。&在终端下可使用命令ulimits unlimited将栈空间限制放大，但你使用的栈 空间大小不应超过题目限制。美食家（delicacy）【题目描述】坐落在Bzcroth人陆上的精灵王国击退地灾军团的入侵后，经过十余年的休养生息, 垂新成为了一片欣欣向荣的乐土，吸引着八方游客。小W是一位游历过世界各地的著 名美食家，现在也慕名来到了精灵王国。精灵王国共有座城市，城市从1到编号，其中城市i的美食能为小W提供仃 的愉悦值。楮灵工国的城市通过”，条单冋道路连接，道路从1到川编号，其中道路/ 的起点为城市m ,终点为城市r沿它通行需耍花费I夭。也就是说，若小W在第 d天从城市他沿道路i通行，那么他
4、会在第d + 天到达城市。小W计划在結灵王国进行一场为期T天的旅行，更具体地：他会在第0天从城市 1出发，经过T天的旅行，最终在恰好第T天回到城市1结束旅行。由于小W是一位 美食家，每当他到达一座城市时（包括第0夭和第了人的城市1）,他都会品尝该城市 的美食并获得其所提供的愉悦值，若小代多次到达同-座城市，他将获得多次购悅值, 注意旅行途中小W不能在任何城市停留.即当他到达座城市且还未结束旅行时，他 半天必须立即从该城市出发前往具他城市。图 1: sain pie 1小W 一种为期11人的町行旅游方案为小W从城市I开始族行，获得愉悦值1并向城帀2出发。小W到达城市2,小W到达城市1,小W到达城
5、市2,小W到达城市3,第11天，小W到达城市1,获得愉悦值1并结束族行。小W在该旅行中获得的愉悦值之和为13。此外，精灵王国会在不同的时间举办k次矣食节。具体來说，第i次美食节将于第 匕天在城市举办，若小W第t,天时恰好在城市切 那么他在品尝城市昕的美食时 会额外得到S的愉悦值。现在小W想谙作为精灵王国接待使者的你帮他算岀，他在旅 行中能获得的愉悦值之和的最大值。 【输入格式】从文件delicacy, in中读入数据。第一行四个整数依次农穴城市数、道路条数、旅行天数与美食节次数。 第二行n个整数表示每座城市的美食所能提供的愉悦值。接下来“2行每行三个幣数ugg 依次表示每条道路的起点、终点与通
6、行天数。最后R行每行三个整数tgg 依次表示每次美食节的举办时间、举办城市与提 供的额外愉悦值。本题中数据保证：对所I z m,有血式“。但数据小可能存在路线重复的单向道路，即可能 存在1 S 2 V j S m，使得血=呵,5 = w；c对每座城市都满足：至少存在一条以该城市为起点的单向道路。每次美食节的举办时间耳互不相同。【输出格式】输出到文件delicacy, out中。仅一行一个整数，表示小w通过旅行能兼得的愉悦值Z和的最大值。若小W无法在第T天回到城市1,则输出-lo 【样例1输入】3411 0134121213232314【样例1输出】13【样例1解释】该样例为题目描述中的例子，最
7、优旅行方案见题目描述。【样例2输入】14816 32312 43121413151326343723283219421104151133512125135420【样例2输出】39【样例2解释】最优方案为1t3t4t2t3t4t1。第0天，第2天，第5天，第6天，第8天，小W从城市1开始旅行，获得愉悦值3并沿道路3通行。小W到达城市3,获得愉悦值2并沿道路4通行。小W到达城市-1,由于美食卩茯得愉悦值20 + 4并沿道路7通行。小W到达城市2,获得愉悦值1并沿道路5通行。小W到达城市3,获得愉悦值2并沿道路4通行。第11天，小W到达城市4,获得愉悦值4并沿道路8通行。第16天，小W到达城市1,获
8、得愉悦值3并结束旅行。小w获得的愉悦值之和为39。【样例3】见选手目录下的 delicacy/delicacy 3.iji 与 debicac对/delicacy 3 cms。笫】页 共12页【测试点约束】对J：所有測试点1 n 50, n m 501, 0k 200,每个测试点的具体限制见卜衣:测试点编号nmT特殊限制L 4 55无58 525019 10 5()A11 13 50k = 011 15109k1016 17无1820 501特殊限制 A： n = m 且 Ui = ?,t；i = (i mod n) + 1。命运(destiny)【题目描述】提不：我们右題冃描述的最瓶段捉供了
9、 份简耍的、形式化描述的题面。在遥远的未來，物理学家终于发现了时间和因果的自然规律。即使住一个人出牛前 我们也可以通过理论分析知晓他或她人生的一些信息，换古之，物理学允许我们从一定 程度上“预言” 一个人的命运”。简单来说，个人的命运是棵由时间点构成的有根树丁：树的根结点代衣荀I住. 而叶结点代表着死亡。每个非叶结点都有一个或多个孩子5.也,，.,表示这个人 在“所代表的时间点做出的个不同的选择可以导向的不同的可能性。形式化的，一 个选择就是树上的一条边(u,3),其中“是S的父结点。一个人的一牛是从出牛(即根结点)到死亡(即某一个叶子结点)的一条不经过重 复结点的路径，这条路径上任何一个包含
10、至少一条边的子路径都是这个人的一段人生紐 历，而他或她以所冇可能的方式度过一生，从而拥有的所有人生经历，都被称为潜在的 人生经历。换言乙所有潜右:的人生经历就是所有“到r的路径，满足u.c 7 u # , 并FI.是的帳先。在数学匕这样一个潜任的人牛经历被记作有序对(u. V),树T所 育潜在的人生经历的集合记作Pro物理理论不仅允许我们观测代衣命运的树，迩能让我们分析-些潜在的人生经J是 否是“重要”的。一个人所作出的每一个选择即树匕的每一条边一都可能是重要 或不重要的。一段潜在的人学经历被称为朿要的，勺几仅为其对应的路径匕存住一条边 是重要的。我们可以观测到一些潜在的人生经历是垂要的：换言
11、之，我们可以观测得到 一个集介Q c Pe满足其中的所有潜在的人生经(n, V)e Q都是重要的。树厂的形态早已被计算确定，集合Q也早已被观测得到，一个人命运的不确定件 己经人人降低了。但不确定性仍然是口人的一來计算一下吧，对于给定的树T和集合 Q,存在多少种不同的方案确定每条边是否是重要的，使Z满足所观測到的Q所对应的 限制：即对任惫WQ.都存在条到“路径上的边被确定为重耍的。形或化的：给定一棵树T = (V. E)和点对集合Q C VxV,满足对于所有(u, v) Q， 都有u丰L-,并 u是r在树了上的祖先。其中2和E分别代表树T的结点荣和边 集。求有多少个不同的函数J ： E f 0.
12、1(将每条边e E的/(e)值置为0或1),满 足対于任何(u,v) E Q,都存在“到r路径匕的一条边e使得/(e) = I。由于答案可能 非常人，你只需要输出结果对998.244,353 (个索数)取模的结果。【输入格式】从文件destiny, in中读入数据。第一行包含一个正整数“，表示树T的大小，树匕结点从1到“编号，I号结点 为根结点；接下来n-1行每行包含空格隔开的两个数缺3 满足1 xhy. m表示树 匕的结点艾和切之间存在一条边，但并不保证这条边的方向；接下来一行包含一个非负整数m,表示所观测得到信息的条数。接下来m行每行包含空格隔开的两个数儿也，表示(如,s)Q。请注戳输入
13、数据可能包含垂复的信息，换言之可能存在中,满足均=勺口 =匕。输入数据规模和限制参见本题末尾的表格。【输岀格式】输岀到文件destiny.out中。输出仅一行一个整数，表示方案数对90&214.353 模的结果。【样例1输入】【样例1输出】10【样例1解释】共有16种方案，其中不满足题童的方案有以下6种：(1,2), (2,3), (3,5)确定为不重耍,(3,4)确定为重耍：集合Q中没有限制被满足。(1,2),(2,3),(3,4),(3,5)确定为不重要:集合Q中没有限制被满足。(1,2),(2,3)确定为不重要,(3,4),(3,5)确定为重要:集合Q中(1,3)没被满足。 (1,2),
14、(2,3),(3,4)确定为不重要,(3,5)确定为重要:集合Q中(1,3)没被满足。 (2.3),(3,5)确定为不垂要,(1,2),(3,4)确定为垂要:集合Q中(2,5)没被满足。 (2,3),(3,4),(3,5)确定为不重要,(1,2)确定为重要：集合Q中5)没被满足。 其他方案下，集合Q中的限制都被满足了笫7页 共12页123456789101112131415161718192021221【样例2输入】152131435263768495107115121013314915863 125 11253138 151 13【样例2输岀】960【样例3】见选手目录下的 destiny/
15、destiny 3. in 与 destiny/des tiny 3. a【样例4】见选手冃录卜的 destiny.in 与 tiestiny/destiny.anso时代的眼泪（tears）【题目描述】小L莒欢与智者交流讨论，而智者也经常为小L出些思考题。这天智者又为小L构思了一个问题。智者首先将时空抽象为了一个二维平面，进而 将一个事件抽象为该平面上的一个点，将一个时代抽象为该平面上的一个矩形。为了方便,下面记（a,b） （c,d）表示平面匕两个点（db），（c,）满足a c,b de更具体地，智苦给定了九个事件，他们用平面上n个不同的点（%）=来表示; 智者还给定了 m个时代，每个时代用
16、平而匕一个短形（G，ri,2tG.2）来表示，其中 （和心1）是矩形的左下角，（几.2,如）是矩形的右上角，保证（F，切）冬（口2心2）。我们 称时代/包含了事件j当且仅当（如,） D （也,知）。智者认为若两个事件i,J满足（击，炉） （町,的），则这两个事件形成了一次遗憾。而 对-个时代内包含的所何事件，它们所形成的遗憾被称为这个时代旳眼泪.而形成的遗 憾次数则称为该时代的眼泪的大小。现在智者想耍小L计算每个时代的眼祠旳丈小。小L明口，如果他回答不了这个问题.他也将成为时代的眼泪，请你帮帮他。【输入格式】从文件tear3.in中读入数据。第一行两个整数a, m,分别表示事件数与时代数。第二
17、行n个整数”，其屮第个数表示事件7：在平面上的坐标为仏河）。保证为 一个1到n,的排列。之后m行，每行四个整数口1,八.2冲.1冲,2，表示毎个时代对应的矩形。【输岀格式】输出到文件tcars.out中o输出m行，每行包含一个整数，第2行输出第？个时代的眼泪的大小。【样例1输入】891011123456789【样例1输岀】142444000【样例1解释】对于时代1,包含的遗憾有(6,7)(即事件6与事件7形成的遗憾，下同)。 对于时代2,包含的遗憾有(5,6),(6,7),(5,7), (5,8)。对于时代3,包含的遗憾有(5,6),(5.8)。对于时代4,包含的遗憾有(5,6),(6,7),
18、 (5,7), (5,8)。对于时代5,包含的遗憾有(5,6),(07),(5,7),(5,8)。对于时代6,包含的遗憾有(5,6), (6,7), (5,7), (5,8)-对于时代7,&9,它们均不包含任何遗憾。【样例21见选手目录下的 tears /tears 2. in 与 t cars/tears 2. ans该样例满足待殊限制4 (貝体限制见測试点约束)。【样例3】见选手目录卜的 tears/tears 3. in 与 t ears /tears 3.anso该样例满足特殊限制B (具体限制见測试点约束人【测试点约束】对于所有测试点:1 n 10s, 1 171 2 X 105,
19、1 / cfj, C1；2 S He毎个测试点的具体限制见下表：测试点编号n m 特殊限制131010无13,0003,00054,0004,00065,0005,000725.00050,000A850.000100.000975.000150.00010100,000200,0001100.00()120,000B1280.000160.00013100,000200,0001420.00040,000无1530.00060,0001640.00080,0001750,000100,0001860.00()120,0001970: 1X)()140,00()2() 22100,000200,00()C23 25无特殊限制A：对于所有时代i有3 = g = no特殊限制B：任意两个不同时代所代表的矩形，它们要么是包含关系(一个矩形在 另一个矩形内，边界允许重合)，要么是相离关系(两矩形不包含共同点，边界不允许重 合)。特殊限制C：最多有50对事件(ij) (lijn)不洒足仏亦
