資源簡介

全國信息學奧林匹克聯賽（ NOIP2018）復賽 普及組
CCF 全國信息學奧林匹克聯賽 （ NOIP2018） 復賽

普及組
（請選手務必仔細閱讀本頁內容）

一．題目概況
中文題目名稱 標題統計 龍虎斗 擺渡車 對稱二叉樹
英文題目與子目錄名 title fight bus tree
可執行文件名 title fight bus tree
輸入文件名 title.in fight.in bus.in tree.in
輸出文件名 title.out fight.out bus.out tree.out
每個測試點時限 1秒 1秒 2秒 1秒
測試點數目 20 25 20 25
每個測試點分值 5 4 5 4
附加樣例文件 有 有 有 有
結果比較方式 全文比較 （ 過濾行末空格及文末回車 ）
題目類型 傳統 傳統 傳統 傳統
運行 內存上限 256M 256M 256M 256M

二．提交源程序文件名
對于 C++語言 title.cpp fight.cpp bus.cpp tree.cpp
對于 C語言 title.c fight.c bus.c tree.c
對于 pascal語言 title.pas fight.pas bus.pas tree.pas

三．編譯命令（不包含任何優化開關）
對于 C++語言 g++ -o title g++ -o fight g++ -o bus g++ -o tree
title.cpp -lm fight.cpp -lm bus.cpp -lm tree.cpp -lm
對于 C語言 gcc -o title title.c gcc -o fight fight.c gcc -o bus gcc -o tree tree.c
-lm -lm bus.c -lm -lm
對于 pascal語言 fpc title.pas fpc fight.pas fpc bus.pas fpc tree.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頁共 9頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 普及組
1. 標題統計
(title.cpp/c/pas)
【問題描述】
凱凱 剛 寫了一篇 美妙 的 作文 ，請問這篇作文的標題中有 多少 個字符？
注意：標題中 可能包含大、小寫英文字母、數字字符 、 空格 和換行符 。統計標題字
符數時，空格 和換行符 不計 算在內 。

【輸入 格式 】
輸入文件名為 title.in。
輸入文件只有 一 行， 一個字符串 s。

【輸出 格式 】
輸出文件名為 title.out。
輸出文件只有 一 行，包含一個 整數，即 作文標題的字符數 （不含空格 和換行符 ） 。

【輸入輸出樣例 1】
title.in title.out
234 3

見選手目錄下的 title/title1.in和 title/title1.ans。
【 輸入輸出樣例 1說明 】
標題中共有 3個 字符，這 3個字符都是 數字 字符 。

【輸入輸出樣例 2】
title.in title.out
Ca 45 4

見選手目錄下的 title/title2.in和 title/title2.ans。
【 輸入輸出樣例 2說明 】
標題中共有 5個字符， 包括 1個大寫英文字母， 1個小寫英文字母 和 2個數字字符 ，
還有 1個空格 。由于空格 不計入結果中 ，故標題的 有效 字符數為 4個 。

【數據規模與約定 】
規定 |s| 表示字符串 s 的長度（即 字符串中的 字符 和空格 數）。
對于 40% 的數據 ， 1 ≤|s| ≤5，保證輸入為數字字符 及行末換行符 。
對于 80% 的數據， 1 ≤|s| ≤5，輸入 只 可能 包含 大、小寫英文字母 、 數字字符 及
行末換行符 。
對于 100% 的數據， 1 ≤ |s|≤ 5，輸入可能包含大 、小 寫英文字母 、 數字字符 、 空
格 和行末換行符 。


