CCF第37届全国青少年信息学奥林匹克竞赛（CCF NOI 2020）（第一试）试题（图片版，无答案）

第37届全国青少年信息学奥林匹克竞赛
CCF
NOI
2020
第一试
时间:2020年8月18日08:00~13:00
题目名称
美食家
命运
时代的眼泪
题目类型
传统型
传统型
传统型
delicacy
desti
tears
可执行文件名de1
cacy
destiny
tears
输入文件名
delicacy
in
destiny.
in
tears.
in
输出文件名
delicacy.
out
destiny.
out
tears
out
每个测试点时限20秒
20秒
40秒
内存限制
512MB
512MB
1
GB
子任务数目
测试点是否等分是
是
是
提交源程序文件名
对于C++语言cel
icac.
cpp
estiny.
cpp
tears.
cpp
编译选项
对于C++语言
1m-02-std=c++11
注意事项
选手提交的源文件必须存放在已建立好的带有下发样例的文件夹中(该文件夹与
试题同名)
2.文件名(包括程序名和输入输出文件名)必须使用英文小写
3.C++中函数main()的返回值类型必须是int,值必须为0
4.对于因未遵守以上规则对成绩造成的影响,相关申诉不予受理
5.若无特殊说明,输入文件中同一行内的多个整数、浮点数、字符串等均使用一个
空格进行分隔
6.若无特殊说明,结果比较方式为忽略行末空格、文末回车后的全文比较
7.程序可使用的栈空间大小与该题内存空间限制一致
8.在终端下可使用命令u1imit-
s
unlimited将栈空间限制放大,但你使用的栈
空间大小不应超过题目限制
第37届全国青少年信息学奧林匹克竞赛
第一试美食家(
delicacy)
美食家(
delicacy)
【题目描述】
坐落在
Zeroth大陆上的精灵王国击退地灾军团的入侵后,经过十余年的休养生息,
重新成为了一片欣欣向荣的乐土,吸引着八方游客。小W是一位游历过世界各地的著
名美食家,现在也慕名来到了精灵王国
精灵王国共有n座城市,城市从1到η编号,其中城市讠的美食能为小W提供c
的愉悦值。精灵王国的城市通过m条单向道路连接,道路从1到m编号,其中道路
的起点为城市;,终点为城市v,沿它通行需要花费ω;天。也就是说,若小W在第
d天从城市v沿道路i通行,那么他会在第d+v;天到达城市v
小W计划在精灵王国进行一场为期T天的旅行,更具体地:他会在第0天从城市
出发,经过T天的旅行,最终在恰好第T天回到城市1结束旅行。由于小W是一位
美食家,每当他到达一座城市时(包括第0天和第T天的城市1),他都会品尝该城市
的美食并获得其所提供的愉悦值,若小W多次到达同一座城市,他将获得多次愉悦值
注意旅行途中小W不能在任何城市停留,即当他到达一座城市且还未结束旅行时,他
当天必须立即从该城市出发前往其他城市
图
samp
对于上图,小W一种为期11天的可行旅游方案为1→2→1→2→3→1
第0天,小W从城市1开始旅行,获得愉悦值1并向城市2出发
第1天,小W到达城市2,获得愉悦值3并向城市1出发
第4天,小W到达城市1,获得愉悦值1并向城市2出发
第5天,小W到达城市2,获得愉悦值3并向城市3出发
第7天,小W到达城市3,获得愉悦值4并向城市1出发
第11天,小W到达城市1,获得愉悦值1并结束旅行
小W在该旅行中获得的愉悦值之和为13
此外,精灵王国会在不同的时间举办k次美食节。具体来说,第讠次美食节将于第
t;天在城市x;举办,若小W第t天时恰好在城市x;,那么他在品尝城市x;的美食时
会额外得到v的愉悦值。现在小W想请作为精灵王国接待使者的你帮他算出,他在旅
行中能获得的愉悦值之和的最大值
第2页共12页