資源簡介

全國信息學奧林匹克聯賽（ NOIP2018）復賽 提高組 day2
CCF 全國信息學奧林匹克聯賽 （ NOIP2018） 復賽

提高 組 day2
（請選手務必仔細閱讀本頁內容）

一．題目概況
中文題目名稱 旅行 填數游戲 保衛王國
英文題目與子目錄名 travel game defense
可執行文件名 travel game defense
輸入文件名 travel.in game.in defense.in
輸出文件名 travel.out game.out defense.out
每個測試點時限 1s 1s 2s
測試點數目 25 20 25
每個測試點分值 4 5 4
附加樣例文件 有 有 有
結果比較方式 全文比較（過濾行末空格及文末回車）
題目類型 傳統 傳統 傳統
運行內存上限 512MB 512MB 512MB

二．提交源程序文件名
對于 C++語言 travel.cpp game.cpp defense.cpp
對于 C語言 travel.c game.c defense.c
對于 pascal語言 travel.pas game.pas defense.pas

三．編譯命令（不包含任何優化開關）
對于 C++語言 g++ -o travel g++ -o game game.cpp g++ -o defense
travel.cpp -lm -lm defense.cpp -lm
對于 C語言 gcc -o travel travel.c gcc -o game game.c gcc -o defense
-lm -lm defense.c -lm
對于 pascal語言 fpc travel.pas fpc game.pas fpc defense.pas

注意 事項 ：
1、 文件名 （程序名和輸入輸出文件名） 必須使用 英文 小寫 。
2、 C/C++中函數 main()的返回值類型必須是 int，程序正常結束時的返回值必須是 0。
3、 全國統一評測時采用的機器配置為： Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz，內存
32GB。 上述時限以此配置為準 。
4、只提供 Linux格式附加樣例文件。
5、特別提醒： 評測在當前最新公布的 NOI Linux下進行，各語言的編譯器版本以其為準 。


第 1頁共 8頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 提高組 day2
1．旅行
(travel.cpp/c/pas)
【問題描述】
小 Y是一個愛好旅行的 OIer。她來到 X國，打算將各個城市都玩一遍。
小 Y了解到， X國的 ???? 個城市之間有 ???? 條 雙向道路 。 每條雙向道路連接兩個城市。
不存在兩條連接同一對城市的道路，也不存在一條連接一個城市和它本身的道路。并且，
從任意一個城市出發，通過這些道路都可以到達任意一個其他城市 。 小 Y只能通過這些
道路從一個城市前往另一個城市。
小 Y的旅行方案是這樣的： 任意選定一個城市作為起點，然后從起點開始， 每次可
以選擇一條與當前城市相連的道路，走向一個 沒有去過 的城市，或者沿著 第一次 訪問該
城市時經過的道路后退到上一個城市。 當小 Y回到起點時，她可以選擇結束這次旅行或
繼續旅行。 需要注意的是，小 Y要求在旅行方案中，每個城市都被訪問到。
為了讓自己的旅行更有意義，小 Y決定在每到達一個新的城市（包括起點）時，將
它的編號記錄下來。她知道這樣會形成一個長度為 ???? 的序列。她希望這個序列的字典序
最小，你能幫幫她嗎？
對于兩個長度均為 ???? 的序列 A和 B，當且僅當存在一個正整數 x， 滿足以下條件時，
我們說序列 A的字典序小于 B。
? 對于任意正整數 1 ≤ i < x，序列 A的第 i 個元素 Ai 和序列 B的第 i 個元素
Bi 相同。
? 序列 A的第 x 個元素的值小于序列 B的第 x 個元素的值。

【輸入格式】
輸入文件名為 travel.in。
輸入文件共 ????+1 行。 第一行 包含 兩個整數 ????,????(???? ≤ ????) ， 中 間用一個空格分隔 。
接下來 ???? 行，每行 包含 兩個整數 ????,???? (1 ≤ ????,???? ≤ ????) ，表示編號為 ???? 和 ???? 的城市之
間有一條道路 ， 兩個整數之間用一個空格分隔 。
【輸出格式】
輸出文件名為 travel.out。
輸出文件包含 一行， ???? 個整數，表示字典序最小的序列。相鄰兩個整數之間用一個
空格分隔。

【輸入輸出樣例 1】
travel.in travel.out
6 5 1 3 2 5 4 6
1 3
2 3
2 5
3 4
4 6

見選手目錄下的 travel/travel1.in和 travel/travel1.ans。
第 2頁共 8頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 提高組 day2

【輸入輸出樣例 2】
travel.in travel.out
6 6 1 3 2 4 5 6
1 3
2 3
2 5
3 4
4 5
4 6

見選手目錄下的 travel/travel2.in和 travel/travel2.ans。

【輸入輸出樣例 3】
見選手目錄下的 travel/travel3.in和 travel/travel3.ans。
這組樣例滿足 ???? = ?????1 。

