新闻活动
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(软件能力认证)中面向非专业级的软件能力认证，也就是我们熟知的信息学奥赛，含金量高。
童程童美信息学奥赛课程是由专业教研团队与北京知名学府联合研发，课程内容循序渐进，指导学员围绕每个考试阶段的重点知识进行学习；教研团队强大专业，授课老师经验充足，确保准确把握科创活动方向和特点，保证学员学习进度和质量，助力学员在测评中取得优异成绩！