传习Chuanxi

CSP-J/S 2019 第二轮认证 入门级

CSP-J/S 2019 第二轮认证 入门级

  • 场次：2019年11月
  • 考试时长：210 分钟
  • 满分：400 分
  • 编译选项：-lm
  • 题目来源：第三方来源（社区转写，非官方，仅供参考）

注意事项（原卷照录）

考试时间：2019 年 11 月 16 日 14:30 ~ 18:00。

注意事项（请仔细阅读）

  1. 文件名（程序名和输入输出文件名）必须使用英文小写。
  2. main 函数的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
  3. 选手提交的程序源文件的放置位置请参考各省的具体要求。
  4. 因违反上述规定而出现的问题，申诉时一律不予受理。
  5. 程序可使用的栈内存空间限制与题目的内存限制一致。
  6. 全国统一评测时采用的机器配置为：Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz，内存 32GB。上述时限以此配置为准。
  7. 只提供 Linux 格式附加样例文件。
  8. 评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以其为准。
  9. 最终评测时所用的编译命令中不含任何优化开关。

结果比较方式：全文比较（过滤行末空格及文末换行）。

编程题

本分区标题为平台补的结构性占位，原卷（来源件）未收录。

编程题

数字游戏

C++时间 1 s内存 256 MB 文件 IO：number.in → number.out

小 K 同学向小 P 同学发送了一个长度为 88 的 01 字符串来玩数字游戏，小 P 同学想要知道字符串中究竟有多少个 11。

注意：01 字符串为每一个字符是 00 或者 11 的字符串，如 101 为一个长度为 33 的 01 字符串。

输入格式

输入文件只有一行，一个长度为 88 的 01 字符串 ss。

输出格式

输出文件只有一行，包含一个整数，即 01 字符串中字符 11 的个数。

样例

输入 1
00010100
输出 1
2

该 01 字符串中有 22 个字符 11。

输入 2
11111111
输出 2
8

该 01 字符串中有 88 个字符 11。

数据范围

对于 20%20\% 的数据，保证输入的字符全部为 00。

对于 100%100\% 的数据，输入只可能包含字符 00 和字符 11，字符串长度固定为 88。

部分分

  • 100 分

    全部 2020 个测试点等分；20%20\% 数据保证输入字符全为 00；100%100\% 数据仅含字符 00 与 11，长度固定为 88。

你的代码（C++）

提交后由评测机编译运行，结果见下方
编辑器加载中…

76 B / 64 KB

判题结果

编程题

公交换乘

C++时间 1 s内存 256 MB 文件 IO：transfer.in → transfer.out

著名旅游城市 B 市为了鼓励大家采用公共交通方式出行，推出了一种地铁换乘公交车的优惠方案：

  1. 在搭乘一次地铁后可以获得一张优惠票，有效期为 45 分钟，在有效期内可以消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。在有效期内指开始乘公交车的时间与开始乘地铁的时间之差小于等于 45 分钟，即：
    tbus−tsubway≤45t_{bus} - t_{subway} \leq 45。
  2. 搭乘地铁获得的优惠票可以累积，即可以连续搭乘若干次地铁后再连续使用优惠票搭乘公交车。
  3. 搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。

现在你得到了小轩最近的公共交通出行记录，你能帮他算算他的花费吗？

输入格式

输入文件的第一行包含一个正整数 nn，代表乘车记录的数量。

接下来的 nn 行，每行包含 3 个整数，相邻两数之间以一个空格分隔。第 ii 行的第 1 个整数代表第 ii 条记录乘坐的交通工具，0 代表地铁，1 代表公交车；第 2 个整数代表第 ii 条记录乘车的票价 priceiprice_i；第 3 个整数代表第 ii 条记录开始乘车的时间 tit_i（距 0 时刻的分钟数）。

我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。

输出格式

输出文件有一行，包含一个正整数，代表小轩出行的总花费。

样例

输入 1
6
0 10 3
1 5 46
0 12 50
1 3 96
0 5 110
1 6 135
输出 1
36

第一条记录，在第 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

第一条记录，在第 1 分钟花费 5 元乘坐地铁。

第二条记录，在第 16 分钟花费 20 元乘坐地铁。

第三条记录，在第 23 分钟花费 7 元乘坐地铁。

第四条记录，在第 31 分钟乘坐公交车，此时只有第二条记录中乘坐的地铁票价高于本次公交车票价，所以使用第二条记录中乘坐地铁获得的优惠票。

