資源簡(jiǎn)介

第37屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽
CCF
NOI
2020
第一試
時(shí)間:2020年8月18日08:00~13:00
題目名稱
美食家
命運(yùn)
時(shí)代的眼淚
題目類型
傳統(tǒng)型
傳統(tǒng)型
傳統(tǒng)型
delicacy
desti
tears
可執(zhí)行文件名de1
cacy
destiny
tears
輸入文件名
delicacy
in
destiny.
in
tears.
in
輸出文件名
delicacy.
out
destiny.
out
tears
out
每個(gè)測(cè)試點(diǎn)時(shí)限20秒
20秒
40秒
內(nèi)存限制
512MB
512MB
1
GB
子任務(wù)數(shù)目
測(cè)試點(diǎn)是否等分是
是
是
提交源程序文件名
對(duì)于C++語(yǔ)言cel
icac.
cpp
estiny.
cpp
tears.
cpp
編譯選項(xiàng)
對(duì)于C++語(yǔ)言
1m-02-std=c++11
注意事項(xiàng)
選手提交的源文件必須存放在已建立好的帶有下發(fā)樣例的文件夾中(該文件夾與
試題同名)
2.文件名(包括程序名和輸入輸出文件名)必須使用英文小寫
3.C++中函數(shù)main()的返回值類型必須是int,值必須為0
4.對(duì)于因未遵守以上規(guī)則對(duì)成績(jī)?cè)斐傻挠绊?相關(guān)申訴不予受理
5.若無特殊說明,輸入文件中同一行內(nèi)的多個(gè)整數(shù)、浮點(diǎn)數(shù)、字符串等均使用一個(gè)
空格進(jìn)行分隔
6.若無特殊說明,結(jié)果比較方式為忽略行末空格、文末回車后的全文比較
7.程序可使用的棧空間大小與該題內(nèi)存空間限制一致
8.在終端下可使用命令u1imit-
s
unlimited將棧空間限制放大,但你使用的棧
空間大小不應(yīng)超過題目限制
第37屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽
第一試美食家(
delicacy)
美食家(
delicacy)
【題目描述】
坐落在
Zeroth大陸上的精靈王國(guó)擊退地災(zāi)軍團(tuán)的入侵后,經(jīng)過十余年的休養(yǎng)生息,
重新成為了一片欣欣向榮的樂土,吸引著八方游客。小W是一位游歷過世界各地的著
名美食家,現(xiàn)在也慕名來到了精靈王國(guó)
精靈王國(guó)共有n座城市,城市從1到η編號(hào),其中城市讠的美食能為小W提供c
的愉悅值。精靈王國(guó)的城市通過m條單向道路連接,道路從1到m編號(hào),其中道路
的起點(diǎn)為城市;,終點(diǎn)為城市v,沿它通行需要花費(fèi)ω;天。也就是說,若小W在第
d天從城市v沿道路i通行,那么他會(huì)在第d+v;天到達(dá)城市v
小W計(jì)劃在精靈王國(guó)進(jìn)行一場(chǎng)為期T天的旅行,更具體地:他會(huì)在第0天從城市
出發(fā),經(jīng)過T天的旅行,最終在恰好第T天回到城市1結(jié)束旅行。由于小W是一位
美食家,每當(dāng)他到達(dá)一座城市時(shí)(包括第0天和第T天的城市1),他都會(huì)品嘗該城市
的美食并獲得其所提供的愉悅值,若小W多次到達(dá)同一座城市,他將獲得多次愉悅值
注意旅行途中小W不能在任何城市停留,即當(dāng)他到達(dá)一座城市且還未結(jié)束旅行時(shí),他
當(dāng)天必須立即從該城市出發(fā)前往其他城市
圖
samp
對(duì)于上圖,小W一種為期11天的可行旅游方案為1→2→1→2→3→1
第0天,小W從城市1開始旅行,獲得愉悅值1并向城市2出發(fā)
第1天,小W到達(dá)城市2,獲得愉悅值3并向城市1出發(fā)
第4天,小W到達(dá)城市1,獲得愉悅值1并向城市2出發(fā)
第5天,小W到達(dá)城市2,獲得愉悅值3并向城市3出發(fā)
第7天,小W到達(dá)城市3,獲得愉悅值4并向城市1出發(fā)
第11天,小W到達(dá)城市1,獲得愉悅值1并結(jié)束旅行
小W在該旅行中獲得的愉悅值之和為13
此外,精靈王國(guó)會(huì)在不同的時(shí)間舉辦k次美食節(jié)。具體來說,第讠次美食節(jié)將于第
t;天在城市x;舉辦,若小W第t天時(shí)恰好在城市x;,那么他在品嘗城市x;的美食時(shí)
會(huì)額外得到v的愉悅值。現(xiàn)在小W想請(qǐng)作為精靈王國(guó)接待使者的你幫他算出,他在旅
行中能獲得的愉悅值之和的最大值
第2頁(yè)共12頁(yè)

展開更多......

收起↑