第 2頁共 9頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 普及組
2. 龍虎斗
(fight.cpp/c/pas)
【問題描述】
軒軒和凱凱正在玩一款叫《龍虎斗》的游戲， 游戲的 棋盤 是一條線段， 線段上有 ????
個兵營（自左至右編號 1 ~ ????） ， 相鄰編號的兵營之間相隔 1 厘米 ， 即 棋盤為 長度為
?????1 厘米 的線段 。 ???? 號兵營里有 c???? 位工兵 。
下面 圖 1為 ???? = 6 的 示 例：
圖 1. ???? =6的 示例
軒軒在左側，代表“龍”；凱凱在右側，代表“虎”。 他們以 m 號兵營作為分界，
靠左的工兵屬于龍勢力，靠右的工兵屬于虎勢力 ，而 第 ???? 號兵營中的工兵很糾結，他
們不屬于任何一方 。
一個兵營的氣勢為：該兵營中的工兵數 × 該兵營到 m 號兵營的距離 ；參與游戲
一方的勢力定義為：屬于這一方所有兵營的氣勢之和。
下 面 圖 2為 n= 6,???? =4 的 示 例 ，其中 紅色為龍方 ， 黃色為虎方 ：
圖 2. n = 6,???? = 4的示例
游戲過程中，某一刻 天降神兵， 共有 ????1 位工兵突然出現 在了 ????1 號 兵營 。 作為 軒
軒和凱凱的朋友， 你知道如果龍虎雙方氣勢差距太懸殊，軒軒和凱凱就不愿意繼續玩下
去了。 為了讓游戲繼續， 你需要選擇一個兵營 ????2， 并 將 你 手里的 ????2 位 工兵 全部 派 往
兵營 ????2，使得雙方氣勢差距盡可能小。
注意： 你手中的 工兵落在哪個兵營，就和 該兵營中 其他工兵有相同的勢力歸屬（如
果落在 m 號兵營，則不屬于任何勢力 ）。

【輸入格式】
輸入文件名為 fight.in。
輸入文件的第一行包含一 個正整數 ????，代表 兵營 的數量 。
接下來 的 一 行 包含 ???? 個正整數， 相鄰兩數之間 以 一個 空格 分隔 ， 第 ???? 個正整數代
表 編號為 ???? 的 兵營中起始時的工兵數量 ????????。
接下來 的 一行 包含 四個正整數， 相鄰兩數間 以 一個 空格 分隔 ，分別代表 ????,????1,????1,????2。
【輸出格式】
輸出文件名為 fight.out。
輸出文件有 一 行， 包含 一 個 正 整數， 即 ????2，表示 你選擇的 兵營 編號。 如果存在多
個編號 同時滿足最優，取 最 小的編號。

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

第 3頁共 9頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 普及組
見選手目錄下的 fight/fight1.in和 fight/fight1.ans。
【輸入輸出樣例 1說明】
見 問 題 描述 中 的 圖 2。
雙方以 ???? =4 號兵營 分界 ， 有 ????1 = 5 位工兵突然出現在 ????1 = 6 號兵營。
龍方的氣勢 為：
2×(4?1)+3×(4?2)+2×(4?3) = 14
虎方的氣勢 為：
2×(5?4)+(3+5)×(6?4) =18
當 你將手中的 ????2 = 2 位工兵派往 ????2 =2 號兵營 時， 龍方的氣勢 變為：
14+2×(4?2) =18
此時 雙方氣勢 相等 。

【輸入輸出樣例 2】
fight.in fight.out
6 1
1 1 1 1 1 16
5 4 1 1

見選手目錄下的 fight/fight2.in和 fight/fight2.ans。
【輸入輸出樣例 2說明】
雙方以 ???? =5 號兵營分界，有 ????1 = 1 位工兵突然出現在 ????1 = 4 號兵營。
龍方的氣勢為 ：
1×(5?1)+1×(5?2)+1×(5?3)+(1+1)×(5?4) = 11
虎方的氣勢為 ：
16×(6?5) =16
當你將手中的 ????2 = 1 位工兵派往 ????2 =1 號兵營時，龍方的氣勢變為：
11+1×(5?1) =15
此時 可以使 雙方氣勢的差距 最小。

【輸入輸出樣例 3】
見選手目錄下的 fight/fight3.in和 fight/fight3.ans。

【數據規模與約定】
1 對于 20% 的數據， ???? =3, ???? =2, ???????? =1, ????1,????2 ≤ 100。
另有 20% 的數據， ???? ≤10, ????1 = ????, ???????? = 1, ????1,????2 ≤ 100。
對于 60% 的數據， ???? ≤100, ???????? = 1, ????1,????2 ≤ 100。
對于 80% 的數據， ???? ≤100, ????????,????1,????2 ≤100。
對于 100% 的數據， ???? ≤ 105, ????????,???? 9
1,????2 ≤ 10 。

