2019年11月16日~17日CSP非專業級別第二輪能力認證結束，全國30個省市共計29165人報名參加！此次認證分為初級組(CSP-J)和高級組(CSP-S)。

重點考察學生對問題的分析理解能力、數學抽象能力、駕馭編程語言的能力、編程技巧、想象力和創造力等。

參賽的小伙伴們，測評結束了，分數評估了嗎？趁著現在記憶仍在，趕緊對著答案來看看吧！童程童美NOI教研部門第一時間為廣大學員整理了2019 CSP-J 第二輪認證試題解析，以供參考。

2019CCF非專業級別軟件能力認證

第二輪

2019 CSP-J 入門級第二輪認證真題解析

數字游戲(number)

輸入文件名：number.in

輸出文件名：number.out

共 20 個測試點，每個測試點 5 分

每個測試點限時 1 秒，運行內存上限 256MB

問題描述

小 K 同學向小 P 同學發送了一個長度為 8 的 01 字符串 來玩數字游戲，小 P 同學想要知道字符串中究竟有多少個 1。

注意：01 字符串為每一個字符是 0 或者 1 的字符串，如“101”(不含雙引號)為一個長度為 3的 01 字符串。

輸入格式

輸入文件名為 number.in。

輸入文件只有一行，一個長度為 8 的 01 字符串 s。

輸出格式

輸出文件名為 number.out。

輸出文件只有一行，包含一個整數，即 01 字符串中字符 1 的個數。

樣例 1 輸入

00010100

樣例 1 輸出

2

樣例 1 解釋

該 01 字符串中有 2 個字符 1。

樣例 2 輸入

11111111

樣例 2 輸出

8

樣例 2 解釋

該 01 字符串中有 8 個字符 1。

樣例 3 輸入

01010101

樣例 3 輸出

4

數據范圍

對于 20% 的數據，保證輸入的字符全部為0。

對于 100% 的數據，輸入只可能包含字符 0 和字符 1，字符串長度固定為 8。

答案及思路分析：

解析：這道題考察字符串的操作、循環結構、分支結構等知識點。輸入字符串，注意看題的最后，總長度是8.遍歷字符串中每一個字符，如果字符為1則計數變量加一，最后輸出計算變量的值。

公交換乘(transfer)

輸入文件名：transfer.in

輸出文件名：transfer.out

共 20 個測試點，每個測試點 5 分

每個測試點限時 1 秒，運行內存上限 256MB

問題描述

著名旅游城市 B 市為了鼓勵大家采用公共交通方式出行，推出了一種地鐵換乘公交車的優惠方案：

在搭乘一次地鐵后可以獲得一張優惠票，有效期為 45 分鐘，在有效期內可以消耗這張優惠票，免費搭乘一次票價不超過地鐵票價的公交車。在有效期內指開始乘公交車的時間與開始乘地鐵的時間之差小于等于 45 分鐘，即

搭乘地鐵獲得的優惠票可以累積，即可以連續搭乘若干次地鐵后再連續使用優惠票搭乘公交車。

搭乘公交車時，如果可以使用優惠票一定會使用優惠票;如果有多張優惠票滿足條件，則優先消耗獲得最早的優惠票。

現在你得到了小軒最近的公共交通出行記錄，你能幫他算算他的花費嗎？

輸入格式

輸入文件名為 transfer.in。

輸入文件的第一行包含一個正整數 n，代表乘車記錄的數量。

接下來的 n 行，每行包含 3 個整數，相鄰兩數之間以一個空格分隔。第 i 行的第 1 個整數代表第 i 條記錄乘坐的交通工具，0代表地鐵，1代表公交車；第 2 個整數代表第 i條記錄乘車的票價

第三個整數代表第 i 條記錄開始乘車的時間

(距 0 時刻的分鐘數)。

我們保證出行記錄是按照開始乘車的時間順序給出的，且不會有兩次乘車記錄出現在同一分鐘。

