2020年第37屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽試題第一試

1、第 1 貝 共 12 貞第37屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽CCF NOI 2020第一試時(shí)間:2020年8月18日08:0013:00題目名稱美食家命運(yùn)時(shí)代的眼淚題冃類生傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型目錄delicacydestinytea rs可執(zhí)行文件名delicacydestinytears輸入文件名delicacy.indestiny intears in輸出文件名delicacy.outdestiny.outtears.out每個(gè)測(cè)試點(diǎn)時(shí)限2.0杪2.0秒4.0秒內(nèi)存限制512 MB512 MB1 GB子任務(wù)數(shù)冃2()2525測(cè)試點(diǎn)是否等分是是是提交源程序文件名對(duì)P C+語(yǔ)言delicacy-

2、cppdestiny.cpptears cpp編譯選項(xiàng)對(duì)于C+語(yǔ)言-lm -02 -std=c+ll注意事項(xiàng)1.選手提交的源文件必須存放在己建立好的帶有下發(fā)樣例的文件夾中（該文件夾與 試題同名）。2.文件名（包括程序名和輸入輸出文件名）必須使用英文小寫。3.C+中函數(shù)maiiiO的返回值類型必須是int,值必須為（）。4.対于因未遵守以上規(guī)則對(duì)成績(jī)?cè)斐傻挠绊?，相關(guān)申訴不予受理。5.若無(wú)特殊說明，輸入文件中同一行內(nèi)的多個(gè)藥數(shù)、浮點(diǎn)數(shù)、字符串等均使用一個(gè) 空格進(jìn)行分隔。6.若無(wú)特殊說明，結(jié)果比較方式為忽略行末空格、文末回車后的全文比較。7.程序可使用的?？臻g大小與該題內(nèi)存空間限制一致。&在

3、終端下可使用命令ulimit s unlimited將?？臻g限制放大，但你使用的棧 空間大小不應(yīng)超過題目限制。笫 37 屆全國(guó)青少年佶息學(xué)奧林匹克競(jìng)賽第試美食家 Gldicacy）第 2 頁(yè) 共 12 頁(yè):美食家（delicacy）【題目描述】坐落在Bzcroth人陸上的精靈王國(guó)擊退地災(zāi)軍團(tuán)的入侵后，經(jīng)過十余年的休養(yǎng)生息, 垂新成為了一片欣欣向榮的樂土，吸引著八方游客。小W是一位游歷過世界各地的著 名美食家，現(xiàn)在也慕名來(lái)到了精靈王國(guó)。精靈王國(guó)共有座城市，城市從1到編號(hào)，其中城市i的美食能為小W提供仃 的愉悅值。楮靈工國(guó)的城市通過”，條單冋道路連接，道路從1到川編號(hào)，其中道路/ 的起點(diǎn)為城市m

4、,終點(diǎn)為城市r沿它通行需?；ㄙM(fèi) I 夭。 也就是說， 若小W在第d天從城市他沿道路i通行，那么他會(huì)在第d +天到達(dá)城市。小W計(jì)劃在結(jié)靈王國(guó)進(jìn)行一場(chǎng)為期T天的旅行， 更具體地： 他會(huì)在第0天從城市1出發(fā)，經(jīng)過T天的旅行，最終在恰好第T天回到城市1結(jié)束旅行。由于小W是一位 美食家，每當(dāng)他到達(dá)一座城市時(shí)（包括第0夭和第了人的城市1）,他都會(huì)品嘗該城市 的美食并獲得其所提供的愉悅值，若小代多次到達(dá)同-座城市，他將獲得多次購(gòu)悅值, 注意旅行途中小W不能在任何城市停留.即當(dāng)他到達(dá)座城市且還未結(jié)束旅行時(shí)，他 半天必須立即從該城市出發(fā)前往具他城市。小W一種為期11人的町行旅游方案為小W從城市I開始族行，獲得愉

5、悅值1并向城帀2出發(fā)。小W到達(dá)城市2,小W到達(dá)城市1,小W到達(dá)城市2,小W到達(dá)城市3,第11天，小W到達(dá)城市1,獲得愉悅值1并結(jié)束族行。對(duì)J：上圖，第（）天，第1天，第4天，第5天，獲得愉悅值3并向城市1出發(fā)。 獲得愉悅值1并向城市2岀發(fā)。 獲得愉悅值3并向城市3岀發(fā)。 獲得愉悅值4并向城市1出發(fā)。圖1: sain pie 1第 37 屆全國(guó)青少年信息學(xué)奧林匹克克賽第一試美食家（ddicacy）第 3 頁(yè) 共 12 頁(yè)小W在該旅行中獲得的愉悅值之和為13。此外，精靈王國(guó)會(huì)在不同的時(shí)間舉辦k次矣食節(jié)。具體來(lái)說，第i次美食節(jié)將于第 匕天在城市舉辦，若小W第t,天時(shí)恰好在城市切 那么他在品嘗城市昕的