第 4頁共 9頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 普及組
3. 擺渡車
(bus.cpp/c/pas)
【問題描述】
有 ???? 名同學要乘坐擺渡車從人大附中前往 人民大學 ， 第 ???? 位同學在第 ???????? 分鐘去
等車 。 只有一輛擺渡車在工作 ，但擺渡車容量可以視為無限大 。 擺渡車從人大附中出發、
把 車上的 同學送到人民大學、再回到人大附中 （ 去接其他同學 ），這樣往返一趟 總共花
費 ???? 分鐘 （同學上下車時間忽略不計）。 擺渡車要將所有同學都送到人民大學 。
凱凱很好奇，如果 他能任意安排 擺渡車出發的時間， 那么 這些同學的等車時間之和
最小為多少呢 ？
注意：擺渡車回到人大附中后可以即刻出發。

【輸入 格式 】
輸入文件名為 bus.in。
第一行包含兩個正整數 ????， m，以一個空格分開，分別代表 等車人數和擺渡車往返
一趟的時間。
第二行 包含 ???? 個正整數， 相鄰兩數之間 以 一個 空格分隔， 第 i 個 非負 整數 ???????? 代
表 第 i 個同學到達車站的時刻。

【輸出 格式 】
輸出文件名為 bus.out。
輸出 一行，一個整數，表示 所有同學等車 時間 之和的最小值 （ 單位： 分鐘） 。

【輸入輸出樣例 1】
bus.in bus.out
5 1 0
3 4 4 3 5

見選手目錄下的 bus/bus1.in和 bus/bus1.ans。
【輸入輸出樣例 1說明】
同學 1 和同學 4 在第 3 分鐘開始等車， 等待 0 分鐘， 在第 3 分鐘 乘坐擺渡車
出發。 擺渡車 在 第 4 分鐘回到 人大附中 。
同學 2 和同學 3 在第 4 分鐘開始等車，等待 0 分鐘，在第 4 分鐘乘坐擺渡車
出發。擺渡車在第 5 分鐘回到人大附中。
同學 5 在第 5 分鐘開始等車，等待 0 分鐘，在第 5 分鐘乘坐擺渡車出發。 自此
所有同學 都被送到人民大學 。總等待時間為 0。

【輸入輸出樣例 2】
bus.in bus.out
5 5 4
11 13 1 5 5

見選手目錄下的 bus/bus2.in和 bus/bus2.ans。

第 5頁共 9頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 普及組

【輸入輸出樣例 2說明】
同學 3 在第 1 分鐘開始等車，等待 0 分鐘 ， 在第 1 分鐘乘坐擺渡車出發。擺渡
車在第 6 分鐘回到人大附中。
同學 4 和同學 5 在第 5 分鐘開始等車，等待 1 分鐘 ， 在第 6 分鐘乘坐擺渡車
出發。擺渡車在第 11 分鐘回到人大附中。
同學 1 在第 11 分鐘開始等車，等待 2 分鐘；同學 2 在第 13 分鐘開始等車，
等待 0 分鐘。他 /她們在第 13 分鐘乘坐擺渡車出發。 自此所有同學都被送到人民大學。
總等待時間為 4。可以證明，沒有總等待時間小于 4 的 方案。

【輸入輸出樣例 3】
見選手目錄下的 bus/bus3.in和 bus/bus3.ans。

【數據規模與約定】
對于 10% 的數據， ???? ≤10, ???? =1, 0≤ ???????? ≤100。
對于 30% 的數據， ???? ≤20, ???? ≤ 2, 0 ≤???????? ≤100。
對于 50% 的數據， ???? ≤500, ???? ≤100, 0 ≤???????? ≤ 104。
另有 20% 的數據， ???? ≤500, ???? ≤10, 0≤ ???? 6
???? ≤4×10 。
對于 100% 的數據， ???? ≤ 500, ???? ≤100, 0≤ ???? 6
???? ≤4×10 。