【輸入輸出樣例 4】
見選手目錄下的 travel/travel4.in和 travel/travel4.ans。
這組樣例滿足 ???? = ???? 。


【 數據規模與約定 】
對于 100% 的數據 和所有樣例 ， 1 ≤ ???? ≤ 5000 且 ???? = ?????1 或 ???? = ???? 。
對于不同的測試點， 我們 約定數據的 規模如下：
測試點 編 號 ???? = ???? = 特殊性質
1,2,3 10 無
4,5 100 無
6,7,8 1000 每個城市最多與兩個城市相連
?????1
9,10 1000 無
11,12,13 5000 每個城市最多與三個城市相連
14,15 5000 無
16,17 10 無
18,19 100 無
????
20,21,22 1000 每個城市最多與兩個城市相連
23,24,25 5000 無

第 3頁共 8頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 提高組 day2
2. 填數游戲
(game.cpp/c/pas)
【問題描述】
小 D特別喜歡玩游戲 。 這一天 ， 他 在玩 一款填數游戲。
這個填數 游戲 的棋盤是 一個 n×m的矩形表格 。玩家 需要在表格的每個格子 中 填 入
一個數字（數字 0或者 數字 1），填數時需要 滿足一些限制 。
下面我們來具體描述這些限制。
為了方便描述，我們先給出一些定義 ：
? 我們用每個格子的行列坐標來表示一個格子，即（行坐標，列坐標） 。（注意：
行列坐標均從 0開始編號）
? 合法路徑 P： 一條路徑是合法的當且僅當 ：
1. 這條路徑從矩形 表格 的左上角 的格子 (0,0)出發，到矩形的右下角 格子
(n?1,m?1)結束 ；
2. 在這條路徑中， 每次只能 從 當前的格子 移動到右邊與它相鄰的格子 ， 或者
從當前格子 移動到下面與它相鄰的格子 。
例如 ： 在下面這個矩形中，只有兩條路徑是合法的，它們 分別 是 ????1： (0,0)→ (0,1)→
(1,1)和 ????2： (0,0)→(1,0)→(1,1)。

對于一條合法的路徑 P，我們 可以 用一個字符串 w(P)來表示 ，該字符串的長度為 n+
m?2，其中只包含字符“ R”或者字符“ D”， 第 i個字符記錄了路徑 P中第 i步的 移動
方法 ，“ R” 表示 移動 到 當前格子右邊 與它相鄰 的格子 ，“ D”表示 移動到當前格子 下面
與它相鄰 的格子 。例如， 上圖中 對于路徑 ????1，有 w(P1)= "RD"；而對于另一條路徑 ????2，
有 w(P2)= "DR"。
同時 ， 將 每條合法路徑 P經過的每個格子上 填入 的數字依次連接后， 會 得到一個 長
度為 n+m?1的 01字符串 ，記為 s(P)。 例 如，如果我們在 格子 (0,0)和 (1,0)上填 入數字
0，在 格子 (0,1)和 (1,1)上填 入數字 1（見 上 圖紅色數字）。 那么對于 路徑 ????1， 我們可以 得
到 s(P1)= "011",對于 路徑 ????2，有 s(P2)= "001"。

游戲要求小 D找到 一種 填 數字 0、 1的方法，使得對于兩條路徑 ????1， P2， 如果 w(P1)>
w(P2)，那么必須 s(P1)≤ s(P2)。 我們說字符串 a比字符串 b小，當且僅當字符串 a的字
典序小于字符串 b的字典序 ，字典序的定義詳見第一題 。 但是僅僅是找一種方法無法滿
足小 D 的好奇心，小 D 更想知道這個游戲有多少種玩法，也就是說，有多少種填數字
的方法滿足游戲的要求？
第 4頁共 8頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 提高組 day2
小 D 能力有限，希望你幫助他解決這個問題 ，即 有多少種填 0、 1 的方法能滿足 題
目 要求 。 由于答案可能很大， 你需要 輸出 答案對 109+7取 模的結果 。

【輸入格式】
輸入文件名為 game.in。
輸入 文件共一行，包含 兩個正整數 n、 m， 由一個空格分隔， 表示矩形的大小。 其
中 n 表示 矩形 表格 的行數， m表示 矩形 表格 的列數。
【輸出格式】
輸出文件名為 game.out。
輸出 共一行，包含 一個正整數，表示有多少種填 0、 1 的方法能滿足游戲的要求 。
注意： 輸出答案對 109+7取模的結果。
【輸入輸出樣例 1】
game.in game.out
2 2 12

見選手目錄下的 game/game1.in和 game/game1.ans。
【樣例解釋】
對于 2×2棋盤，有上圖 所 示的 12種填數方法滿足要求。
【輸入輸出樣例 2】
game.in game.out
3 3 112

見選手目錄下的 game/game2.in和 game/game2.ans。 。
【輸入輸出樣例 3】
game.in game.out
5 5 7136

