1、2014-5-24 NOIPby hzwer共4道題目，時(shí)間3.5小時(shí)大家盡量多拿分就是了提醒：c+輸出long long請(qǐng)使用%I64d或者cout輸出時(shí)請(qǐng)注意類型的正確預(yù)祝各位虐場成功題目名護(hù)花修建草坪蟲洞麻將源文件flower.cpp/c/pasmowlawn.cpp/c/paswormhole.cpp/c/pasdata.cpp/c/pas輸入文件flower.inmowlawn.inwormhole.indata.in輸出文件flower.outmowlawn.outWormhole.outdata.out時(shí)間限制1000MS1000MS1000MS1000MS內(nèi)存限制256MB25

2、6MB256MB256MB測試點(diǎn)10101010測試點(diǎn)分值10101010因?yàn)榍叭}題目來自u(píng)saco，數(shù)據(jù)可能較弱，因此會(huì)根據(jù)實(shí)際情況調(diào)整實(shí)際測評(píng)時(shí)間限制以防暴力AK評(píng)測環(huán)境操作系統(tǒng)：Windows XP SP3CPU: Pentium(R) Dual-Core CPU E5300 2.60Ghz(2CPUs)系統(tǒng)內(nèi)存：2GBProblem 1 護(hù)花(flower.cpp/c/pas)【題目描述】約翰留下他的N(N=100000)只奶牛上山采木他離開的時(shí)候，她們像往常一樣悠閑地在草場里吃草可是，當(dāng)他回來的時(shí)候，他看到了一幕慘?。号冋阍谒幕▓@里，啃食著他心愛的美麗花朵！為了使接下來花朵的

3、損失最小，約翰趕緊采取行動(dòng)，把牛們送回牛棚牛們從1到N編號(hào)第i只牛所在的位置距離牛棚Ti(1Ti2000000)分鐘的路程，而在約翰開始送她回牛棚之前，她每分鐘會(huì)啃食Di(1Di100)朵鮮花無論多么努力，約翰一次只能送一只?；嘏锒\(yùn)送第第i只牛事實(shí)上需要2Ti分鐘，因?yàn)閬砘囟夹枰獣r(shí)間寫一個(gè)程序來決定約翰運(yùn)送奶牛的順序，使最終被吞食的花朵數(shù)量最小【輸入格式】第1行輸入N，之后N行每行輸入兩個(gè)整數(shù)Ti和Di【輸出格式】一個(gè)整數(shù)，表示最小數(shù)量的花朵被吞食【樣例輸入】63 12 52 33 24 11 6【樣例輸出】86【樣例解釋】約翰用6，2，3，4，1，5的順序來運(yùn)送他的奶牛 Problem 2

4、 修剪草坪(mowlawn.cpp/c/pas)【題目描述】在一年前贏得了小鎮(zhèn)的最佳草坪比賽后，F(xiàn)J變得很懶，再也沒有修剪過草坪?，F(xiàn)在，新一輪的最佳草坪比賽又開始了，F(xiàn)J希望能夠再次奪冠。然而，F(xiàn)J的草坪非常臟亂，因此，F(xiàn)J只能夠讓他的奶牛來完成這項(xiàng)工作。FJ有N(1 = N = 100,000)只排成一排的奶牛，編號(hào)為1.N。每只奶牛的效率是不同的，奶牛i的效率為E_i(0 = E_i = 1,000,000,000)?？拷哪膛兒苁煜ぃ虼?，如果FJ安排超過K（1=K=N）只連續(xù)的奶牛，那么，這些奶牛就會(huì)罷工去開派對(duì):)。因此，現(xiàn)在FJ需要你的幫助，計(jì)算FJ可以得到的最大效率，并且該方案

5、中沒有連續(xù)的超過K只奶牛。【輸入格式】* 第一行：空格隔開的兩個(gè)整數(shù)N和K* 第二到N+1行：第i+1行有一個(gè)整數(shù)E_i【輸出格式】* 第一行：一個(gè)值，表示FJ可以得到的最大的效率值?！緲永斎搿? 212345輸入解釋：FJ有5只奶牛，他們的效率為1，2，3，4，5。他們希望選取效率總和最大的奶牛，但是他不能選取超過2只連續(xù)的奶牛【樣例輸出】12FJ可以選擇出了第三只以外的其他奶牛，總的效率為1+2+4+5=12。Problem 3 蟲洞(wormhole.cpp/c/pas)【題目描述】John在他的農(nóng)場中閑逛時(shí)發(fā)現(xiàn)了許多蟲洞。蟲洞可以看作一條十分奇特的有向邊，并可以使你返回到過去的一個(gè)時(shí)