第 6頁共 9頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 普及組
4. 對稱二叉樹
(tree.cpp/c/pas)
【問題描述】
一棵 有點權的 有根 樹 如果 滿足以下條件，則被 軒軒 稱為 對稱二叉樹 ：
1. 二叉樹 ；
2. 將這 棵樹 所有 節點的左右 子樹交換，新樹和原樹對應位置的 結構相同且 點權相
等。

下圖 中節點內的數字為權值，節點外的 ???????? 表示節點 編號 。

對稱二叉樹 非對稱二叉樹 非對稱二叉樹
（ 權值不對稱 ） （ 結構不對稱 ）
原樹

所有節
點的左
右子樹
交換 后


現在給出一棵 二叉樹，希望你 找 出它的一棵子樹 ， 該子樹為對稱二叉樹 ， 且節點數
最多 。 請 輸出這棵 子樹的 節點數。
注意：只有樹根的樹也是對稱二叉樹。 本題中 約定， 以 節點 ???? 為 子樹 根 的 一 棵 “子
樹”指 的是 ： 節點 ???? 和它 的 全部 后代節點 構成的二叉樹 。


【輸入格式】
輸入文件名為 tree.in。
第一行一 個正整數 ????， 表示 給 定 的樹的節點的 數目 ， 規定節點編號 1~n，其中 節點
1 是樹根 。
第二行 ???? 個正整數， 用 一個 空格分隔， 第 ???? 個正整數 ???????? 代表節點 ???? 的權值 。
接下來 ???? 行，每行兩個正整數 ????????, ????????，分別表示 節點 ???? 的 左右孩子的 編 號 。 如果
不存在左 / 右孩子，則 以 ?1 表示 。 兩個數之間用一個空格隔開。

【輸出格式】
輸出文件名為 tree.out。
輸出文件 共一行， 包含 一個整數，表示 給定的樹的最大 對稱 二叉子樹的節點數。

第 7頁共 9頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 普及組
【輸入輸出樣例 1】
tree.in tree.out
2 1
1 3
2 -1
-1 -1

見選手目錄下的 tree/tree1.in和 tree/tree1.ans。

【輸入輸出樣例 1說明】

最大的對稱二叉子樹為 以節點 2 為樹根的子樹，節點數為 1。

【輸入輸出樣例 2】
tree.in tree.out
10 3
2 2 5 5 5 5 4 4 2 3
9 10
-1 -1
-1 -1
-1 -1
-1 -1
-1 2
3 4
5 6
-1 -1
7 8

見選手目錄下的 tree/tree2.in和 tree/tree2.ans。

【輸入輸出樣例 2說明】

第 8頁共 9頁

全國信息學奧林匹克聯賽（ NOIP2018）復賽 普及組
最大的對稱二叉子樹為以節點 7 為樹根的子樹，節點數為 3。
【輸入輸出樣例 3】
見選手 目錄下的 tree/tree3.in和 tree/tree3.ans。

【數據規模與約定】
共 25 個測試點。
???????? ≤ 1000。
測試點 1~3， ???? ≤ 10， 保證 根結點的左子樹的所有節點都沒有右 孩子，根結點的右
子樹的所有節點 都沒有左 孩子。
測試點 4~8， ???? ≤ 10。
測試點 9~12， ???? ≤105， 保證輸入是一棵 “ 滿二叉樹 ” 。
測試點 13~16， ???? ≤ 105， 保證輸入 是一棵 “ 完全二叉樹 ” 。
測試點 17~20， ???? ≤ 105， 保證輸入的樹的 點權 均 為 1。
測試點 21~25， ???? ≤ 106。

本題約定：
層次 ： 節點的層次從根開始定義起，根為第一層，根的孩子為第二層。樹中任一節
點的層次等于其 父親 節點的層次加 1。

樹的深度： 樹中節點的最大層次稱為樹的深度。

滿二叉樹： 設二叉樹的深度為 ?，且二叉樹有 2? ?1 個節點，這就是滿二叉樹。


滿二叉樹 （深度為 3）

完全二叉樹： 設二叉樹的深度為 ?，除第 ? 層外，其它各層的結點數都達到最大
個數，第 ? 層所有的結點都連續集中在最左邊，這就是完全二叉樹。


完全二叉樹 （深度為 3） 完全二叉樹 （深度為 3）
第 9頁共 9頁

展開更多......

收起↑