2019年11月16日~17日CSP非專(zhuān)業(yè)級(jí)別第二輪能力認(rèn)證結(jié)束，全國(guó)30個(gè)省市共計(jì)29165人報(bào)名參加！此次認(rèn)證分為初級(jí)組(CSP-J)和高級(jí)組(CSP-S)。

重點(diǎn)考察學(xué)生對(duì)問(wèn)題的分析理解能力、數(shù)學(xué)抽象能力、駕馭編程語(yǔ)言的能力、編程技巧、想象力和創(chuàng)造力等。

參賽的小伙伴們，測(cè)評(píng)結(jié)束了，分?jǐn)?shù)評(píng)估了嗎？趁著現(xiàn)在記憶仍在，趕緊對(duì)著答案來(lái)看看吧！童程童美NOI教研部門(mén)第一時(shí)間為廣大學(xué)員整理了2019 CSP-J 第二輪認(rèn)證試題解析，以供參考。

2019CCF非專(zhuān)業(yè)級(jí)別軟件能力認(rèn)證

第二輪

2019 CSP-J 入門(mén)級(jí)第二輪認(rèn)證真題解析

數(shù)字游戲(number)

輸入文件名：number.in

輸出文件名：number.out

共 20 個(gè)測(cè)試點(diǎn)，每個(gè)測(cè)試點(diǎn) 5 分

每個(gè)測(cè)試點(diǎn)限時(shí) 1 秒，運(yùn)行內(nèi)存上限 256MB

問(wèn)題描述

小 K 同學(xué)向小 P 同學(xué)發(fā)送了一個(gè)長(zhǎng)度為 8 的 01 字符串 來(lái)玩數(shù)字游戲，小 P 同學(xué)想要知道字符串中究竟有多少個(gè) 1。

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

輸入格式

輸入文件名為 number.in。

輸入文件只有一行，一個(gè)長(zhǎng)度為 8 的 01 字符串 s。

輸出格式

輸出文件名為 number.out。

輸出文件只有一行，包含一個(gè)整數(shù)，即 01 字符串中字符 1 的個(gè)數(shù)。

樣例 1 輸入

00010100

樣例 1 輸出

2

樣例 1 解釋

該 01 字符串中有 2 個(gè)字符 1。

樣例 2 輸入

11111111

樣例 2 輸出

8

樣例 2 解釋

該 01 字符串中有 8 個(gè)字符 1。

樣例 3 輸入

01010101

樣例 3 輸出

4

數(shù)據(jù)范圍

對(duì)于 20% 的數(shù)據(jù)，保證輸入的字符全部為0。

對(duì)于 100% 的數(shù)據(jù)，輸入只可能包含字符 0 和字符 1，字符串長(zhǎng)度固定為 8。

答案及思路分析：

解析：這道題考察字符串的操作、循環(huán)結(jié)構(gòu)、分支結(jié)構(gòu)等知識(shí)點(diǎn)。輸入字符串，注意看題的最后，總長(zhǎng)度是8.遍歷字符串中每一個(gè)字符，如果字符為1則計(jì)數(shù)變量加一，最后輸出計(jì)算變量的值。

公交換乘(transfer)

輸入文件名：transfer.in

輸出文件名：transfer.out

共 20 個(gè)測(cè)試點(diǎn)，每個(gè)測(cè)試點(diǎn) 5 分

每個(gè)測(cè)試點(diǎn)限時(shí) 1 秒，運(yùn)行內(nèi)存上限 256MB

問(wèn)題描述

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

在搭乘一次地鐵后可以獲得一張優(yōu)惠票，有效期為 45 分鐘，在有效期內(nèi)可以消耗這張優(yōu)惠票，免費(fèi)搭乘一次票價(jià)不超過(guò)地鐵票價(jià)的公交車(chē)。在有效期內(nèi)指開(kāi)始乘公交車(chē)的時(shí)間與開(kāi)始乘地鐵的時(shí)間之差小于等于 45 分鐘，即

搭乘地鐵獲得的優(yōu)惠票可以累積，即可以連續(xù)搭乘若干次地鐵后再連續(xù)使用優(yōu)惠票搭乘公交車(chē)。