6、美食時(shí) 會(huì)額外得到 S的愉悅值?，F(xiàn)在小W想諳作為精靈王國(guó)接待使者的你幫他算岀，他在旅 行中能獲得的愉悅值之和的最大值。 【輸入格式】從文件delicacy, in中讀入數(shù)據(jù)。第一行四個(gè)整數(shù)依次農(nóng)穴城市數(shù)、道路條數(shù)、旅行天數(shù)與美食節(jié)次數(shù)。 第二行n個(gè)整數(shù)表示每座城市的美食所能提供的愉悅值。接下來(lái)“2行每行三個(gè)幣數(shù) ugg 依次表示每條道路的起點(diǎn)、終點(diǎn)與通行天數(shù)。最后R行每行三個(gè)整數(shù) tgg 依次表示每次美食節(jié)的舉辦時(shí)間、舉辦城市與提 供的額外愉悅值。本題中數(shù)據(jù)保證：對(duì)所I z m,有血式“。但數(shù)據(jù)小可能存在路線重復(fù)的單向道路，即可能 存在1 S 2 V j Sm，使得血=呵,5 = w；c對(duì)每座

7、城市都滿足：至少存在一條以該城市為起點(diǎn)的單向道路。每次美食節(jié)的舉辦時(shí)間耳互不相同?！据敵龈袷健枯敵龅轿募elicacy, out中。僅一行一個(gè)整數(shù)，表示小w通過旅行能兼得的愉悅值Z和的最大值。若小W無(wú)法在第T天回到城市1,則輸出-lo 【樣例 1 輸入】34 11 013 412 1213232314第 37 屆全國(guó)青少年信息學(xué)奧林匹克克賽第一試美食家（ddicacy）第 3 頁(yè) 共 12 頁(yè)【樣例 1 輸出】13【樣例 1 解釋】該樣例為題目描述中的例子，最優(yōu)旅行方案見題目描述。第 37 屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽笫試美食家(kliraty )【樣例 2 輸入】148 16 32312

8、 4312 141315132634 37232832 1942 1104151133 5121251354 20【樣例 2 輸出】39【樣例 2 解釋】最優(yōu)方案為1T3T4T2T3T4T1。第0天，第2天，第5天，第6天，小W從城市1開始旅行，獲得愉悅值3并沿道路3通行。小W到達(dá)城市3,獲得愉悅值2并沿道路4通行。小W到達(dá)城市-1,由于美食卩茯得愉悅值20 + 4并沿道路7通行。小W到達(dá)城市2,獲得愉悅值1并沿道路5通行。第11天，小W到達(dá)城市4,獲得愉悅值4并沿道路8通行。第16天，小W到達(dá)城市1,獲得愉悅值3并結(jié)束旅行。小w獲得的愉悅值之和為39?！緲永?3】第 37 屆全國(guó)青少年信息學(xué)

9、奧林匹克克賽第一試美食家(delicacy)第 5 頁(yè) 人 12 頁(yè)見選手目錄下的delicacy/delicacy 3.iji與debicac 對(duì)/delicacy 3 cms。笫】頁(yè) 共 12 頁(yè)【測(cè)試點(diǎn)約束】對(duì)J：所有測(cè)試點(diǎn)1 n 50, n m 501, 0k200,每個(gè)測(cè)試點(diǎn)的具體限制見卜衣:測(cè)試點(diǎn)編號(hào)nmT特殊限制L 4 55無(wú)58 525019 10 5()A11 13 50k = 01115109k1016 17無(wú)1820 501特殊限制A：n =m且Ui =?,t；i =(imodn)+ 1。第 37 屆仝國(guó)用少年信總學(xué)奧林匹克競(jìng)賽第一試命運(yùn)(destiny)第 6 頁(yè)12

