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

1、CCF 全國信息學(xué)奧林匹克聯(lián)賽（NOIP2015）復(fù)賽提高組 day2（請選手務(wù)必仔細閱讀本頁內(nèi)容）一題目概況中文題目名稱跳石頭子串運輸計劃英文題目與子目錄名stonesubstringtransport可執(zhí)行文件名stonesubstringtransport輸入文件名ransport.in輸出文件名stone.outsubstring.outtransport.out每個測試點時限1 秒1 秒1 秒測試點數(shù)目101020每個測試點分值10105附加樣例文件有有有結(jié)果比較方式全文比較（過濾行末空格及文末回車）題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)運行內(nèi)存上限128M1

2、28M256M二提交源程序文件名對于 C+語言stone.cppsubstring.cpptransport.cpp對于 C 語言stone.csubstring.ctransport.c對于 pascal 語言stone.passubstring.pastransport.pas三編譯命令（不包含任何優(yōu)化開關(guān)）對于 C+語言g+ -o stoneg+ -o substringg+ -o transportstone.cpp -lmsubstring.cpp -lmtransport.cpp -lm對于 C 語言gcc -o stone stone.cgcc -o substringgcc -

3、o transport-lmsubstring.c -lmtransport.c -lm對于 pascal 語言fpc stone.pasfpc substring.pasfpc transport.pas注意事項：1、文件名（程序名和輸入輸出文件名）必須使用英文小寫。2、C/C+中函數(shù) main()的返回值類型必須是 int，程序正常結(jié)束時的返回值必須是 0。 3、全國統(tǒng)一評測時采用的機器配置為：CPU AMD Athlon(tm) II x2 240 processor，2.8GHz，內(nèi)存 4G，上述時限以此配置為準。4、只提供 Linux 格式附加樣例文件。5、特別提醒：評測在當(dāng)前最新公

4、布的 NOI Linux 下進行，各語言的編譯器版本以其為準。1跳石頭(stone.cpp/c/pas)【問題描述】 一年一度的“跳石頭”比賽又要開始了！這項比賽將在一條筆直的河道中進行，河道中分布著一些巨大巖石。組委會已經(jīng)選擇好了兩塊巖石作為比賽起點和終點。在起點和終點之間，有 N 塊巖石（不含起點和終點的巖石）。在比賽過程中，選手們將從起點出發(fā)，每一步跳向相鄰的巖石，直至到達終點。為了提高比賽難度，組委會計劃移走一些巖石，使得選手們在比賽過程中的最短跳躍距離盡可能長。由于預(yù)算限制，組委會至多從起點和終點之間移走 M 塊巖石（不能移走起點和終點的巖石）?！据斎敫袷健?輸入文件名為 stone

5、.in。輸入文件第一行包含三個整數(shù) L，N，M，分別表示起點到終點的距離，起點和終點之間的巖石數(shù)，以及組委會至多移走的巖石數(shù)。接下來 N 行，每行一個整數(shù)，第 i 行的整數(shù) Di（0 < Di < L）表示第 i 塊巖石與 起點的距離。這些巖石按與起點距離從小到大的順序給出，且不會有兩個巖石出現(xiàn)在同一個位置?！据敵龈袷健枯敵鑫募麨?stone.out。輸出文件只包含一個整數(shù)，即最短跳躍距離的最大值。【輸入輸出樣例 1】stone.instone.out25 5 22111417214見選手目錄下的 stone/stone1.in 和 stone/stone1.ans。【輸入輸出樣

6、例 1 說明】將與起點距離為 2 和 14 的兩個巖石移走后，最短的跳躍距離為 4（從與起點距離 17 的巖石跳到距離 21 的巖石，或者從距離 21 的巖石跳到終點）?！据斎胼敵鰳永?2】見選手目錄下的 stone/stone2.in 和 stone/stone2.ans?！緮?shù)據(jù)規(guī)模與約定】對于 20%的數(shù)據(jù)，0 M N 10。對于 50%的數(shù)據(jù)，0 M N 100。對于 100%的數(shù)據(jù)，0 M N 50,000，1 L 1,000,000,000。2子串(substring.cpp/c/pas)【問題描述】有兩個僅包含小寫英文字母的字符串A和B?，F(xiàn)在要從字符串A中取出k個互不重疊的非空子串

7、，然后把這 k 個子串按照其在字符串 A 中出現(xiàn)的順序依次連接起來得到一個新的字符串，請問有多少種方案可以使得這個新串與字符串 B 相等？注意：子串取出的位置不同也認為是不同的方案?！据斎敫袷健枯斎胛募麨?substring.in。第一行是三個正整數(shù) n，m，k，分別表示字符串 A 的長度，字符串 B 的長度，以及問題描述中所提到的 k，每兩個整數(shù)之間用一個空格隔開。第二行包含一個長度為 n 的字符串，表示字符串A。第三行包含一個長度為 m 的字符串，表示字符串B?！据敵龈袷健枯敵鑫募麨?substring.out。輸出共一行，包含一個整數(shù)，表示所求方案數(shù)。由于答案可能很大，所以這里要求輸