搭乘公交車(chē)時(shí)，如果可以使用優(yōu)惠票一定會(huì)使用優(yōu)惠票;如果有多張優(yōu)惠票滿(mǎn)足條件，則優(yōu)先消耗獲得最早的優(yōu)惠票。

現(xiàn)在你得到了小軒最近的公共交通出行記錄，你能幫他算算他的花費(fèi)嗎？

輸入格式

輸入文件名為 transfer.in。

輸入文件的第一行包含一個(gè)正整數(shù) n，代表乘車(chē)記錄的數(shù)量。

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

第三個(gè)整數(shù)代表第 i 條記錄開(kāi)始乘車(chē)的時(shí)間

(距 0 時(shí)刻的分鐘數(shù))。

我們保證出行記錄是按照開(kāi)始乘車(chē)的時(shí)間順序給出的，且不會(huì)有兩次乘車(chē)記錄出現(xiàn)在同一分鐘。

輸出格式

輸出文件名為 transfer.out。

輸出文件有一行，包含一個(gè)正整數(shù)，代表小軒出行的總花費(fèi)。

樣例 1 輸入

6

0 10 3

1 5 46

0 12 50

1 3 96

0 5 110

1 6 135

樣例 1 輸出

36

樣例 1 解釋

第一條記錄，在第 3 分鐘花費(fèi) 10 元乘坐地鐵。

第二條記錄，在第 46 分鐘乘坐公交車(chē)，可以使用第一條記錄中乘坐地鐵獲得的優(yōu)惠票，因此沒(méi)有花費(fèi)。

第三條記錄，在第 50 分種花費(fèi) 12 元乘坐地鐵。

第四條記錄，在第 96 分鐘乘坐公交車(chē)，由于距離第三條記錄中乘坐地鐵已超過(guò) 45 分鐘，所以?xún)?yōu)惠票已失效，花費(fèi) 3 元乘坐公交車(chē)。

第五條記錄，在第 110 分鐘花費(fèi) 5 元乘坐地鐵。

第六條記錄，在第 135 分鐘乘坐公交車(chē)，由于此時(shí)手中只有第五條記錄中乘坐地鐵獲得的優(yōu)惠票有效，而本次公交車(chē)的票價(jià)為 6 元，高于第五條記錄中地鐵的票價(jià) 5 元， 所以不能使用優(yōu)惠票，花費(fèi) 6 元乘坐公交車(chē)。

總共花費(fèi) 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 分鐘花費(fèi) 5 元乘坐地鐵。

第二條記錄，在第 16 分鐘花費(fèi) 20元乘坐地鐵。

第三條記錄，在第 23 分鐘花費(fèi) 7元乘坐地鐵。

第四條記錄，在第 31 分鐘乘坐公交車(chē)，此時(shí)只有第二條記錄中乘坐的地鐵票價(jià)高于本次公交車(chē)票價(jià)，所以使用第二條記錄中乘坐地鐵獲得的優(yōu)惠票。

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

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

總共花費(fèi) 32 元。

答案及思路分析：

/*

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

車(chē)票有2中，如果是地鐵票，必須要花錢(qián)。如果是公交車(chē)票，就不一定了。

如果45分鐘內(nèi)，有做過(guò)的地鐵票，并且費(fèi)用大于等于公交車(chē)的，就免費(fèi)；

否則要花費(fèi)。

*/

紀(jì)念品(souvenir)

輸入文件名：souvenir.in

輸出文件名：souvenir.out

共 20 個(gè)測(cè)試點(diǎn)，每個(gè)測(cè)試點(diǎn) 5 分

每個(gè)測(cè)試點(diǎn)限時(shí) 1 秒，運(yùn)行內(nèi)存上限 256MB

問(wèn)題描述

小偉突然獲得一種超能力，他知道未來(lái) T 天 N 種紀(jì)念品每天的價(jià)格。某個(gè)紀(jì)念品的價(jià)格是指購(gòu)買(mǎi)一個(gè)該紀(jì)念品所需的金幣數(shù)量，以及賣(mài)出一個(gè)該紀(jì)念品換回的金幣數(shù)量。

