1、精選優(yōu)質(zhì)文檔-傾情為你奉上第22屆全國青少年信息學奧林匹克聯(lián)賽CCF-NOIP-2016提高組（復賽）第一試競賽時間：2016年11月19日8:3012:00題目名稱玩具謎題天天愛跑步換教室題目類型傳統(tǒng)型傳統(tǒng)型傳統(tǒng)型目錄toyrunningclassroom可執(zhí)行文件名toyrunningclassroom輸入文件名toy.inrunning.inclassroom.in輸出文件名toy.outrunning.outclassroom.out每個測試點時限1.0秒2.0秒1.0秒內(nèi)存限制512MB512MB512MB測試點數(shù)目202025每個測試點分值554提交源程序文件名對于C+語言toy.

2、cpprunning.cppclassroom.cpp對于C語言toy.crunning.cclassroom.c對于Pascal語言toy.pasrunning.pasclassroom.pas編譯選項對于C+語言-lm-lm-lm對于語言-lm-lm-lm對于Pascal語言注意事項：1文件名（程序名和輸入輸出文件名）必須使用英文小寫。2除非特殊說明，結果比較方式均為忽略行末空格及文末回車的全文比較。3C/C+中函數(shù)main()的返回值類型必須是int，程序正常結束時的返回值必須是0。4全國統(tǒng)一評測時采用的機器配置為：CPU AMD Athlon(tm) X2 240 processor

3、2.8GHz，內(nèi)存4G，上述時限以此配置為準。5只提供Linux格式附加樣例文件。6評測在NOI Linux下進行。7編譯時不打開任何優(yōu)化選項。專心-專注-專業(yè)玩具謎題（toy）【問題描述】小南有一套可愛的玩具小人，它們各有不同的職業(yè)。有一天，這些玩具小人把小南的眼鏡藏了起來。小南發(fā)現(xiàn)玩具小人們圍成了一個圈，它們有的面朝圈內(nèi)，有的面朝圈外。如下圖：這時singer告訴小南一個謎題：“眼鏡藏在我左數(shù)第3個玩具小人的右數(shù)第1個玩具小人的左數(shù)第2個玩具小人那里?！毙∧习l(fā)現(xiàn)，這個謎題中玩具小人的朝向非常關鍵，因為朝內(nèi)和朝外的玩具小人的左右方向是相反的：面朝圈內(nèi)的玩具小人，它的左邊是順時針方向，右邊是逆

4、時針方向；而面向圈外的玩具小人，它的左邊是逆時針方向，右邊是順時針方向。小南一邊艱難地辨認著玩具小人，一邊數(shù)著：“singer”朝內(nèi)，左數(shù)第3個是archer。“archer”朝外，右數(shù)第1個是thinker?！皌hinker”朝外，左數(shù)第2個是writer。“所以眼鏡藏在writer這里！”雖然成功找回了眼鏡，但小南并沒有放心。如果下次有更多的玩具小人藏他的眼鏡，或是謎題的長度更長，他可能就無法找到眼鏡了。所以小南希望你寫程序幫他解決類似的謎題。這樣的謎題具體可以描述為：有n個玩具小人圍成一圈，已知它們的職業(yè)和朝向?，F(xiàn)在第1個玩具小人告訴小南一個包含m條指令的謎題，其中第i條指令形如“左數(shù)/

5、右數(shù)第si個玩具小人”。你需要輸出依次數(shù)完這些指令后，到達的玩具小人的職業(yè)?！据斎敫袷健繌奈募oy.in中讀入數(shù)據(jù)。輸入的第一行包含兩個正整數(shù)n,m，表示玩具小人的個數(shù)和指令的條數(shù)。接下來n行，每行包含一個整數(shù)和一個字符串，以逆時針為順序給出每個玩具小人的朝向和職業(yè)。其中0表示朝向圈內(nèi)，1表示朝向圈外。保證不會出現(xiàn)其他的數(shù)。字符串長度不超過10且僅由小寫字母構成，字符串不為空，并且字符串兩兩不同。整數(shù)和字符串之間用一個空格隔開。接下來m行，其中第i行包含兩個整數(shù)ai，si，表示第i條指令。若ai=0，表示向左數(shù)si個人；若ai=1，表示向右數(shù)si個人。保證ai不會出現(xiàn)其他的數(shù)，1=sin?！?/p>

6、輸出格式】輸出到文件toy.out中。輸出一個字符串，表示從第一個讀入的小人開始，依次數(shù)完m條指令后到達的小人的職業(yè)?！緲永?輸入】7 30 singer0 reader1 thinker1 archer0 write1 mogician0 31 10 2【樣例1輸出】writer【樣例1說明】這組數(shù)據(jù)就是【題目描述】中提到的例子?！緲永?輸入】10 101 c0 r0 p1 d1 e1 m1 t1 y1 u0 v1 71 11 40 50 30 11 61 20 80 4【樣例2輸出】y【子任務】子任務會給出部分測試數(shù)據(jù)的特點。如果你在解決題目中遇到了困難，可以嘗試只解決一部分測試數(shù)據(jù)。每個

