资源简介

2025 CCF 非专业级软件能力认证
CSP-J/S 2025 第二轮认证
提高级
时间：2025 年 11 月 1 日 14:30 18:30
题目名称 社团招新 道路修复 谐音替换 员工招聘
题目类型 传统型 传统型 传统型 传统型
目录 club road replace employ
可执行文件名 club road replace employ
输入文件名 club.in road.in replace.in employ.in
输出文件名 club.out road.out replace.out employ.out
每个测试点时限 1.0 秒 1.0 秒 1.0 秒 1.0 秒
内存限制 512 MiB 512 MiB 2048 MiB 512 MiB
测试点数目 20 25 20 25
测试点是否等分 是 是 是 是
提交源程序文件名
对于 C++ 语言 club.cpp road.cpp replace.cpp employ.cpp
编译选项
对于 C++ 语言 ‐O2 ‐std=c++14 ‐static
注. 意. 事. 项. （请. 仔. 细. 阅. 读. ）
1. 文件名（程序名和输入输出文件名）必须使用英文小写。
2. main 函数的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3. 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末换行）。
4. 选手提交的程序源文件大小不得超过 100 KiB。
5. 提交的程序源文件的放置位置请参考各省的具体要求。
6. 程序可使用的栈空间内存限制与题目的内存限制一致。
7. 禁止在源代码中改变编译器参数（如使用 #pragma 命令），禁止使用系统结构相
关指令（如内联汇编）或其他可能造成不公平的方法。
8. 因违反上述规定而出现的问题，申诉时一律不予受理。
9. 只提供 Linux 格式附加样例文件。
10. 全国统一评测时采用的机器配置为：Intel Core Ultra 9 285K CPU @ 3.70 GHz
（关闭睿频与能效核），内存 96 GB。上述时限以此配置为准。
11. 评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准。
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 社团招新（club）
社团招新（club）
【题目描述】
小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 n 个新
成员，其中 n 为偶. 数. 。现在小 L 希望将他们分到协会不同的部门。
算法协会共设有三个部门，其中第 i (1 ≤ i ≤ n) 个新成员对第 j (1 ≤ j ≤ 3) 个部
门的满意度为 ai,j。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度
之和，也就是说，若将∑第 i (1 ≤ i ≤ n) 个新成员分配到了第 di ∈ {1, 2, 3} 个部门，则该
分配方案的满意度为 ni=1 ai,d 。i
小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不. 存. 在.
一个部门被分配多. 于. n 个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满2
意度的最大值。
【输入格式】
从文件 club.in 中读入数据。
本. 题. 包. 含. 多. 组. 测. 试. 数. 据. 。
输入的第一行包含一个正整数 t，表示测试数据组数。
接下来依次输入每组测试数据，对于每组测试数据：
第一行包含一个正整数 n，表示新成员的数量。
第 i+ 1 (1 ≤ i ≤ n) 行包含三个非负整数 ai,1, ai,2, ai,3，分别表示第 i 个新成员对
第 1, 2, 3 个部门的满意度。
【输出格式】
输出到文件 club.out 中。
对于每组测试数据，输出一行一个非负整数，表示满足小 L 要求的分配方案的满意
度的最大值。
【样例 1 输入】
1 3
2 4
3 4 2 1
4 3 2 4
5 5 3 4
6 3 5 1
7 4
第 2 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 社团招新（club）
8 0 1 0
9 0 1 0
10 0 2 0
11 0 2 0
12 2
13 10 9 8
14 4 0 0
【样例 1 输出】
1 18
2 4
3 13
【样例 1 解释】
该样例共包含三组测试数据。
对于第一组测试数据，可以将四个新成员分别分配到第 1, 3, 1, 2 个部门，则三个部
门的新成员数量分别为 2, 1, 1，均不超过 4 = 2，满意度为 4 + 4 + 5 + 5 = 18。
2
对于第二组测试数据，可以将四个新成员分别分配到第 1, 1, 2, 2 个部门，则三个部
门的新成员数量分别为 2, 2, 0，均不超过 4 = 2，满意度为 0 + 0 + 2 + 2 = 4。
2
对于第三组测试数据，可以将两个新成员分别分配到第 2, 1 个部门，则三个部门的
新成员数量分别为 1, 1, 0，均不超过 2 = 1，满意度为 9 + 4 = 13。
2
【样例 2】
见选手目录下的 club/club2.in 与 club/club2.ans。
该样例满足测试点 3, 4 的约束条件。
【样例 3】
见选手目录下的 club/club3.in 与 club/club3.ans。
该样例满足测试点 5 8 的约束条件。
【样例 4】
见选手目录下的 club/club4.in 与 club/club4.ans。
该样例满足测试点 9 的约束条件。
第 3 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 社团招新（club）
【样例 5】
见选手目录下的 club/club5.in 与 club/club5.ans。
该样例满足测试点 15, 16 的约束条件。
【数据范围】
对于所有测试数据，保证：
1 ≤ t ≤ 5；
2 ≤ n ≤ 105，且 n 为偶数；
对于所有 1 ≤ i ≤ n，1 ≤ j ≤ 3，均有 0 ≤ a 4i,j ≤ 2× 10 。
测试点编号 n = 特殊性质
1 2
2 4
无
3, 4 10
5 8 30
9 B
200
10, 11 无
12 A
13, 14 B
105
15, 16 C
17 20 无
特殊性质 A：对于所有 1 ≤ i ≤ n，均有 ai,2 = ai,3 = 0。
特殊性质 B：对于所有 1 ≤ i ≤ n，均有 ai,3 = 0。
特殊性质 C：对于所有 1 ≤ i ≤ n，1 ≤ j ≤ 3，ai,j 均在 [0, 2× 104] 中独. 立. 均. 匀. 随. 机.
生成。
第 4 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 道路修复（road）
道路修复（road）
【题目描述】
C国的交通系统由 n座城市与m条连接两座城市的双向道路构成，第 i (1 ≤ i ≤ m)
条道路连接城市 ui 和 vi。任. 意. 两. 座. 城. 市. 都. 能. 通. 过. 若. 干. 条. 道. 路. 相. 互. 到. 达. 。
然而，近期由于一场大地震，所有m条道路都被破坏了，修复第 i (1 ≤ i ≤ m)条道路
的费用为 wi。与此同时，C国还有 k个准备进行城市化改造的乡镇。对于第 j (1 ≤ j ≤ k)
个乡镇，C国对其进行城市化改造的费用为 cj。在城市化改造完第 j (1 ≤ j ≤ k)个乡镇
后，可以在这个乡镇与原来的 n 座城市间建造若干条道路，其中在它与第 i (1 ≤ i ≤ n)
座城市间建造一条道路的费用为 aj,i。C 国可以在这 k 个乡镇中选择任. 意. 多. 个. 进行城市
化改造，也可以不选择任何乡镇进行城市化改造。
为尽快恢复城市间的交通，C 国政府希望以最低的费用将原. 有. 的 n 座城市两两连
通，也即任意两座原有的城市都能通过若干条修复或新建造的道路相互到达。你需要帮
助他们求出，将原有的 n 座城市两两连通的最小费用。
【输入格式】
从文件 road.in 中读入数据。
输入的第一行包含三个非负整数 n,m, k，分别表示原有的城市数量、道路数量和准
备进行城市化改造的乡镇数量。
输入的第 i+ 1 (1 ≤ i ≤ m) 行包含三个非负整数 ui, vi, wi，表示第 i 条道路连接的
两座城市与修复该道路的费用。
输入的第 j +m+1 (1 ≤ j ≤ k) 行包含 n+1 个非负整数 cj, aj,1, aj,2, . . . , aj,n，分别
表示将第 j 个乡镇进行城市化改造的费用与在该乡镇与原有的城市间建造道路的费用。
【输出格式】
输出到文件 road.out 中。
输出一行一个非负整数，表示将原有的 n 座城市两两连通的最小费用。
【样例 1 输入】
1 4 4 2
2 1 4 6
3 2 3 7
4 4 2 5
5 4 3 4
6 1 1 8 2 4
第 5 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 道路修复（road）
7 100 1 3 2 4
【样例 1 输出】
1 13
【样例 1 解释】
C 国政府可以选择修复第 3 条和第 4 条道路，然后将第 1 个乡镇进行城市化改造，
并建造它与第 1, 3 座城市间的道路，总费用为 5 + 4 + 1 + 1 + 2 = 13。可以证明，不存
在比 13 更小的费用能使原有的 4 座城市两两连通。
【样例 2】
见选手目录下的 road/road2.in 与 road/road2.ans。
该样例满足测试点 11, 12 的约束条件。
【样例 3】
见选手目录下的 road/road3.in 与 road/road3.ans。
该样例满足测试点 13, 14 的约束条件。
【样例 4】
见选手目录下的 road/road4.in 与 road/road4.ans。
该样例满足测试点 15, 16 的约束条件。
【数据范围】
对于所有测试数据，保证：
1 ≤ n ≤ 104，1 ≤ m ≤ 106，0 ≤ k ≤ 10；
对于所有 1 ≤ i ≤ m，均有 1 ≤ ui, vi ≤ n，ui = vi 且 0 ≤ wi ≤ 109；
对于所有 1 ≤ j ≤ k，均有 0 ≤ cj ≤ 109；
对于所有 1 ≤ j ≤ k，1 ≤ i ≤ n，均有 0 ≤ a 9j,i ≤ 10 ；
任意两座原有的城市都能通过若干条原有的道路相互到达。
第 6 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 道路修复（road）
测试点编号 n ≤ m ≤ k ≤ 特殊性质
1 4 104 106 0 无
5, 6 A
105
7, 8 无
5
9, 10 A
103
11, 12 无
13, 14 A
10
15, 16 106 无
17, 18 A
5
19, 20 104
无
21 25 10
特殊性质 A：对于所有 1 ≤ j ≤ k，均有 cj = 0 且均存在 1 ≤ i ≤ n 满足 aj,i = 0。
第 7 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 谐音替换（replace）
谐音替换（replace）
【题目描述】
小 W 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字
词替换为读音相同或相近的字词。小 W 发现，谐音替换的过程可以用字符串来进行描
述。具体地，小 W 将谐音替换定义为以下字符串问题：
给定 n 个字符串二元组，第 i (1 ≤ i ≤ n) 个字符串二元组为 (si,1, si,2)，满足
|si,1| = |si,2|，其中 |s| 表示字符串 s 的长度。
对于字符串 s，定义 s 的替. 换. 如下：
对于 s 的某个子串 y，若存在 1 ≤ i ≤ n 满足 y = s ′i,1，则将 y 替换为 y = si,2。
具体地，设 s = x + y + z，其中 x 和 z 可以为空，“+”表示字符串拼接，则 s
的替换将得到字符串 s′ = x+ y′ + z。
小 W 提出了 q 个问题，第 j (1 ≤ j ≤ m) 个问题会给定两个不. 同. 的字符串 tj,1, tj,2，
她想知道有多少种字符串 tj,1 的替换能够得到字符串 tj,2。两种 s 的替换不同当且仅当
子. 串. y 的. 位. 置. 不. 同. 或. 用. 于. 替. 换. 的. 二. 元. 组. (si,1, si,2) 不. 同. ，即 x, z 不同或 i 不同。你需要
回答小 W 提出的所有问题。
【输入格式】
从文件 replace.in 中读入数据。
输入的第一行包含两个正整数 n, q，分别表示字符串二元组的数量和小 W 提出的
问题的数量。
输入的第 i+ 1 (1 ≤ i ≤ n) 行包含两个字符串 si,1, si,2，表示第 i 个字符串二元组。
输入的第 j + n + 1 (1 ≤ j ≤ q) 行包含两个字符串 tj,1, tj,2，表示小 W 提出的第 j
个问题。
【输出格式】
输出到文件 replace.out 中。
输出 q 行，其中第 j (1 ≤ j ≤ q) 行包含一个非负整数，表示替换后得到字符串 tj,2
的字符串 tj,1 的替换的数量。
【样例 1 输入】
1 4 2
2 xabcx xadex
3 ab cd
4 bc de
第 8 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 谐音替换（replace）
5 aa bb
6 xabcx xadex
7 aaaa bbbb
【样例 1 输出】
1 2
2 0
【样例 1 解释】
对于小 W 的第一个询问，共有 2 种 t1,1 的替换能够得到 t1,2：
1. 令 x, z 均为空串，y = xabcx，i = 1，则 y′ = xadex，替换后得到 xadex；
2. 令 x = xa，y = bc，z = x，i = 3，则 y′ = de，替换后得到 xadex。
【样例 2 输入】
1 3 4
2 a b
3 b c
4 c d
5 aa bb
6 aa b
7 a c
8 b a
【样例 2 输出】
1 0
2 0
3 0
4 0
【样例 3】
见选手目录下的 replace/replace3.in 与 replace/replace3.ans。
该样例满足测试点 11, 12 的约束条件。
第 9 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 谐音替换（replace）
【样例 4】
见选手目录下的 replace/replace4.in 与 replace/replace4.ans。
该样例满足测试点 15, 16 的约束条件。
【数据范围∑】 ∑
设 L = n1 i=1|si,1|+ |s |，L =
q
i,2 2 j=1|tj,1|+ |tj,2|。对于所有测试数据，保证：
1 ≤ n, q ≤ 2× 105；
2 ≤ L1, L2 ≤ 5× 106；
对于所有 1 ≤ i ≤ n，si,1, si,2 均仅包含小写英文字母，且 |si,1| = |si,2|；
对于所有 1 ≤ j ≤ q，tj,1, tj,2 均仅包含小写英文字母，且 tj,1 = tj,2。
测试点编号 n, q ≤ L1, L2 ≤ 特殊性质
1, 2 102 200
无
3 5 2, 000
103
6 AB
7, 8 104 106 A
9, 10 B
11, 12 2× 106 无
13, 14 2× 105 A
15, 16 5× 106 B
17 20 无
特殊性质 A：q = 1。
特殊性质 B：定义字符串 s 为特. 别. 的. ，当且仅当字符串 s 仅包含字符 a 和 b，且
字符 b 在 s 中出现恰. 好. 一次。对于所有 1 ≤ i ≤ n，si,1, si,2 均为特别的，且对于所有
1 ≤ j ≤ q，tj,1, tj,2 均为特别的。
第 10 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 员工招聘（employ）
员工招聘（employ）
【题目描述】
小 Z 和小 H 想要合伙开一家公司，共有 n 人前来应聘，编号为 1 n。小 Z 和小
H 希望录用至少 m 人。
小 H 是面试官，将在接下来 n 天每天面试一个人。小 Z 负责决定应聘人前来面试
的顺序。具体地，小 Z 可以选择一个 1 n 的排列 p，然后在第 i (1 ≤ i ≤ n) 天通知编
号为 pi 的人前来面试。
小 H 准备了 n 套难度不一的面试题。由于 n 个前来应聘的人水平大致相同，因此
对于同一套题，所有人的作答结果是一致的。具体地，第 i (1 ≤ i ≤ n) 天的面试题的难
度为 si ∈ {0, 1}，其中 si = 0 表示这套题的难度较高，没有人能够做出；si = 1 表示这
套题的难度较低，所有人均能做出。小 H 会根据面试者的作答结果决定是否录用，即如
果面试者没有做出面试题，则会拒绝，否则会录用。
然而，每个人的耐心都有一定的上限，如果在他面试之前未录用的人数过多，则他
会直接放弃参加面试。具体地，编号为 i (1 ≤ i ≤ n) 的人的耐心上限可以用非负整数 ci
描述，若在他之前已经有不. 少. 于. ci 人被拒绝或放弃参加面试，则他也将放弃参加面试。
小 Z 想知道一共有多少种面试的顺序 p 能够让他们录用至少 m 人。你需要帮助小
Z 求出，能够录用至少 m 人的排列 p 的数量。由于答案可能较大，你只需要求出答案
对 998, 244, 353 取模后的结果。
【输入格式】
从文件 employ.in 中读入数据。
输入的第一行包含两个正整数 n,m，分别表示前来应聘的人数和希望录用的人数。
输入的第二行包含一个长度为 n 的字符串 s1 . . . sn，表示每一天的面试题的难度。
输入的第三行包含 n 个非负整数 c1, c2, . . . , cn，表示每个人的耐心上限。
【输出格式】
输出到文件 employ.out 中。
输出一行一个非负整数，表示能够录用至少 m 人的排列 p 的数量对 998, 244, 353
取模后的结果。
【样例 1 输入】
1 3 2
2 101
3 1 1 2
第 11 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 员工招聘（employ）
【样例 1 输出】
1 2
【样例 1 解释】
共有以下 2 种面试的顺序 p 能够让小 Z 和小 H 录用至少 2 人：
1. p = [1, 2, 3]，依次录用编号为 1 的人和编号为 3 的人；
2. p = [2, 1, 3]，依次录用编号为 2 的人和编号为 3 的人。
【样例 2 输入】
1 10 5
2 1101111011
3 6 0 4 2 1 2 5 4 3 3
【样例 2 输出】
1 2204128
【样例 3】
见选手目录下的 employ/employ3.in 与 employ/employ3.ans。
该样例满足测试点 6 8 的约束条件。
【样例 4】
见选手目录下的 employ/employ4.in 与 employ/employ4.ans。
该样例满足测试点 12 14 的约束条件。
【样例 5】
见选手目录下的 employ/employ5.in 与 employ/employ5.ans。
该样例满足测试点 18 21 的约束条件。
第 12 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}
2025 CCF 非专业级软件能力认证 CSP-J/S 2025 第二轮认证 提高级 员工招聘（employ）
【数据范围】
对于所有测试数据，保证：
1 ≤ m ≤ n ≤ 500；
对于所有 1 ≤ i ≤ n，均有 si ∈ {0, 1}；
对于所有 1 ≤ i ≤ n，均有 0 ≤ ci ≤ n。
测试点编号 n ≤ m 特殊性质
1, 2 10
无
3 5 18
≤ n
6 8 A
102
9 11
12 14 = 1 无
15 = n
16, 17 500 A
18 21 ≤ n B
22 25 无
特殊性质 A：对于所有 1 ≤ i ≤ n，均有 si = 1。 ∑
特殊性质 B：在 s1, s2, . . . , sn 中最多只有 18 个取值为 1，即 ni=1 si ≤ 18。
第 13 页 共 13 页
{#{QQABAQSUogiAAJAAAAgCAQGgCEIYkAGACIgOxFAcMAIBgAFABAA=}#}

展开更多......

收起↑