第五条记录，在第 38 分钟乘坐公交车，此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用，使用获得最早的优惠票，即第一条记录中乘坐地铁获得的优惠票。

第六条记录，在第 68 分钟乘坐公交车，使用第三条记录中乘坐地铁获得的优惠票。

总共花费 32 元。

数据范围

对于 30%30\% 的数据，n≤1000n \leq 1000，ti≤106t_i \leq 10^6。

另有 15%15\% 的数据，ti≤107t_i \leq 10^7，所有 priceiprice_i 相等。

另有 15%15\% 的数据，ti≤109t_i \leq 10^9，所有 priceiprice_i 相等。

对于 100%100\% 的数据，n≤105n \leq 10^5，ti≤109t_i \leq 10^9，1≤pricei≤10001 \leq price_i \leq 1000。

部分分

  • 100 分

    全部 2020 个测试点等分；数据范围见 constraintsMd 各百分比档。

原文保真说明：原卷印刷错误 1 处（照原卷保留，未作修改）

  • 原卷印刷如此其它name

    原卷作 公交换乘

    原卷第 4 页题目标题印作「公交换乘」；第 1 页题目概况表中文题目名称印作「交通换乘」。本题 name 按题面页标题录入。

你的代码（C++）

提交后由评测机编译运行，结果见下方
编辑器加载中…

76 B / 64 KB

判题结果

编程题

纪念品

C++时间 1 s内存 256 MB 文件 IO：souvenir.in → souvenir.out

小伟突然获得一种超能力，他知道未来 TT 天 NN 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

每天，小伟可以进行以下两种交易无限次：

  1. 任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；
  2. 卖出持有的任意一个纪念品，以当日价格换回金币。

每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。

TT 天之后，小伟的超能力消失。因此他一定会在第 TT 天卖出所有纪念品换回金币。

小伟现在有 MM 枚金币，他想要在超能力消失后拥有尽可能多的金币。

输入格式

第一行包含三个正整数 T,N,MT, N, M，相邻两数之间以一个空格分开，分别代表未来天数 TT，纪念品数量 NN，小伟现在拥有的金币数量 MM。

接下来 TT 行，每行包含 NN 个正整数，相邻两数之间以一个空格分隔。第 ii 行的 NN 个正整数分别为 Pi,1,Pi,2,…,Pi,NP_{i,1},P_{i,2},\dots,P_{i,N}，其中 Pi,jP_{i,j} 表示第 ii 天第 jj 种纪念品的价格。

输出格式

输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。

样例

输入 1
6 1 100
50
20
25
20
25
50
输出 1
305

最佳策略是：

第二天花光所有 100100 枚金币买入 55 个纪念品 11；

第三天卖出 55 个纪念品 11，获得金币 125125 枚；

第四天买入 66 个纪念品 11，剩余 55 枚金币；

第六天必须卖出所有纪念品换回 300300 枚金币，第四天剩余 55 枚金币，共 305305 枚金币。

超能力消失后，小伟最多拥有 305305 枚金币。

输入 2
3 3 100
10 20 15
15 17 13
15 25 16
输出 2
217

最佳策略是：

第一天花光所有金币买入 1010 个纪念品 11；

第二天卖出全部纪念品 11 得到 150150 枚金币并买入 88 个纪念品 22 和 11 个纪念品 33，剩余 11 枚金币；

第三天必须卖出所有纪念品换回 216216 枚金币，第二天剩余 11 枚金币，共 217217 枚金币。

超能力消失后，小伟最多拥有 217217 枚金币。

数据范围

对于 10%10\% 的数据，T=1T = 1。

对于 30%30\% 的数据，T≤4,N≤4,M≤100T \leq 4, N \leq 4, M \leq 100，所有价格 10≤Pi,j≤10010 \leq P_{i,j} \leq 100。

另有 15%15\% 的数据，T≤100,N=1T \leq 100, N = 1。

另有 15%15\% 的数据，T=2,N≤100T = 2, N \leq 100。

对于 100%100\% 的数据，T≤100,N≤100,M≤103T \leq 100, N \leq 100, M \leq 10^3，所有价格 1≤Pi,j≤1041 \leq P_{i,j} \leq 10^4，数据保证任意时刻，小明手上的金币数不可能超过 10410^4。

部分分

  • 100 分

    全部 2020 个测试点等分；数据范围见 constraintsMd 各百分比档。