10、91命運(yùn)(destiny)【題目描述】提不：我們右題冃描述的最瓶段捉供了 份簡(jiǎn)耍的、形式化描述的題面。在遙遠(yuǎn)的未來(lái)，物理學(xué)家終于發(fā)現(xiàn)了時(shí)間和因果的自然規(guī)律。即使住一個(gè)人出牛前我們也可以通過理論分析知曉他或她人生的一些信息，換古之，物理學(xué)允許我們從一定 程度上“預(yù)言” 一個(gè)人的命運(yùn)”。簡(jiǎn)單來(lái)說，個(gè)人的命運(yùn)是棵由時(shí)間點(diǎn)構(gòu)成的有根樹?。簶涞母Y(jié)點(diǎn)代衣荀I住. 而葉結(jié)點(diǎn)代表著死亡。每個(gè)非葉結(jié)點(diǎn)都有一個(gè)或多個(gè)孩子 5.也,，.,表示這個(gè)人 在“所代表的時(shí)間點(diǎn)做出的個(gè)不同的選擇可以導(dǎo)向的不同的可能性。 形式化的， 一 個(gè)選擇就是樹上的一條邊(u,3),其中“是 S 的父結(jié)點(diǎn)。一個(gè)人的一牛是從出牛(即根結(jié)點(diǎn)

11、)到死亡(即某一個(gè)葉子結(jié)點(diǎn))的一條不經(jīng)過重 復(fù)結(jié)點(diǎn)的路徑，這條路徑上任何一個(gè)包含至少一條邊的子路徑都是這個(gè)人的一段人生紐 歷，而他或她以所冇可能的方式度過一生，從而擁有的所有人生經(jīng)歷，都被稱為潛在的 人生經(jīng)歷。換言乙所有潛右:的人生經(jīng)歷就是所有“到r的路徑，滿足u.c 7u # ,并FI.是的帳先。 在數(shù)學(xué)匕這樣一個(gè)潛任的人牛經(jīng)歷被記作有序?qū)?u. V),樹T所 育潛在的人生經(jīng)歷的集合記作Pro物理理論不僅允許我們觀測(cè)代衣命運(yùn)的樹，邇能讓我們分析-些潛在的人生經(jīng)J是 否是“重要”的。一個(gè)人所作出的每一個(gè)選擇即樹匕的每一條邊一都可能是重要 或不重要的。一段潛在的人學(xué)經(jīng)歷被稱為朿要的，勺幾僅為其對(duì)

12、應(yīng)的路徑匕存住一條邊 是重要的。我們可以觀測(cè)到一些潛在的人生經(jīng)歷是垂要的：換言之，我們可以觀測(cè)得到 一個(gè)集介Q c Pe滿足其中的所有潛在的人生經(jīng)(n, V)e Q都是重要的。樹廠的形態(tài)早已被計(jì)算確定， 集合Q也早已被觀測(cè)得到， 一個(gè)人命運(yùn)的不確定件 己經(jīng)人人降低了。但不確定性仍然是口人的一來(lái)計(jì)算一下吧，對(duì)于給定的樹T和集合Q,存在多少種不同的方案確定每條邊是否是重要的，使Z滿足所觀測(cè)到的Q所對(duì)應(yīng)的 限制：即對(duì)任憊WQ.都存在條到“路徑上的邊被確定為重耍的。形或化的：給定一棵樹T= (V.E)和點(diǎn)對(duì)集合QCVxV,滿足對(duì)于所有(u, v) Q，都有u 豐L-,并u是r在樹了上的祖先。其中 2

13、和E分別代表樹T的結(jié)點(diǎn)榮和邊 集。求有多少個(gè)不同的函數(shù)J ： E f0.1(將每條邊e E的/(e)值置為0或1),滿 足対于任何(u,v) E Q,都存在“到r路徑匕的一條邊e使得/(e) = I。由于答案可能 非常人，你只需要輸出結(jié)果對(duì)998.244,353(個(gè)索數(shù))取模的結(jié)果?！据斎敫袷健繌奈募estiny, in中讀入數(shù)據(jù)。第 37 屆仝國(guó)用少年信總學(xué)奧林匹克競(jìng)賽第一試命運(yùn)(destiny)第 6 頁(yè)12 91第一行包含一個(gè)正整數(shù)“，表示樹T的大小，樹匕結(jié)點(diǎn)從1到“編號(hào)，I號(hào)結(jié)點(diǎn) 為根結(jié)點(diǎn)；第 37 屆全國(guó)青少年信息學(xué)奧林匹克競(jìng)賽第試命運(yùn)(k-stiny)接下來(lái)n-1行每行包含空格隔

14、開的兩個(gè)數(shù)缺 3滿足1xhy.m表示樹 匕的結(jié)點(diǎn)艾和切之間存在一條邊，但并不保證這條邊的方向；接下來(lái)一行包含一個(gè)非負(fù)整數(shù)m,表示所觀測(cè)得到信息的條數(shù)。接下來(lái)m行每行包含空格隔開的兩個(gè)數(shù)兒也，表示(如,s)Q。請(qǐng)注戳輸入 數(shù)據(jù)可能包含垂復(fù)的信息，換言之可能存在中,滿足均=勺口 =匕。輸入數(shù)據(jù)規(guī)模和限制參見本題末尾的表格。【輸岀格式】輸岀到文件destiny.out中。輸出僅一行一個(gè)整數(shù)，表示方案數(shù)對(duì)90&214.353模的結(jié)果?！緲永?輸入】【樣例1輸出】10【樣例1解釋】共有16種方案，其中不滿足題童的方案有以下6種：(1,2), (2,3), (3,5)確定為不重耍,(3,4)確定為