每天，小偉可以進(jìn)行以下兩種交易 無(wú)限次:

1. 任選一個(gè)紀(jì)念品，若手上有足夠金幣，以當(dāng)日價(jià)格購(gòu)買(mǎi)該紀(jì)念品；

2. 賣(mài)出持有的任意一個(gè)紀(jì)念品，以當(dāng)日價(jià)格換回金幣。

每天賣(mài)出紀(jì)念品換回的金幣可以立即用于購(gòu)買(mǎi)紀(jì)念品，當(dāng)日購(gòu)買(mǎi)的紀(jì)念品也可以當(dāng)日賣(mài)出換回金幣。當(dāng)然，一直持有紀(jì)念品也是可以的。

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

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

輸入格式

輸入文件名為 souvenir.in。

第一行包含三個(gè)正整數(shù) T,N,MT,N,M，相鄰兩數(shù)之間以一個(gè)空格分開(kāi)，分別代表未來(lái)天數(shù) TT，紀(jì)念品數(shù)量 NN，小偉現(xiàn)在擁有的金幣數(shù)量 MM。

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

輸出格式

輸出文件名為 souvenir.out。

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

輸入樣例 1

6 1 100

50

20

25

20

25

50

輸出樣例 1

305

輸入輸出樣例 1 說(shuō)明

最佳策略是：

第二天花光所有 100100 枚金幣買(mǎi)入 55 個(gè)紀(jì)念品 1；

第三天賣(mài)出 55 個(gè)紀(jì)念品 1，獲得金幣 125125 枚；

第四天買(mǎi)入 66 個(gè)紀(jì)念品 1，剩余 55 枚金幣；

第六天必須賣(mài)出所有紀(jì)念品換回 300300 枚金幣，第四天剩余 55 枚金幣，共 305305 枚金幣。

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

輸入樣例 2

3 3 100

10 20 15

15 17 13

15 25 16

輸出樣例 2

217

輸入輸出樣例 2 說(shuō)明

最佳策略是：

第一天花光所有金幣買(mǎi)入 1010 個(gè)紀(jì)念品 1;

第二天賣(mài)出全部紀(jì)念品 1 得到 150150 枚金幣并買(mǎi)入 88 個(gè)紀(jì)念品 2 和 11 個(gè)紀(jì)念品 3，剩余 11 枚金幣;

第三天必須賣(mài)出所有紀(jì)念品換回 216216 枚金幣，第二天剩余 11 枚金幣，共 217217 枚金幣。

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

答案及思路分析：

解析：如果只有1天的話，買(mǎi)了再賣(mài)，總共剩下M個(gè)金幣。

T天N種紀(jì)念幣，根據(jù)題目設(shè)定范圍，100以?xún)?nèi)，可以用二維表格推導(dǎo)。

時(shí)間不可逆，只能1~N。

每天買(mǎi)哪些紀(jì)念品呢?根據(jù)測(cè)試樣例分析，紀(jì)念品任意多，沒(méi)有個(gè)數(shù)限制。根據(jù)金幣的上限，可以推到出這個(gè)就是完全背包。大家可以套一下完全背包的算法。每天需要做一次完全背包處理，當(dāng)天不想賣(mài)出金幣，相當(dāng)于賣(mài)出金幣再買(mǎi)入金幣。

參考答案：

加工零件(work)

輸入文件名：work.in

輸出文件名：work.out

共 20 個(gè)測(cè)試點(diǎn)，每個(gè)測(cè)試點(diǎn) 5 分

每個(gè)測(cè)試點(diǎn)限時(shí) 1 秒，運(yùn)行內(nèi)存上限 256MB

問(wèn)題描述

凱凱的工廠正在有條不紊地生產(chǎn)一種神奇的零件，神奇的零件的生產(chǎn)過(guò)程自然也很神奇。工廠里有 n 位工人，工人們從 1 ~ 編號(hào)，某些工人之間存在雙向的零件傳送帶。保證每?jī)擅と酥g最多只存在一條傳送帶。

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

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