見選手目錄下的 game/game3.in和 game/game3.ans。
第 5頁共 8頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 提高組 day2
【 數據規模與約定 】

測試點編號 n≤ m≤
1~4 3 3
5~10 2 1000000
11~13 3 1000000
14~16 8 8
17~20 8 1000000




第 6頁共 8頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 提高組 day2
3． 保衛王國
(defense.cpp/c/pas)
【問題描述】
Z 國有 n座城市， n?1條雙向道路，每條雙向道路連接兩座城市，且任意兩座城市
都能通過若干條道路相互到達。
Z國的國防部長小 Z要在 城市中駐扎軍隊 。 駐扎軍隊需要滿足如下 幾個條件：
? 一座城市可以駐扎一支軍隊，也可以不駐扎軍隊。
? 由道路直接連接的兩座城市中至少要有一座城市駐扎軍隊。
? 在城市里駐扎軍隊會產生花費，在編號為 i的城市中駐扎軍隊的花費是 pi。
小 Z很快就規劃出了一種駐扎軍隊的方案，使總花費最小。但是國王又給小 Z提出
了 m個要求，每個要求規定了 其中兩座 城市 是否駐扎軍隊 。 小 Z需要 針對每個要求 逐一
給出 回答 。具體而言 ，如果 國王 提出的 第 j個要求 能夠 滿足 上述 駐扎 條件 （不需要 考慮
第 j 個要求之外的 其它要求） ， 則 需要給出在此要求前提下 駐扎軍隊的最小開銷。 如果
國王提出的第 j個 要求無法滿足， 則 需要輸出 -1 (1 ≤ j ≤ m)。 現在請你來幫助小 Z。
【輸入 格式 】
輸入文件名為 defense.in。
第 1行包含 兩 個正整數 ????,????和一個字符串 ????????????????， 分別 表示城市數、 要求數 和數據類
型 。 ????????????????是 一個 由 大寫字母 A， B或 C和一個數字 1， 2， 3組成的字符串。它可以幫助
你獲得部分分。你可能不需要用到這個參數。這個參數的含義在 【 數據規模與約定 】 中
有具體的描述。
第 2行 n個整數 pi，表示 編號 i的城市中駐扎軍隊的花費。
接下來 n?1行，每行兩個正整數 u,v，表示有一條 u到 v的雙向道路。
接下來 m行，第 j行四個整數 a,x,b,y(a ≠ b)，表示第 j個要求是在城市 a駐扎 x支軍隊，
在城市 b駐扎 y支軍隊。 其中， x 、 y 的取值只有 0或 1： 若 x為 0，表示城市 a不得駐
扎軍隊，若 x 為 1，表示城市 a 必須駐扎軍隊 ； 若 y 為 0，表示城市 b 不得駐扎軍隊，
若 y為 1，表示城市 b必須駐扎軍隊。
輸入文件中每一行 相鄰 的兩個數據之間均 用 一個空格分隔。
【輸出 格式 】
輸出文件名為 defense.out。
輸出共 m行， 每行 包含 1 個整數， 第 j行 表示 在滿足國王第 j個要求時的最小開銷，
如果無法滿足國王的第 j個要求，則 該行 輸出 -1。
【輸入輸出樣例 1】
defense.in defense.out
5 3 C3 12
2 4 1 3 9 7
1 5 -1
5 2
5 3
3 4
1 0 3 0
2 1 3 1
1 0 5 0

第 7頁共 8頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 提高組 day2
見選手目錄下的 defense/defense1.in和 defense/defense1.ans。
【樣例解釋】
對于第一個要求，在 4號和 5號城市駐扎軍隊時開銷最小。
對于第二個要求，在 1號、 2號、 3號城市駐扎軍隊時開銷最小。
第三個要求是無法滿足的 ，因為在 1號、 5號城市都不駐扎軍隊就意味著 由道路直接連
接的兩座城市中都沒有 駐扎軍隊 。

【輸入輸出樣例 2】
見選手目錄下的 defense/defense2.in和 defense/defense2.ans。


【數據規模與約定】
對于 100%的數據， n,m ≤ 300000,1≤ pi ≤ 100000。
測試點 編 號 type ???? = ???? =
1~2 A3 10 10
3~4 C3
5~6 A3 100 100
7 C3
8~9 A3 2000 2000
10~11 C3
12~13 A1 100000 100000
14~16 A2
17 A3
18~19 B1
20~21 C1
22 C2
23~25 C3

數據類型的含義：
A： 城市 i與城市 i+1直接相連。
B：任意城市與城市 1的距離不超過 100（距離定義為最短路徑上邊的數量），即如果這
棵樹以 1號城市為根，深度不超過 100。
C：在樹的形態上無特殊約束。
1：詢問時保證 a = 1,x = 1，即要求在城市 1駐軍。對 b,y沒有限制。
2：詢問時保證 a,b是相鄰的（由一條道路直接連通）
3：在詢問上無特殊約束。
第 8頁共 8頁

展開更多......

收起↑