15、重耍：集合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 頁(yè) 共 12 頁(yè)51233212345第 37 屆全國(guó)

16、育少年信息學(xué)奧林匹克競(jìng)賽第一試命運(yùn)（destiny）第 8 貝 共 12 頁(yè)【樣例 2 輸入】152131435263768495107115121013314915863 125 11253138 151 13【樣例 2 輸岀】960【樣例 3】123456789101112131415161718192021221第 37 屆全國(guó)育少年信息學(xué)奧林匹克競(jìng)賽第一試命運(yùn)（destiny）第 8 貝 共 12 頁(yè)見選手目錄下的destiny/destiny 3. in與destiny/des tiny 3. a【樣例 4】見選手冃錄卜的destiny.in與tiestiny/destiny.ans

17、o笫 37 屆全國(guó)青少年倍息學(xué)奧林匹克競(jìng)賽笫試時(shí)代的眼汨（tPaix）笫 10 頁(yè) 共 12 頁(yè)時(shí)代的眼淚（tears）【題目描述】小L莒歡與智者交流討論，而智者也經(jīng)常為小L出些思考題。這天智者又為小L構(gòu)思了一個(gè)問題。智者首先將時(shí)空抽象為了一個(gè)二維平面，進(jìn)而 將一個(gè)事件抽象為該平面上的一個(gè)點(diǎn)，將一個(gè)時(shí)代抽象為該平面上的一個(gè)矩形。為了方便,下面記（a,b） （c,d）表示平面匕兩個(gè)點(diǎn)（db），（c,）滿足a c,b de更具體地，智苦給定了九個(gè)事件，他們用平面上n個(gè)不同的點(diǎn)（%）=來(lái)表示; 智者還給定了m個(gè)時(shí)代，每個(gè)時(shí)代用平而匕一個(gè)短形（G，ri,2tG.2）來(lái)表示，其中 （和心1）是矩形的左下

18、角，（幾.2,如）是矩形的右上角，保證（F，切）冬（口2心2）。我們 稱時(shí)代/包含了事件j當(dāng)且僅當(dāng)（如,）D （也,知）。智者認(rèn)為若兩個(gè)事件i,J滿足（擊，爐） （町,的），則這兩個(gè)事件形成了一次遺憾。而 對(duì)-個(gè)時(shí)代內(nèi)包含的所何事件，它們所形成的遺憾被稱為這個(gè)時(shí)代旳眼淚.而形成的遺 憾次數(shù)則稱為該時(shí)代的眼淚的大小。現(xiàn)在智者想耍小L計(jì)算每個(gè)時(shí)代的眼祠旳丈小。小L明口，如果他回答不了這個(gè)問題.他也將成為時(shí)代的眼淚，請(qǐng)你幫幫他?！据斎敫袷健繌奈募ear3.in中讀入數(shù)據(jù)。第一行兩個(gè)整數(shù)a, m,分別表示事件數(shù)與時(shí)代數(shù)。第二行n個(gè)整數(shù)”，其屮第個(gè)數(shù)表示事件7：在平面上的坐標(biāo)為仏河）。保證為 一個(gè)1到

19、n,的排列。之后m行，每行四個(gè)整數(shù)口1,八.2沖.1沖,2，表示毎個(gè)時(shí)代對(duì)應(yīng)的矩形?！据攲绺袷健枯敵龅轿募cars.out中 o輸出m行，每行包含一個(gè)整數(shù)，第2行輸出第？個(gè)時(shí)代的眼淚的大小。【樣例 1 輸入】笫 37 屆全國(guó)青少年佶息學(xué)奧林匹克競(jìng)賽笫一試時(shí)代的眼淚(Ward第11頁(yè) 共 12 頁(yè)【樣例1輸岀】142444000【樣例1解釋】對(duì)于時(shí)代1,包含的遺憾有(6,7)(即事件6與事件7形成的遺憾，下同)。對(duì)于時(shí)代2,包含的遺憾有(5,6),(6,7),(5,7), (5,8)。對(duì)于時(shí)代3,包含的遺憾有(5,6),(5.8)。對(duì)于時(shí)代4,包含的遺憾有(5,6),(6,7), (5,7), (5,8)。對(duì)于時(shí)代5,包含的遺憾有(5,6),(07),(5,7),(5,8)。對(duì)于時(shí)代6,包含的遺憾有(5,6), (6,7), (5,7), (5,8)-對(duì)于時(shí)代7,&9,它們均不包含任何遺憾。【樣例21見選手目錄下的tears /tears 2. in與t cars/tears 2. ans該樣例滿足待殊限制4(貝體限制見測(cè)試點(diǎn)約束)?！緲永?】8910111234567891 91