NOIP2015提高組復(fù)賽試題Day2

全國(guó)信息學(xué)奧林匹克聯(lián)賽（2015）復(fù)賽提高組2（請(qǐng)選手務(wù)必仔細(xì)閱讀本頁(yè)內(nèi)容）．題目概況二．提交源程序文件名二．提交源程序文件名中文題目名稱跳石頭子串運(yùn)輸計(jì)劃英文題目與子目錄名可執(zhí)行文件名輸入文件名輸出文件名每個(gè)測(cè)試點(diǎn)時(shí)限1秒1秒1秒測(cè)試點(diǎn)數(shù)目101020每個(gè)測(cè)試點(diǎn)分值10105附加樣例文件有有有結(jié)果比較方式全文比較（過(guò)濾行末空格及文末回車(chē)）題目類(lèi)型傳統(tǒng)傳統(tǒng)傳統(tǒng)運(yùn)行內(nèi)存上限128M128M256M對(duì)于語(yǔ)言對(duì)于C語(yǔ)言對(duì)于語(yǔ)言注意事項(xiàng):1、文件名（程序名和輸入輸出文件名）必須使用英文小寫(xiě)。2、中函數(shù)（）的返回值類(lèi)型必須是，程序正常結(jié)束時(shí)的返回值必須是0。3、全國(guó)統(tǒng)一評(píng)測(cè)時(shí)采用的機(jī)器配置為4、只提供格式附加樣例文件。5、特別提醒：評(píng)測(cè)在當(dāng)前最新公布的（）x24、只提供格式附加樣例文件。5、特別提醒：評(píng)測(cè)在當(dāng)前最新公布的（）x2240,2.8,下進(jìn)行,各語(yǔ)言的編譯器版本以其為準(zhǔn)。11．跳石頭11．跳石頭（）【問(wèn)題描述】一年一度的“跳石頭”比賽又要開(kāi)始了！這項(xiàng)比賽將在一條筆直的河道中進(jìn)行，河道中分布著一些巨大巖石。組委會(huì)已經(jīng)選擇好了兩塊巖石作為比賽起點(diǎn)和終點(diǎn)。在起點(diǎn)和終點(diǎn)之間，有N塊巖石（不含起點(diǎn)和終點(diǎn)的巖石）。在比賽過(guò)程中，選手們將從起點(diǎn)出發(fā)，每一步跳向相鄰的巖石，直至到達(dá)終點(diǎn)。為了提高比賽難度，組委會(huì)計(jì)劃移走一些巖石，使得選手們?cè)诒荣愡^(guò)程中的最短跳躍距離盡可能長(zhǎng)。由于預(yù)算限制，組委會(huì)至多從起點(diǎn)和終點(diǎn)之間移走M(jìn)塊巖石（不能移走起點(diǎn)和終點(diǎn)的巖石）?！据斎敫袷健枯斎胛募麨?。輸入文件第一行包含三個(gè)整數(shù)L,N,M,分別表示起點(diǎn)到終點(diǎn)的距離，起點(diǎn)和終點(diǎn)之間的巖石數(shù)，以及組委會(huì)至多移走的巖石數(shù)。接下來(lái)N行,每行一個(gè)整數(shù),第i行的整數(shù)（0<<L）表示第i塊巖石與起點(diǎn)的距離。這些巖石按與起點(diǎn)距離從小到大的順序給出,且不會(huì)有兩個(gè)巖石出現(xiàn)在同一個(gè)位置?！据敵龈袷健枯敵鑫募麨?。輸出文件只包含一個(gè)整數(shù),即最短跳躍距離的最大值。輸入輸出樣例1】25521417214見(jiàn)選手目錄下的1和1。【輸入輸出樣例1說(shuō)明】將與起點(diǎn)距離為2和14的兩個(gè)巖石移走后,最短的跳躍距離為4（從與起點(diǎn)距離17的巖石跳到距離21的巖石,或者22．子串從距離21的巖石跳到終點(diǎn)）?！据斎胼敵鰳永?】見(jiàn)選手目錄下的2和2?！緮?shù)據(jù)規(guī)模與約定】對(duì)于20%的數(shù)據(jù)，0WMWNW10。對(duì)于50%的數(shù)據(jù)，0WMWNW100。對(duì)于100%的數(shù)據(jù)，0WMWNW50,000，1WLW1,000,000,000。()【問(wèn)題描述】有兩個(gè)僅包含小寫(xiě)英文字母的字符串A和B?，F(xiàn)在要從字符串A中取出k個(gè)互不重疊的非空子串，然后把這k個(gè)子串按照其在字符串A中出現(xiàn)的順序依次連接起來(lái)得到一個(gè)新的字符串,請(qǐng)問(wèn)有多少種方案可以使得這個(gè)新串與字符串B相等？注意：子串取出的位置不同也認(rèn)為是不同的方案?！据斎敫袷健枯斎胛募麨?。第一行是三個(gè)正整數(shù)n，m，k，分別表示字符串A的長(zhǎng)度,字符串B的長(zhǎng)度，以及問(wèn)題描述中所提到的k，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)。第二行包含一個(gè)長(zhǎng)度為n的字符串，表示字符串A。第三行包含一個(gè)長(zhǎng)度為m的字符串，表示字符串B。【輸出格式】輸出文件名為。輸出共一行，包含一個(gè)整數(shù)，表示所求方案數(shù)。由于答案可能很大，所以這里要求輸出答案對(duì)1,000,000,007取模的結(jié)果。輸入輸出樣例1】6312見(jiàn)選手目錄下1與1。輸入輸出樣例2】6327見(jiàn)選手目錄下2與2。輸入輸出樣例3】