輸出格式

輸出文件名為 transfer.out。

輸出文件有一行，包含一個正整數，代表小軒出行的總花費。

樣例 1 輸入

6

0 10 3

1 5 46

0 12 50

1 3 96

0 5 110

1 6 135

樣例 1 輸出

36

樣例 1 解釋

第一條記錄，在第 3 分鐘花費 10 元乘坐地鐵。

第二條記錄，在第 46 分鐘乘坐公交車，可以使用第一條記錄中乘坐地鐵獲得的優惠票，因此沒有花費。

第三條記錄，在第 50 分種花費 12 元乘坐地鐵。

第四條記錄，在第 96 分鐘乘坐公交車，由于距離第三條記錄中乘坐地鐵已超過 45 分鐘，所以優惠票已失效，花費 3 元乘坐公交車。

第五條記錄，在第 110 分鐘花費 5 元乘坐地鐵。

第六條記錄，在第 135 分鐘乘坐公交車，由于此時手中只有第五條記錄中乘坐地鐵獲得的優惠票有效，而本次公交車的票價為 6 元，高于第五條記錄中地鐵的票價 5 元， 所以不能使用優惠票，花費 6 元乘坐公交車。

總共花費 36 元。

樣例 2 輸入

6

0 5 1

0 20 16

0 7 23

1 18 31

1 4 38

1 7 68

樣例 2 輸出

32

樣例 2 解釋

第一條記錄，在第 1 分鐘花費 5 元乘坐地鐵。

第二條記錄，在第 16 分鐘花費 20元乘坐地鐵。

第三條記錄，在第 23 分鐘花費 7元乘坐地鐵。

第四條記錄，在第 31 分鐘乘坐公交車，此時只有第二條記錄中乘坐的地鐵票價高于本次公交車票價，所以使用第二條記錄中乘坐地鐵獲得的優惠票。

第五條記錄，在第 38 分鐘乘坐公交車，此時第一條和第三條記錄中乘坐地鐵獲得的優惠票都可以使用，使用獲得最早的優惠票，即第一條記錄中乘坐地鐵獲得的優惠票。

第六條記錄，在第 68 分鐘乘坐公交車，使用第三條記錄中乘坐地鐵獲得的優惠票。

總共花費 32 元。

答案及思路分析：

/*

解析：和2016年海港有些像，模擬題。

車票有2中，如果是地鐵票，必須要花錢。如果是公交車票，就不一定了。

如果45分鐘內，有做過的地鐵票，并且費用大于等于公交車的，就免費；

否則要花費。

*/

紀念品(souvenir)

輸入文件名：souvenir.in

輸出文件名：souvenir.out

共 20 個測試點，每個測試點 5 分

每個測試點限時 1 秒，運行內存上限 256MB

問題描述

小偉突然獲得一種超能力，他知道未來 T 天 N 種紀念品每天的價格。某個紀念品的價格是指購買一個該紀念品所需的金幣數量，以及賣出一個該紀念品換回的金幣數量。

每天，小偉可以進行以下兩種交易 無限次:

1. 任選一個紀念品，若手上有足夠金幣，以當日價格購買該紀念品；

2. 賣出持有的任意一個紀念品，以當日價格換回金幣。

每天賣出紀念品換回的金幣可以立即用于購買紀念品，當日購買的紀念品也可以當日賣出換回金幣。當然，一直持有紀念品也是可以的。

T 天之后，小偉的超能力消失。因此他一定會在第 TT 天賣出所有紀念品換回金幣。

小偉現在有 M 枚金幣，他想要在超能力消失后擁有盡可能多的金幣。

輸入格式

輸入文件名為 souvenir.in。

第一行包含三個正整數 T,N,MT,N,M，相鄰兩數之間以一個空格分開，分別代表未來天數 TT，紀念品數量 NN，小偉現在擁有的金幣數量 MM。