7、測試點的數(shù)據(jù)規(guī)模及特點如下表：測試點nm全朝內(nèi)全左數(shù)si=1職業(yè)長度為11= 20= 103234567891011121314151617= 105= 10518X19X20X其中一些簡寫的列意義如下：l 全朝內(nèi)：若為“”，表示該測試點保證所有的玩具小人都朝向圈內(nèi)；l 全左數(shù)：若為“”，表示該測試點保證所有的指令都向左數(shù)，即對任意的1=i=m，ai=0；l si=1：若為“”，表示該測試點保證所有的指令都只數(shù)1個，即對任意的1=i=m，si=1；l 職業(yè)長度為1：若為“”，表示該測試點保證所有玩具小人的職業(yè)一定是一個長度為1的字符串。天天愛跑步（running）【問題描述】小C同學認為跑步非

8、常有趣，于是決定制作一款叫做天天愛跑步的游戲。天天愛跑步是一個養(yǎng)成類游戲，需要玩家每天按時上線，完成打卡任務。這個游戲的地圖可以看作一棵包含n個結點和n-1條邊的樹，每條邊連接兩個結點，且任意兩個結點存在一條路徑互相可達。樹上結點編號為從1到n的連續(xù)正整數(shù)?，F(xiàn)在有m個玩家，第i個玩家的起點為Si，終點為Ti。每天打卡任務開始時，所有玩家在第0秒同時從自己的起點出發(fā)，以每秒跑一條邊的速度，不間斷地沿著最短路徑向著自己的終點跑去，跑到終點后該玩家就算完成了打卡任務。（由于地圖是一棵樹，所以每個人的路徑是唯一的）小C想知道游戲的活躍度，所以在每個結點上都放置了一個觀察員。在結點J的觀察員會選擇在第W

9、j秒觀察玩家，一個玩家能被這個觀察員觀察到當且僅當該玩家在第Wj秒也正好到達了結點J。小C想知道每個觀察員會觀察到多少人？注意：我們認為一個玩家到達自己的終點后該玩家就會結束游戲，他不能等待一段時間后再被觀察員觀察到。即對于把結點J作為終點的玩家：若他在第Wj秒前到達終點，則在結點J的觀察員不能觀察到該玩家；若他正好在第Wj秒到達終點，則在結點J的觀察員可以觀察到這個玩家?！据斎敫袷健繌奈募unning.in中讀入數(shù)據(jù)。第一行有兩個整數(shù)n和m。其中n代表樹的結點數(shù)量，同時也是觀察員的數(shù)量，m代表玩家的數(shù)量。接下來n-1行每行兩個整數(shù)u和v，表示結點u到結點v有一條邊。接下來一行n個整數(shù)，其中

10、第J個整數(shù)為Wj，表示結點J出現(xiàn)觀察員的時間。接下來m行，每行兩個整數(shù)Si和Ti，表示一個玩家的起點和終點。對于所有的數(shù)據(jù)，保證1=Si,Ti=n，0=Wj=n?！据敵龈袷健枯敵龅轿募unning.out中。輸出1行n個整數(shù)，第j個整數(shù)表示結點J的觀察員可以觀察到多少人?！緲永?輸入】6 32 31 21 44 54 60 2 5 1 2 31 52 6【樣例1輸出】2 0 0 1 1 1【樣例1說明】對于1號點，W1=0，故只有起點為1號點的玩家才會被觀察到，所以玩家1和玩家2被觀察到，共2人被觀察到。對于2號點，沒有玩家在第2秒時在此結點，共0人被觀察到。對于3號點，沒有玩家在第5秒時在

11、此結點，共0人被觀察到。對于4號點，玩家1被觀察到，共1人被觀察到。對于5號點，玩家2被觀察到，共1人被觀察到。對于6號點，玩家3被觀察到，共1人被觀察到。【樣例2輸入】5 31 22 32 41 50 1 0 3 03 11 45 5【樣例2輸出】1 2 1 0 1【子任務】每個測試點的數(shù)據(jù)規(guī)模及特點如下表所示。提示：數(shù)據(jù)范圍的個位上的數(shù)宇可以幫助判斷是哪一種數(shù)據(jù)類型。測試點編號nm約定1= 991= 991所有人的起點等于自己的終點，即Si=Ti23= 992= 992Wj=045= 993= 993無6= 99994= 99994樹退化成一條鏈，其中1與2有邊，2與3有邊，n-1與n有邊

12、789= 99995= 99995所有的Si=110111213= 99996= 99996所有的Ti=114151617= 99997= 99997無181920= = 【提示】如果你的程序需要用到較大的棧空間（這通常意味著需要較深層數(shù)的遞歸），請務必仔細閱讀選手目錄下的文檔running/stack.pdf，以了解在最終評測時?？臻g的限制與在當前工作環(huán)境下調(diào)整棧空間限制的方法。換教室（classroom）【問題描述】對于剛上大學的牛牛來說，他面臨的第一個問題是如何根據(jù)實際情況申請合適的課程。在可以選擇的課程中，有2n節(jié)課程安排在n個時間段上。在第i（1=i=n）個時間段上，兩節(jié)內(nèi)容相同的課

