第37届全国青少年信息学奥林匹克竞赛试题第一试.docx
- 文档编号:16270920
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:15
- 大小:50.18KB
第37届全国青少年信息学奥林匹克竞赛试题第一试.docx
《第37届全国青少年信息学奥林匹克竞赛试题第一试.docx》由会员分享,可在线阅读,更多相关《第37届全国青少年信息学奥林匹克竞赛试题第一试.docx(15页珍藏版)》请在冰点文库上搜索。
第37届全国青少年信息学奥林匹克竞赛试题第一试
第37届全国青少年信息学奥林匹克竞赛
CCFNOI2020
第一试
时间:
2020年8月18日08:
00〜13:
00
题目名称
美食家
命运
时代的眼泪
题冃类生
传统型
传统型
传统型
delicacy
destiny
tears
可执行文件名
delicacy
destiny
tears
输入文件名
delicacy.in
destiny・in
tears・in
输出文件名
delicacy.out
destiny.out
tears.out
每个测试点时限
2.0杪
2.0秒
4.0秒
内存限制
512MB
512MB
1GB
子任务数冃
2()
25
25
測试点是否等分
是
是
是
提交源程序文件名
对PC++语言
delicacy-cpp
destiny.cpp
tears・cpp
编译选项
对于C++语言
-lm-02-std=c++ll
注意事项
1.选手提交的源文件必须存放在己建立好的带有下发样例的文件夹中(该文件夹与试题同名)。
2.文件名(包括程序名和输入输出文件名)必须使用英文小写。
3.C++中函数maiiiO的返回值类型必须是int,值必须为()。
4.対于因未遵守以上规则对成绩造成的影响,相关申诉不予受理。
5.若无特殊说明,输入文件中同一行内的多个藥数、浮点数、字符串等均使用一个空格进行分隔。
6.若无特殊说明,结果比较方式为忽略行末空格、文末回车后的全文比较。
7.程序可使用的栈空间大小与该题内存空间限制一致。
&在终端下可使用命令ulimit・sunlimited将栈空间限制放大,但你使用的栈空间大小不应超过题目限制。
美食家(delicacy)
【题目描述】
坐落在Bzcroth人陆上的精灵王国击退地灾军团的入侵后,经过十余年的休养生息,垂新成为了一片欣欣向荣的乐土,吸引着八方游客。
小W是一位游历过世界各地的著名美食家,现在也慕名来到了精灵王国。
精灵王国共有"座城市,城市从1到〃编号,其中城市i的美食能为小W提供仃的愉悦值。
楮灵工国的城市通过”,条单冋道路连接,道路从1到川编号,其中道路/的起点为城市m,终点为城市r„沿它通行需耍花费I夭。
也就是说,若小W在第d天从城市他沿道路i通行,那么他会在第d+©天到达城市"。
小W计划在結灵王国进行一场为期T天的旅行,更具体地:
他会在第0天从城市1出发,经过T天的旅行,最终在恰好第T天回到城市1结束旅行。
由于小W是一位美食家,每当他到达一座城市时(包括第0夭和第了人的城市1),他都会品尝该城市的美食并获得其所提供的愉悦值,若小代多次到达同-座城市,他将获得多次购悅值,注意旅行途中小W不能在任何城市停留.即当他到达•座城市且还未结束旅行时,他半天必须立即从该城市出发前往具他城市。
图1:
sainpie1
小W一种为期11人的町行旅游方案为
小W从城市I开始族行,获得愉悦值1并向城帀2出发。
小W到达城市2,
小W到达城市1,
小W到达城市2,
小W到达城市3,
•第11天,小W到达城市1,获得愉悦值1并结束族行。
•小W在该旅行中获得的愉悦值之和为13。
此外,精灵王国会在不同的时间举办k次矣食节。
具体來说,第i次美食节将于第
••
匕天在城市举办,若小W第t,天时恰好在城市切那么他在品尝城市昕的美食时会额外得到S的愉悦值。
现在小W想谙作为精灵王国接待使者的你帮他算岀,他在旅行中能获得的愉悦值之和的最大值。
•••
【输入格式】
从文件delicacy,in中读入数据。
第一行四个整数依次农穴城市数、道路条数、旅行天数与美食节次数。
第二行n个整数表示每座城市的美食所能提供的愉悦值。
接下来“2行每行三个幣数ugg依次表示每条道路的起点、终点与通行天数。
最后R行每行三个整数tgg依次表示每次美食节的举办时间、举办城市与提供的额外愉悦值。
本题中数据保证:
・对所I 但数据小可能存在路线重复的单向道路,即可能存在1S2VjSm,使得血=呵,5=w;c ・对每座城市都满足: 至少存在一条以该城市为起点的单向道路。 ・每次美食节的举办时间耳互不相同。 【输出格式】 输出到文件delicacy,out中。 仅一行一个整数,表示小w通过旅行能兼得的愉悦值Z和的最大值。 若小W无法在第T天回到城市1,则输出-lo •••••••••••••• 【样例1输入】 3 4 110 1 3 4 1 2 1 2 1 3 2 3 2 3 1 4 【样例1输出】 13 【样例1解释】 该样例为题目描述中的例子,最优旅行方案见题目描述。 【样例2输入】 1 4 8 163 2 3 1 24 3 1 2 1 4 1 3 1 5 1 3 2 6 3 4 3 7 2 3 2 8 3 2 1 9 4 2 1 10 4 1 5 11 3 3 5 12 1 2 5 13 5 4 20 【样例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,获得愉悦值3并结束旅行。 小w获得的愉悦值之和为39。 【样例3】 见选手目录下的delicacy/delicacy3.iji与debicac对/delicacy3・cms。 笫】页共12页 【测试点约束】 对J: 所有測试点^ 1 每个测试点的具体限制见卜衣: 测试点编号 n m T 特殊限制 L~4 <5 <5 无 5〜8 <52501 9~10 <5() A 11~13 <50 k=0 11〜15 <109 k<10 16~17 无 18~20 <501 特殊限制A: n=m且Ui=? t;i=(imodn)+1。 命运(destiny) 【题目描述】 提不: 我们右「題冃描述的最瓶」段捉供了•份简耍的、形式化描述的题面。 在遥远的未來,物理学家终于发现了时间和因果的自然规律。 即使住一个人出牛前・我们也可以通过理论分析知晓他或她人生的一些信息,换古之,物理学允许我们从一定程度上“预言”一个人的'‘命运”。 简单来说,•个人的命运是•棵由时间点构成的有根树丁: 树的根结点代衣荀I住.而叶结点代表着死亡。 每个非叶结点"都有一个或多个孩子5.也,•••,%.,表示这个人在“所代表的时间点做出的°个不同的选择可以导向的不同的可能性。 形式化的,一个选择就是树上的一条边(u,3),其中“是S的父结点。 一个人的一牛•是从出牛(即根结点)到死亡(即某一个叶子结点)的一条不经过重复结点的路径,这条路径上任何一个包含至少一条边的子路径都是这个人的一段人生紐历,而他或她以所冇可能的方式度过一生,从而拥有的所有人生经历,都被称为潜在的 ••••人生经历。 换言乙所有潜右: 的人生经历就是所有“到r的路径,满足u.c€7\u#",并FI."是"的帳先。 在数学匕这样一个潜任的人牛•经历被记作有序对(u.V),树T所育潜在的人生经历的集合记作Pro 物理理论不仅允许我们观测代衣命运的树,迩能让我们分析-些潜在的人生经〃J是否是“重要”的。 一个人所作出的每一个选择——即树匕的每一条边一都可能是重要或不重要的。 一段潜在的人学•经历被称为朿要的,勺几仅为其对应的路径匕存住一条边 ••• 是重要的。 我们可以观测到一些潜在的人生经历是垂要的: 换言之,我们可以观测得到一个集介QcPe满足其中的所有潜在的人生经(n,V)eQ都是重要的。 树厂的形态早已被计算确定,集合Q也早已被观测得到,一个人命运的不确定件己经人人降低了。 但不确定性仍然是口人的一來计算一下吧,对于给定的树T和集合Q,存在多少种不同的方案确定每条边是否是重要的,使Z满足所观測到的Q所对应的限制: 即对「•任惫WQ.都存在•条"到“路径上的边被确定为重耍的。 形或化的: 给定一棵树T=(V.E)和点对集合QCVxV,满足对于所有(u,v)€Q,都有u丰L-,并□u是r在树了上的祖先。 其中2和E分别代表树T的结点荣和边集。 求有多少个不同的函数J: Ef{0.1}(将每条边e€E的/(e)值置为0或1),满足対于任何(u,v)EQ,都存在“到r路径匕的一条边e使得/(e)=I。 由于答案可能非常人,你只需要输出结果对998.244,353(—个索数)取模的结果。 【输入格式】 从文件destiny,in中读入数据。 ・第一行包含一个正整数“,表示树T的大小,树匕结点从1到“编号,I号结点为根结点; •接下来n-1行每行包含空格隔开的两个数缺3满足1 ・接下来一行包含一个非负整数m,表示所观测得到信息的条数。 ・接下来m行每行包含空格隔开的两个数儿也,表示(如,s)€Q。 请注戳输入数据可能包含垂复的信息,换言之可能存在中,满足均=勺口%=匕。 输入数据规模和限制参见本题末尾的表格。 【输岀格式】 输岀到文件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),(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页 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1 【样例2输入】 15 21 31 43 52 63 76 84 95 107 115 1210 133 149 158 6 312 511 25 313 815 113 【样例2输岀】 960 【样例3】 见选手目录下的destiny/destiny3.in与destiny/destiny3.a 【样例4】 见选手冃录卜的destiny.in与tiestiny/destiny^.anso 时代的眼泪(tears) 【题目描述】 小L莒欢与智者交流讨论,而智者也经常为小L出些思考题。 这天智者又为小L构思了一个问题。 智者首先将时空抽象为了一个二维平面,进而将一个事件抽象为该平面上的一个点,将一个时代抽象为该平面上的一个矩形。 为了方便,下面记(a,b)<(c,d)表示平面匕两个点(db),(c,〃)满足a 更具体地,智苦给定了九个事件,他们用平面上n个不同的点{(%◎)}=来表示;智者还给定了m个时代,每个时代用平而匕一个短形(G,ri,2t」G.2)来表示,其中(和心1)是矩形的左下角,(几.2,如)是矩形的右上角,保证(F,切)冬(口2心2)。 我们称时代/包含了事件j当且仅当(如,%) 智者认为若两个事件i,J满足(击,炉)<(町,的),则这两个事件形成了一次遗憾。 而对-个时代内包含的所何事件,它们所形成的遗憾被称为这个时代旳眼泪.而形成的遗憾次数则称为该时代的眼泪的大小。 现在智者想耍小L计算每个时代的眼祠旳丈小。 小L明口,如果他回答不了这个问题.他也将成为时代的眼泪,请你帮帮他。 【输入格式】 从文件tear3.in中读入数据。 第一行两个整数a,m,分别表示事件数与时代数。 第二行n个整数”,其屮第£个数表示事件7: 在平面上的坐标为仏河)。 保证〃为一个1到n,的排列。 之后m行,每行四个整数口1,八.2冲.1冲,2,表示毎个时代对应的矩形。 【输岀格式】 输出到文件tcars.out中o 输出m行,每行包含一个整数,第2行输出第? 个时代的眼泪的大小。 【样例1输入】 8 9 10 11 1 2 3 4 5 6 7 8 9 【样例1输岀】 1 4 2 4 4 4 0 0 0 【样例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),(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/tears2.in与tcars/tears2.ans^ 该样例满足待殊限制4(貝体限制见測试点约束)。 【样例3】 见选手目录卜的tears/tears3.in与tears/tears3.anso 该样例满足特殊限制B(具体限制见測试点约束人 【测试点约束】 对于所有测试点: 1 毎个测试点的具体限制见下表: 测试点编号 n< m< 特殊限制 1〜3 10 10 无 1 3,000 3,000 5 4,000 4,000 6 5,000 5,000 7 25.000 50,000 A 8 50.000 100.000 9 75.000 150.000 10 100,000 200,000 11 00.00() 120,000 B 12 80.000 160.000 13 100,000 200,000 14 20.000 40,000 无 15 30.000 60,000 16 40.000 80,000 17 50,000 100,000 18 60.00() 120,000 19 70: 1X)() 140,00() 2()~22 100,000 200,00() C 23〜25 无 特殊限制A: 对于所有时代i有3=g=no 特殊限制B: 任意两个不同时代所代表的矩形,它们要么是包含关系(一个矩形在另一个矩形内,边界允许重合),要么是相离关系(两矩形不包含共同点,边界不允许重合)。 特殊限制C: 最多有50对事件(ij)(l
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 37 全国青少年 信息学 奥林匹克 竞赛 试题 第一