接下來 TT 行，每行包含 NN 個正整數，相鄰兩數之間以一個空格分隔。第 ii 行的 NN 個正整數分別為 P_{i,1}, P_{i,2}, \ldots \ldots ,P_{i,N}Pi,1,Pi,2,……,Pi,N，其中 P_{i,j}Pi,j 表示第 ii 天第 jj 種紀念品的價格。

輸出格式

輸出文件名為 souvenir.out。

輸出僅一行，包含一個正整數，表示小偉在超能力消失后最多能擁有的金幣數量。

輸入樣例 1

6 1 100

50

20

25

20

25

50

輸出樣例 1

305

輸入輸出樣例 1 說明

最佳策略是：

第二天花光所有 100100 枚金幣買入 55 個紀念品 1；

第三天賣出 55 個紀念品 1，獲得金幣 125125 枚；

第四天買入 66 個紀念品 1，剩余 55 枚金幣；

第六天必須賣出所有紀念品換回 300300 枚金幣，第四天剩余 55 枚金幣，共 305305 枚金幣。

超能力消失后，小偉最多擁有 305305 枚金幣。

輸入樣例 2

3 3 100

10 20 15

15 17 13

15 25 16

輸出樣例 2

217

輸入輸出樣例 2 說明

最佳策略是：

第一天花光所有金幣買入 1010 個紀念品 1;

第二天賣出全部紀念品 1 得到 150150 枚金幣并買入 88 個紀念品 2 和 11 個紀念品 3，剩余 11 枚金幣;

第三天必須賣出所有紀念品換回 216216 枚金幣，第二天剩余 11 枚金幣，共 217217 枚金幣。

超能力消失后，小偉最多擁有 217217 枚金幣。

答案及思路分析：

解析：如果只有1天的話，買了再賣，總共剩下M個金幣。

T天N種紀念幣，根據題目設定范圍，100以內，可以用二維表格推導。

時間不可逆，只能1~N。

每天買哪些紀念品呢?根據測試樣例分析，紀念品任意多，沒有個數限制。根據金幣的上限，可以推到出這個就是完全背包。大家可以套一下完全背包的算法。每天需要做一次完全背包處理，當天不想賣出金幣，相當于賣出金幣再買入金幣。

參考答案：

加工零件(work)

輸入文件名：work.in

輸出文件名：work.out

共 20 個測試點，每個測試點 5 分

每個測試點限時 1 秒，運行內存上限 256MB

問題描述

凱凱的工廠正在有條不紊地生產一種神奇的零件，神奇的零件的生產過程自然也很神奇。工廠里有 n 位工人，工人們從 1 ~ 編號，某些工人之間存在雙向的零件傳送帶。保證每兩名工人之間最多只存在一條傳送帶。

如果 x號工人想生產一個被加工到第 L(L > 1)階段的零件，則所有與 x 號工人有傳送帶直接相連的工人，都需要生產一個被加工到第 L-1階段的零件(但 x 號工人自己無需生產第 L?1 階段的零件)。

如果 x號工人想生產一個被加工到第 1 階段的零件，則所有與 x 號工人有傳送帶直接相連的工人，都需要為 x 號工人提供一個原材料。

軒軒是 1 號工人。現在給出 q 張工單，第 i 張工單表示編號為ai的工人想生產一個第 Li 階段的零件。軒軒想知道對于每張工單，他是否需要給別人提供原材料。他知道聰明的你一定可以幫他計算出來！

輸入格式

輸入文件名為 work.in。

第一行三個正整數 n,m和 q，分別表示工人的數目、傳送帶的數目和工單的數目。

接下來 m 行，每行兩個正整數 u 和 v，表示編號為 u 和 v 的工人之間存在一條零件傳送帶。保證 u !=v。

接下來 q行，每行兩個正整數 a 和 L，表示編號為 a 的工人想生產一個第 L 階段的零件。

輸出格式