6、刻（相對(duì)你進(jìn)入蟲洞之前）。John的每個(gè)農(nóng)場有M條小路（無向邊）連接著N （從1.N標(biāo)號(hào)）塊地，并有W個(gè)蟲洞（有向邊）。其中1=N=500,1=M=2500,1=W=200。 現(xiàn)在John想借助這些蟲洞來回到過去（出發(fā)時(shí)刻之前），請(qǐng)你告訴他能辦到嗎。 John將向你提供F(1=F=5)個(gè)農(nóng)場的地圖。沒有小路會(huì)耗費(fèi)你超過10000秒的時(shí)間，當(dāng)然也沒有蟲洞回幫你回到超過10000秒以前?！据斎敫袷健? Line 1: 一個(gè)整數(shù) F, 表示農(nóng)場個(gè)數(shù)。* Line 1 of each farm: 三個(gè)整數(shù) N, M, W。* Lines 2.M+1 of each farm: 三個(gè)數(shù)（S, E, T）

7、。表示在標(biāo)號(hào)為S的地與標(biāo)號(hào)為E的地中間有一條用時(shí)T秒的小路。* Lines M+2.M+W+1 of each farm: 三個(gè)數(shù)（S, E, T）。表示在標(biāo)號(hào)為S的地與標(biāo)號(hào)為E的地中間有一條可以使John到達(dá)T秒前的蟲洞?！据敵龈袷健? Lines 1.F: 如果John能在這個(gè)農(nóng)場實(shí)現(xiàn)他的目標(biāo)，輸出YES,否則輸出NO?！緲永斎搿?3 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8【樣例輸出】NOYESProblem 4 麻將(data.cpp/c/pas)【題目描述】眾所周知，麻將是我們國家的國粹。這段時(shí)間，小D也迷上了麻將這個(gè)老少皆宜的游戲。小

8、D覺得這些不同規(guī)則的麻將太麻煩了，所以他集合了很多種麻將規(guī)則創(chuàng)造出了一套D麻將。下面是D麻將的幾個(gè)特點(diǎn)：D麻將中有三種花色，萬（w）索（s）筒（t），每個(gè)花色下有9張牌，每張牌有4個(gè)。D麻將中沒有杠牌，只有順子和刻子。順子的含義是相同花色的三張連在一起的牌型（比如說2w3w4w）；刻子的含義是三張花色和數(shù)字都相同的牌型（比如說2s2s2s）。D麻將的胡牌的時(shí)候手上往往有14張牌，14張牌湊成了四個(gè)順子或刻子和兩張一樣的牌做雀頭就可以胡牌了。D麻將胡牌的時(shí)候有很多種不同的牌型，不同的牌型會(huì)有不一樣的番數(shù)。你的一種牌型可能滿足了多個(gè)加番牌型，滿足多個(gè)的情況下就把所有滿足的牌型的番數(shù)全部加起來計(jì)算。

9、D麻將中有如下牌型可以加番：平和（一番）：4個(gè)順子組成；一杯口（一番）：同花色同數(shù)值的順子兩組；混全帶幺九（一番）：全部的順子，刻子中都含有數(shù)字1或9；三色同順（一番）：三種花色同數(shù)值的順子各一組；一氣貫通（兩番）：由同花色一至九組成順子；對(duì)對(duì)和（兩番）：四組刻子；斷幺九（兩番）：胡牌的時(shí)候手上只有2-8的數(shù)字組成的牌型；一色三順（三番）：同花色同數(shù)值順子三組；兩杯口（三番）：由兩組不同的一杯口組成；三色同刻（四番）：三種花色同數(shù)值的刻子各一組；清老頭（五番）：全部由1或9的刻子和雀頭組成；清一色（七番）：全部由同一種花色的順子，刻子及雀頭組成；比如說一個(gè)牌型為1s2s3s4s5s6s7s8s9s1s2s3s9s9s的牌，它滿足了平和、一杯口、一氣貫通、清一色四個(gè)牌型，所以它的番數(shù)是10番。小D希望為D麻將做一個(gè)程序來幫