2025年CSP-S2复赛试题
__SECTIONS__:[{"name": "编程题", "count": 4}] 从PDF导入：2025年CSP-S2复赛试题
试卷题目预览
社团招新（club）
小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 n 个新成员，其中 n 为偶数。现在小 L 希望将他们分到协会不同的部门。
算法协会共设有三个部门，其中第 i (1 ≤ i ≤ n) 个新成员对第 j (1 ≤ j ≤ 3) 个部门的满意度为 ai,j。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和。
小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于 n/2 个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大值。
本题包含多组测试数据。 输入的第一行包含一个正整数 t，表示测试数据组数。 对于每组测试数据：第一行包含一个正整数 n；接下来 n 行，每行包含三个非负整数 ai,1, ai,2, ai,3，分别表示第 i 个新成员对三个部门的满意度。
对于每组测试数据，输出一行一个非负整数，表示满足小 L 要求的分配方案的满意度的最大值。
3 4 4 2 1 3 2 4 5 3 4 3 5 1 4 0 1 0 0 1 0 0 2 0 0 2 0 2 10 9 8 4 0 0
18 4 13
道路修复（road）
C 国的交通系统由 n 座城市与 m 条连接两座城市的双向道路构成。任意两座城市都能通过若干条道路相互到达。
然而，近期由于一场大地震，所有 m 条道路都被破坏了，修复第 i (1 ≤ i ≤ m) 条道路的费用为 wi。与此同时，C 国还有 k 个准备进行城市化改造的乡镇。
对于第 j (1 ≤ j ≤ k) 个乡镇，C 国对其进行城市化改造的费用为 cj。在城市化改造完后，可以在这个乡镇与原来的 n 座城市间建造道路，其中在第 j 个乡镇与第 i 座城市间建造一条道路的费用为 aj,i。
C 国可以在这 k 个乡镇中选择任意多个进行城市化改造，也可以不选择任何乡镇进行城市化改造。
C 国政府希望以最低的费用将原有的 n 座城市两两连通。你需要帮助他们求出最小费用。
输入的第一行包含三个非负整数 n, m, k，分别表示原有的城市数量、道路数量和准备进行城市化改造的乡镇数量。 接下来 m 行，每行包含三个非负整数 ui, vi, wi，表示第 i 条道路连接的两座城市与修复该道路的费用。 接下来 k 行，每行包含 n+1 个非负整数 cj, aj,1, aj,2, ..., aj,n，分别表示第 j 个乡镇进行城市化改造的费用与建造道路的费用。
输出一行一个非负整数，表示将原有的 n 座城市两两连通的最小费用。
4 4 2 1 4 6 2 3 7 4 2 5 4 3 4 1 1 8 2 4 100 1 3 2 4
13
谐音替换（replace）
小 W 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字词替换为读音相同或相近的字词。
给定 n 个字符串二元组，第 i 个字符串二元组为 (si,1, si,2)，满足 |si,1| = |si,2|。
对于字符串 s，定义 s 的替换如下：对于 s 的某个子串 y，若存在 1 ≤ i ≤ n 满足 y = si,1，则将 y 替换为 si,2。
小 W 提出了 q 个问题，第 j 个问题会给定两个不同的字符串 tj,1, tj,2，她想知道有多少种字符串 tj,1 的替换能够得到字符串 tj,2。
输入的第一行包含两个正整数 n, q。 接下来 n 行，每行包含两个字符串 si,1, si,2，表示第 i 个字符串二元组。 接下来 q 行，每行包含两个字符串 tj,1, tj,2，表示第 j 个问题。
输出 q 行，每行包含一个非负整数，表示替换的数量。
4 2 xabcx xadex ab cd bc de aa bb xabcx xadex aaaa bbbb
2 0
员工招聘（employ）
小 Z 和小 H 想要合伙开一家公司，共有 n 人前来应聘，编号为 1 ~ n。小 Z 和小 H 希望录用至少 m 人。
小 H 是面试官，将在接下来 n 天每天面试一个人。小 Z 负责决定应聘人前来面试的顺序。
小 H 准备了 n 套难度不一的面试题。第 i 天的面试题的难度为 si ∈ {0, 1}，其中 si = 0 表示难度较高（没有人能做出），si = 1 表示难度较低（所有人都能做出）。
每个人的耐心都有一定的上限，编号为 i 的人的耐心上限为 ci。若在他之前已经有不少于 ci 人被拒绝或放弃参加面试，则他也将放弃参加面试。
小 Z 想知道一共有多少种面试的顺序 p 能够让他们录用至少 m 人。答案对 998244353 取模。
输入的第一行包含两个正整数 n, m。 输入的第二行包含一个长度为 n 的字符串 s1...sn，表示每一天的面试题的难度。 输入的第三行包含 n 个非负整数 c1, c2, ..., cn，表示每个人的耐心上限。
输出一行一个非负整数，表示排列的数量对 998244353 取模后的结果。
3 2 101 1 1 2
2