輸出文件名為 work.out。

共 q 行，每行一個字符串“Yes”或者“No”。如果按照第 i 張工單生產，需要編號為 1 的軒軒提供原材料，則在第 i 行輸出“Yes”;否則在第 i 行輸出“No”。注意輸出不含引號。

樣例 1 輸入

3 2 6

1 2

2 3

1 1

2 1

3 1

1 2

2 2

3 2

樣例 1 輸出

No

Yes

No

Yes

No

Yes

樣例 1 解釋

編號為 1 的工人想生產第 1 階段的零件，需要編號為 2 的工人提供原材料。

編號為 2 的工人想生產第 1 階段的零件，需要編號為 1 和 3 的工人提供原材料。

編號為 3 的工人想生產第 1 階段的零件，需要編號為 2 的工人提供原材料。

編號為 1 的工人想生產第 2 階段的零件，需要編號為 2 的工人生產第 1 階段的零件，需要為編號 1 和 3 的工人提供原材料。

編號為 2 的工人想生產第 2 階段的零件，需要編號為 1 和 3 的工人生產第 1 階段的零件，他/她們都需要編號為 2 的工人提供原材料。

編號為 3 的工人想生產第 2 階段的零件，需要編號為 2 的工人生產第 1 階段的零件，需要編號為 1 和 3 的工人提供原材料。

樣例 2 輸入

5 5 5

1 2

2 3

3 4

4 5

1 5

1 1

1 2

1 3

1 4

1 5

樣例 2 輸出

No

Yes

No

Yes

Yes

樣例 2 解釋

編號為 1 的工人想生產第 1 階段的零件，需要編號為 2 和 5 的工人提供原材料。

編號為 1 的工人想生產第 2 階段的零件，需要編號為 2 和 5 的工人生產第 1 階段的零件，需要編號為1,3,4 的工人提供原材料。

編號為 1 的工人想生產第 3 階段的零件，需要編號為 2 和 5 的工人生產第 2 階段的零件，需要編號為 1,3,4 的工人生產第 1 階段的零件，需要編號為 2,3,4,5 的工人提供 原材料。

編號為 1 的工人想生產第 4 階段的零件，需要編號為 2 和 5 的工人生產第 3 階段的零件，需要編號為 1,3,4 的工人生產第 2 階段的零件，需要編號為 2,3,4,5 的工人生產第 1 階段的零件，需要全部工人提供原材料。

編號為 1 的工人想生產第 5 階段的零件，需要編號為 2 和 5 的工人生產第 4 階段的零件，需要編號為 1,3,4的工人生產第 3 階段的零件，需要編號為 2,3,4,5的工人生產 第 2 階段的零件，需要全部工人生產第 1 階段的零件，需要全部工人提供原材料。

答案及思路分析：

解析：這道題考察圖論的知識運用，是屬于最短路徑的變形題目，可以利用spfa或Dijkstra來完成，難度較高。

根據性質，工人之間的關系是圖。相連接，之間的路徑權值是1。加工零件的過程可以相互傳遞，來回都是偶數次，因此在求個最短路時看奇偶步數內能否可達，要求與L的奇偶性一致。

參考答案：

以上是2019CSP-J(入門級)第二輪認證試題的解題分析，參加此次考試的學員們，你們都答對了嗎？另，關注童程童美微信公眾，在后臺回復【真題】即可免費領取“信息學奧賽歷年真題資料包”哦~

CSP-J/S是CCF創辦的CSP(軟件能力認證)中面向非專業級的軟件能力認證，也就是我們熟知的信息學奧賽，含金量高。

童程童美信息學奧賽課程是由專業教研團隊與北京知名學府聯合研發，課程內容循序漸進，指導學員圍繞每個考試階段的重點知識進行學習；教研團隊強大專業，授課老師經驗充足，確保準確把握科創活動方向和特點，保證學員學習進度和質量，助力學員在測評中取得優異成績！