8、出答案對 1,000,000,007 取模的結(jié)果?！据斎胼敵鰳永?1】substring.insubstring.out6 3 1aabaabaab2見選手目錄下 substring/substring1.in 與 substring/substring1.ans?！据斎胼敵鰳永?2】substring.insubstring.out6 3 2aabaabaab7見選手目錄下 substring/substring2.in 與 substring/substring2.ans?！据斎胼敵鰳永?3】substring.insubstring.out6 3 3aabaabaab7見選手目錄下 su

9、bstring/substring3.in 與 substring/substring3.ans?！据斎胼敵鰳永f明】 所有合法方案如下：（加下劃線的部分表示取出的子串） 樣例 1：aab aab / aab aab 樣例 2：a ab aab / a aba ab / a a ba ab / aab a ab aa b aab / aa baa b / aab aa b 樣例 3：a a b aab / a a baa b / a ab a a b / a aba a b a a b a a b / a a ba a b / aab a a b 【輸入輸出樣例 4】見選手目錄下 substr

10、ing/substring4.in 與 substring/substring4.ans?！緮?shù)據(jù)規(guī)模與約定】對于第 1 組數(shù)據(jù)：1n500，1m50，k=1；對于第 2 組至第 3 組數(shù)據(jù)：1n500，1m50，k=2； 對于第 4 組至第 5 組數(shù)據(jù)：1n500，1m50，k=m； 對于第 1 組至第 7 組數(shù)據(jù)：1n500，1m50，1km； 對于第 1 組至第 9 組數(shù)據(jù)：1n1000，1m100，1km； 對于所有 10 組數(shù)據(jù)：1n1000，1m200，1km。3. 運輸計劃（transport.cpp/c/pas)【問題描述】公元 2044 年，人類進入了宇宙紀元。L 國有 n 個

11、星球，還有 n-1 條雙向航道，每條航道建立在兩個星球之間，這 n-1 條航道連通了 L 國的所有星球。小 P 掌管一家物流公司，該公司有很多個運輸計劃，每個運輸計劃形如：有一艘物流飛船需要從 ui 號星球沿最快的宇航路徑飛行到 vi 號星球去。顯然，飛船駛過一條航道是需要時間的，對于航道j，任意飛船駛過它所花費的時間為 tj，并且任意兩艘飛船之間不會產(chǎn)生任何干擾。為了鼓勵科技創(chuàng)新，L 國國王同意小 P 的物流公司參與 L 國的航道建設(shè)，即允許小 P 把某一條航道改造成蟲洞，飛船駛過蟲洞不消耗時間。在蟲洞的建設(shè)完成前小 P 的物流公司就預(yù)接了 m 個運輸計劃。在蟲洞建設(shè)完成后，這 m 個運輸計

12、劃會同時開始，所有飛船一起出發(fā)。當(dāng)這 m 個運輸計劃都完成時，小 P 的 物流公司的階段性工作就完成了。如果小 P 可以自由選擇將哪一條航道改造成蟲洞，試求出小 P 的物流公司完成階段性工作所需要的最短時間是多少？【輸入格式】輸入文件名為 transport.in。第一行包括兩個正整數(shù) n、m，表示 L 國中星球的數(shù)量及小 P 公司預(yù)接的運輸計劃的數(shù)量，星球從 1 到 n 編號。接下來 n-1 行描述航道的建設(shè)情況，其中第 i 行包含三個整數(shù) ai, bi 和 ti，表示第 i 條雙向航道修建在 ai 與 bi 兩個星球之間，任意飛船駛過它所花費的時間為 ti。接下來 m 行描述運輸計劃的情況

13、，其中第 j 行包含兩個正整數(shù) uj 和 vj，表示第 j 個 運輸計劃是從 uj 號星球飛往 vj 號星球。【輸出格式】輸出文件名為 transport.out。共 1 行，包含 1 個整數(shù)，表示小 P 的物流公司完成階段性工作所需要的最短時間?！据斎胼敵鰳永?1】ransport.out6 31 2 31 6 43 1 74 3 63 5 53 62 54 511見選手目錄下的 transport/transport1.in 與 transport/transport1.ans?！据斎胼敵鰳永?1 說明】將第 1 條航道改造成蟲洞：則三個計劃耗時分別為：11、12

14、、11，故需要花費的時間為 12。將第 2 條航道改造成蟲洞：則三個計劃耗時分別為：7、15、11，故需要花費的時間為 15。將第 3 條航道改造成蟲洞：則三個計劃耗時分別為：4、8、11，故需要花費的時間為 11。將第 4 條航道改造成蟲洞：則三個計劃耗時分別為：11、15、5，故需要花費的時間為 15。將第 5 條航道改造成蟲洞：則三個計劃耗時分別為：11、10、6，故需要花費的時間為 11。故將第 3 條或第 5 條航道改造成蟲洞均可使得完成階段性工作的耗時最短，需要花費的時間為 11?！緲永斎胼敵?2】見選手目錄下的 transport/transport2.in 與 transport/transport2.ans?！緮?shù)據(jù)規(guī)模與約定】所有測試數(shù)據(jù)的范圍和特點如下表所示測試點編號n=m=約定110012100第 i 條航道連接 i 號星球與 i+1 號星球3420001510001000第 i 條航道連接 i 號星球與 i+1 號星球6200