軒軒是 1 號(hào)工人。現(xiàn)在給出 q 張工單，第 i 張工單表示編號(hào)為ai的工人想生產(chǎn)一個(gè)第 Li 階段的零件。軒軒想知道對(duì)于每張工單，他是否需要給別人提供原材料。他知道聰明的你一定可以幫他計(jì)算出來(lái)！

輸入格式

輸入文件名為 work.in。

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

接下來(lái) m 行，每行兩個(gè)正整數(shù) u 和 v，表示編號(hào)為 u 和 v 的工人之間存在一條零件傳送帶。保證 u !=v。

接下來(lái) q行，每行兩個(gè)正整數(shù) a 和 L，表示編號(hào)為 a 的工人想生產(chǎn)一個(gè)第 L 階段的零件。

輸出格式

輸出文件名為 work.out。

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

樣例 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 解釋

編號(hào)為 1 的工人想生產(chǎn)第 1 階段的零件，需要編號(hào)為 2 的工人提供原材料。

編號(hào)為 2 的工人想生產(chǎn)第 1 階段的零件，需要編號(hào)為 1 和 3 的工人提供原材料。

編號(hào)為 3 的工人想生產(chǎn)第 1 階段的零件，需要編號(hào)為 2 的工人提供原材料。

編號(hào)為 1 的工人想生產(chǎn)第 2 階段的零件，需要編號(hào)為 2 的工人生產(chǎn)第 1 階段的零件，需要為編號(hào) 1 和 3 的工人提供原材料。

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

編號(hào)為 3 的工人想生產(chǎn)第 2 階段的零件，需要編號(hào)為 2 的工人生產(chǎn)第 1 階段的零件，需要編號(hào)為 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 解釋

編號(hào)為 1 的工人想生產(chǎn)第 1 階段的零件，需要編號(hào)為 2 和 5 的工人提供原材料。

編號(hào)為 1 的工人想生產(chǎn)第 2 階段的零件，需要編號(hào)為 2 和 5 的工人生產(chǎn)第 1 階段的零件，需要編號(hào)為1,3,4 的工人提供原材料。

編號(hào)為 1 的工人想生產(chǎn)第 3 階段的零件，需要編號(hào)為 2 和 5 的工人生產(chǎn)第 2 階段的零件，需要編號(hào)為 1,3,4 的工人生產(chǎn)第 1 階段的零件，需要編號(hào)為 2,3,4,5 的工人提供 原材料。

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

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

答案及思路分析：

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

根據(jù)性質(zhì)，工人之間的關(guān)系是圖。相連接，之間的路徑權(quán)值是1。加工零件的過(guò)程可以相互傳遞，來(lái)回都是偶數(shù)次，因此在求個(gè)最短路時(shí)看奇偶步數(shù)內(nèi)能否可達(dá)，要求與L的奇偶性一致。

參考答案：

以上是2019CSP-J(入門(mén)級(jí))第二輪認(rèn)證試題的解題分析，參加此次考試的學(xué)員們，你們都答對(duì)了嗎？另，關(guān)注童程童美微信公眾，在后臺(tái)回復(fù)【真題】即可免費(fèi)領(lǐng)取“信息學(xué)奧賽歷年真題資料包”哦~

CSP-J/S是CCF創(chuàng)辦的CSP(軟件能力認(rèn)證)中面向非專(zhuān)業(yè)級(jí)的軟件能力認(rèn)證，也就是我們熟知的信息學(xué)奧賽，含金量高。

童程童美信息學(xué)奧賽課程是由專(zhuān)業(yè)教研團(tuán)隊(duì)與北京知名學(xué)府聯(lián)合研發(fā)，課程內(nèi)容循序漸進(jìn)，指導(dǎo)學(xué)員圍繞每個(gè)考試階段的重點(diǎn)知識(shí)進(jìn)行學(xué)習(xí)；教研團(tuán)隊(duì)強(qiáng)大專(zhuān)業(yè)，授課老師經(jīng)驗(yàn)充足，確保準(zhǔn)確把握科創(chuàng)活動(dòng)方向和特點(diǎn)，保證學(xué)員學(xué)習(xí)進(jìn)度和質(zhì)量，助力學(xué)員在測(cè)評(píng)中取得優(yōu)異成績(jī)！