原文保真说明：原卷印刷错误 1 处（照原卷保留，未作修改）

  • 原卷印刷如此符号不一致数据范围

    原卷作 小明手上的金币数 ，常规写法应为 小伟手上的金币数

    原卷第 7 页【数据规模与约定】末句印作「小明」，题面正文（第 6 页）与样例解释均作「小伟」。constraintsMd 按第 7 页图像照录「小明」；原卷印刷不一致已如实记录。

你的代码（C++）

提交后由评测机编译运行，结果见下方
编辑器加载中…

76 B / 64 KB

判题结果

编程题

加工零件

C++时间 1 s内存 256 MB 文件 IO：work.in → work.out

凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有 nn 位工人，工人们从 1∼n1 \sim n 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。

如果 xx 号工人想生产一个被加工到第 L (L>1)L\,(L \gt 1) 阶段的零件，则所有与 xx 号工人有传送带直接相连的工人，都需要生产一个被加工到第 L−1L - 1 阶段的零件（但 xx 号工人自己无需生产第 L−1L - 1 阶段的零件）。

如果 xx 号工人想生产一个被加工到第 11 阶段的零件，则所有与 xx 号工人有传送带直接相连的工人，都需要为 xx 号工人提供一个原材料。

轩轩是 11 号工人。现在给出 qq 张工单，第 ii 张工单表示编号为 aia_i 的工人想生产一个第 LiL_i 阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来！

输入格式

第一行三个正整数 nn，mm 和 qq，分别表示工人的数目、传送带的数目和工单的数目。

接下来 mm 行，每行两个正整数 uu 和 vv，表示编号为 uu 和 vv 的工人之间存在一条零件传输带。保证 u≠vu \neq v。

接下来 qq 行，每行两个正整数 aa 和 LL，表示编号为 aa 的工人想生产一个第 LL 阶段的零件。

输出格式

共 qq 行，每行一个字符串 Yes 或者 No。如果按照第 ii 张工单生产，需要编号为 1 的轩轩提供原材料，则在第 ii 行输出 Yes；否则在第 ii 行输出 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 阶段的零件，需要编号为 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

编号为 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 阶段的零件，需要全部工人提供原材料。

数据范围

共 2020 个测试点。

对所有测试点保证 1≤u,v,a≤n1 \leq u, v, a \leq n。

测试点 1∼41\sim4，1≤n,m≤10001 \leq n, m \leq 1000，q=3q = 3，L=1L = 1。

测试点 5∼85\sim8，1≤n,m≤10001 \leq n, m \leq 1000，q=3q = 3，1≤L≤101 \leq L \leq 10。

测试点 9∼129\sim12，1≤n,m,L≤10001 \leq n, m, L \leq 1000，1≤q≤1001 \leq q \leq 100。

测试点 13∼1613\sim16，1≤n,m,L≤10001 \leq n, m, L \leq 1000，1≤q≤1051 \leq q \leq 10^5。

测试点 17∼2017\sim20，1≤n,m,q≤1051 \leq n, m, q \leq 10^5，1≤L≤1091 \leq L \leq 10^9。

部分分

  • 20 分

    测试点 1∼41\sim4：1≤n,m≤10001 \leq n, m \leq 1000，q=3q = 3，L=1L = 1。

  • 20 分

    测试点 5∼85\sim8：1≤n,m≤10001 \leq n, m \leq 1000，q=3q = 3，1≤L≤101 \leq L \leq 10。

  • 20 分

    测试点 9∼129\sim12：1≤n,m,L≤10001 \leq n, m, L \leq 1000，1≤q≤1001 \leq q \leq 100。

  • 20 分

    测试点 13∼1613\sim16：1≤n,m,L≤10001 \leq n, m, L \leq 1000，1≤q≤1051 \leq q \leq 10^5。

  • 20 分

    测试点 17∼2017\sim20：1≤n,m,q≤1051 \leq n, m, q \leq 10^5，1≤L≤1091 \leq L \leq 10^9。

原文保真说明：原卷印刷错误 1 处（照原卷保留，未作修改）

  • 原卷印刷如此其它name

    原卷作 加工零件

    原卷第 8 页题目标题印作「加工零件」；第 1 页题目概况表中文名称印作「零件加工」。本题 name 按题面页标题录入。

你的代码（C++）

提交后由评测机编译运行，结果见下方
编辑器加载中…

76 B / 64 KB

判题结果