13、程同時在不同的地點進行，其中，牛牛預先被安排在教室ci上課，而另一節(jié)課程在教室di進行。在不提交任何申請的情況下，學生們需要按時間段的順序依次完成所有的n節(jié)安排好的課程。如果學生想更換第i節(jié)課程的教室，則需要提出申請。若申請通過，學生就可以在第i個時間段去教室di上課，否則仍然在教室ci上課。由于更換教室的需求太多，申請不一定能獲得通過。通過計算，牛牛發(fā)現(xiàn)申請更換第i節(jié)課程的教室時，申請被通過的概率是一個已知的實數(shù)ki，并且對于不同課程的申請，被通過的概率是互相獨立的。學校規(guī)定，所有的申請只能在學期開始前一次性提交，并且每個人只能選擇至多m節(jié)課程進行申請。這意味著牛牛必須一次性決定是否申請更換

14、每節(jié)課的教室，而不能根據(jù)某些課程的申請結果來決定其他課程是否申請；牛?？梢陨暾堊约鹤钕Ｍ鼡Q教室的m門課程，也可以不用完這m個申請的機會，甚至可以一門課程都不申請。因為不同的課程可能會被安排在不同的教室進行，所以牛牛需要利用課間時間從一間教室趕到另一間教室。牛牛所在的大學有v個教室，有e條道路。每條道路連接兩間教室，并且是可以雙向通行的。由于道路的長度和擁堵程度不同，通過不同的道路耗費的體力可能會有所不同。當?shù)趇（1=i=n-1）節(jié)課結束后，牛牛就會從這節(jié)課的教室出發(fā)，選擇一條耗費體力最少的路徑前往下一節(jié)課的教室。現(xiàn)在牛牛想知道，申請哪幾門課程可以使他因在教室間移動耗費的體力值的總和的期望值最

15、小，請你幫他求出這個最小值?！据斎敫袷健繌奈募lassroom.in中讀入數(shù)據(jù)。第一行四個整數(shù)n,m,v,e。n表示這個學期內(nèi)的時間段的數(shù)量；m表示牛牛最多可以申請更換多少節(jié)課程的教室；v表示牛牛學校里教室的數(shù)量；e表示牛牛的學校里道路的數(shù)量。第二行n個正整數(shù)，第i（1=i=n）個正整數(shù)表示ci。，即第i個時間段牛牛被安排上課的教室；保證1=ci=v。第三行n個正整數(shù)，第i（1=i=n）個正整數(shù)表示di，即第i個時間段另一間上同樣課程的教室；保證1=di=v。第四行n個實數(shù)，第i（1=i=n）個實數(shù)表示ki，即牛牛申請在第i個時間段更換教室獲得通過的概率。保證0=ki=1。接下來e行，每行三

16、個正整數(shù)aj，bj，wj，表示有一條雙向道路連接教室aj，bj，通過這條道路需要耗費的體力值是wj；保證1=aj，bj=v。保證1=n=2000，0=m=2000，1=v=300，0=e=90000。保證通過學校里的道路，從任何一間教室出發(fā)，都能到達其他所有的教室。保證輸入的實數(shù)最多包含3位小數(shù)?！据敵龈袷健枯敵龅轿募lassroom.out中。輸出一行，包含一個實數(shù)，四舍五入精確到小數(shù)點后恰好2位，表示答案。你的輸出必須和標準輸出完全一樣才算正確。測試數(shù)據(jù)保證四舍五入后的答案和準確答案的差的絕對值不大于4*10-3。（如果你不知道什么是浮點誤差，這段話可以理解為：對于大多數(shù)的算法，你可以正

17、常地使用浮點數(shù)類型而不用對它進行特殊的處理）【樣例1輸入】3 2 3 32 1 21 2 10.8 0.2 0.51 2 51 3 32 3 1【樣例1輸出】2.80【樣例1說明】所有可行的申請方案和期望收益如下表：申請更換教室的時間段申請通過的時間段出現(xiàn)的概率耗費的體力值耗費的體力值的期望無無1.088.0110.844.8無0.28220.206.4無0.88330.546.0無0.581、21、20.1644.4810.64420.040無0.1681、31、30.402.810.4430.14無0.182、32、30.145.220.1030.44無0.48【樣例2】見選手目錄下的classroom/classroom2.in與classroom/classroom2.ans。【提示】1道路中可能會有多條雙向道路連接相同的兩間教室。也有可能有道路兩端連接的是同一間教室。2請注意區(qū)分n,m,v,e的意義，n不是教室的數(shù)量，m不是道路的數(shù)量。【子任務】測試點nmv特殊性質(zhì)1特殊性質(zhì)21= 1= 1= 300XX2= 2= 0= 203= 1= 1004=