6337見(jiàn)選手目錄下3與3。輸入輸出樣例說(shuō)明】所有合法方案如下：（加下劃線的部分表示取出的子串）樣例1：/樣例2：a/a/aa/a一b/_b/b樣例3：aab/aab/aaab/aabaabaab/aaab/aab輸入輸出樣例4】見(jiàn)選手目錄下4與4?！緮?shù)據(jù)規(guī)模與約定】對(duì)于第1組數(shù)據(jù)：lWnW500,lWmW50,1；對(duì)于第2組至第3組數(shù)據(jù)：lWnW500,lWmW50,2；對(duì)于第4組至第5組數(shù)據(jù)：lWnW500,lWmW50,；對(duì)于第1組至第7組數(shù)據(jù)：lWnW500,lWmW50,lWkWm；對(duì)于第1組至第9組數(shù)據(jù)：lWnW1000,lWmW100,lWkWm；對(duì)于所有10組數(shù)據(jù)：lWnW1000,lWmW200,lWkWm。3.3.運(yùn)輸計(jì)劃（）問(wèn)題描述】公元2044年，人類(lèi)進(jìn)入了宇宙紀(jì)元。L國(guó)有n個(gè)星球，還有1條雙向航道，每條航道建立在兩個(gè)星球之間，這1條航道連通了帀的所有星球。小P掌管一家物流公司，該公司有很多個(gè)運(yùn)輸計(jì)劃，每個(gè)運(yùn)輸計(jì)劃形如：有一艘物流飛船需要從號(hào)星球沿最快的宇航路徑飛行到號(hào)星球去。顯然，飛船駛過(guò)一條航道是需要時(shí)間的,對(duì)于航道j，任意飛船駛過(guò)它所花費(fèi)的時(shí)間為，并且任意兩艘飛船之間不會(huì)產(chǎn)生任何干擾。為了鼓勵(lì)科技創(chuàng)新，L國(guó)國(guó)王同意小P的物流公司參與L國(guó)的航道建設(shè)，即允許小P把某一條航道改造成蟲(chóng)洞，飛船駛過(guò)蟲(chóng)洞不消耗時(shí)間。在蟲(chóng)洞的建設(shè)完成前小P的物流公司就預(yù)接了m個(gè)運(yùn)輸計(jì)劃。在蟲(chóng)洞建設(shè)完成后，這m個(gè)運(yùn)輸計(jì)劃會(huì)同時(shí)開(kāi)始，所有飛船一起出發(fā)。當(dāng)這m個(gè)運(yùn)輸計(jì)劃都完成時(shí)，小P的物流公司的階段性工作就完成了。如果小P可以自由選擇將哪一條航道改造成蟲(chóng)洞，試求出小P的物流公司完成階段性工作所需要的最短時(shí)間是多少？【輸入格式】輸入文件名為。第一行包括兩個(gè)正整數(shù)n、m,表示L國(guó)中星球的數(shù)量及小P公司預(yù)接的運(yùn)輸計(jì)劃的數(shù)量，星球從1到n編號(hào)。接下來(lái)1行描述航道的建設(shè)情況，其中第i行包含三個(gè)整數(shù),和，表示第i條雙向航道修建在與兩個(gè)星球之間，任意飛船駛過(guò)它所花費(fèi)的時(shí)間為。接下來(lái)m行描述運(yùn)輸計(jì)劃的情況，其中第j行包含兩個(gè)正整數(shù)和，表示第j個(gè)運(yùn)輸計(jì)劃是從號(hào)星球飛往號(hào)星球【輸出格式】輸出文件名為。共1行，包含1個(gè)整數(shù)，表示小P的物流公司完成階段性工作所需要的最短時(shí)間?！据斎胼敵鰳永?】

【輸入輸出樣例1說(shuō)明】將第1條航道改造成蟲(chóng)洞：則三個(gè)計(jì)劃耗時(shí)分別為：11、12、11，故需要花費(fèi)的時(shí)間為12。將第2條航道改造成蟲(chóng)洞：則三個(gè)計(jì)劃耗時(shí)分別為：7、1511，故需要花費(fèi)的時(shí)間為15。將第3條航道改造成蟲(chóng)洞：則三個(gè)計(jì)劃耗時(shí)分別為：4、811，故需要花費(fèi)的時(shí)間為11。將第4條航道改造成蟲(chóng)洞：則三個(gè)計(jì)劃耗時(shí)分別為：11、15、5，故需要花費(fèi)的時(shí)間為15。將第5條航道改造成蟲(chóng)洞：則三個(gè)計(jì)劃耗時(shí)分別為：11、10、6，故需要花費(fèi)的時(shí)間為11。故將第3條或第5條航道改造成蟲(chóng)洞均可使得完成階段性工作的耗時(shí)最短，需要花費(fèi)的時(shí)間為11?！緲永斎胼敵?】見(jiàn)選手目錄下的2與2。數(shù)據(jù)規(guī)模與約定】所有測(cè)試數(shù)據(jù)的范圍和特點(diǎn)如下表所示測(cè)試點(diǎn)編號(hào)約定110012100第i條航道連接i號(hào)星球與1號(hào)星球3420001510001000第i條航道連接i號(hào)星球與1號(hào)星球620002000730003000810001000920002000103000300011800001請(qǐng)注意常數(shù)因子帶來(lái)的程序效率上的影響。請(qǐng)注意常數(shù)因子帶來(lái)的程序效率上的影響。請(qǐng)注意常數(shù)因子帶來(lái)的程序效率上的影響。請(qǐng)注意常數(shù)因子帶來(lái)的程序效率上的影響。12/