Article2PDF 插件演示

CuteMurasame · 2026-03-04 15:23:11 · 个人记录

:::align{center}

2025 CCF 非专业级软件能力认证

时间：2025 年 10 月 30 日 14:00 ~ 18:00 :::

提交源程序文件名

编译选项

注意事项（请仔细阅读）

1. 文件名（程序名和输入输出文件名）必须使用英文小写。
2. main() 函数的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3. 选手提交的源程序请直接放在选手目录下，无需建立子文件夹。
4. 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。
5. 选手提交的程序源文件必须不大于 100 KB。
6. 程序可使用的栈空间内存限制与题目的内存限制一致。
7. 评测时会开启的子任务依赖已在题面中说明。
8. 只提供 Linux 格式附加样例文件。
9. 直接复制 PDF 题面中的多行样例，数据将带有行号，建议选手直接使用对应目录下的样例文件进行测试。
10. 在终端中执行命令 ulimit -s unlimited 可将当前终端下的栈空间限制放大，但你使用的栈空间大小不应超过题目限制。
11. 禁止在源代码中改变编译器参数（如使用 #pragma 指令），禁止使用系统结构相关指令（如内联汇编）和其他可能造成不公平的方法。

===pagebreak===

:::align{center}

社团招新（club）

:::

【题目描述】

小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 n 个新成员，其中 n 为偶数。现在小 L 希望将他们分到协会不同的部门。

算法协会共设有三个部门，其中第 i (1 \leq i \leq n) 个新成员对第 j (1 \leq j \leq 3) 个部门的满意度为 a_{i,j}。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第 i (1 \leq i \leq n) 个新成员分配到了第 d_i \in \{1,2,3\} 个部门，则该分配方案的满意度为 \sum_{i=1}^{n} a_{i,d_i}。

小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于 \frac{n}{2} 个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大值。

【输入格式】

本题包含多组测试数据。

输入的第一行包含一个正整数 t，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 n，表示新成员的数量。
• 第 i+1 (1 \leq i \leq n) 行包含三个非负整数 a_{i,1}, a_{i,2}, a_{i,3}，分别表示第 i 个新成员对第 1,2,3 个部门的满意度。

【输出格式】

对于每组测试数据，输出一行一个非负整数，表示满足小 L 要求的分配方案的满意度的最大值。

【样例 1 输入】

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

【样例 1 输出】

18
4
13

【样例 1 解释】

该样例共包含三组测试数据。

对于第一组测试数据，可以将四个新成员分别分配到第 1,3,1,2 个部门，则三个部门的新成员数量分别为 2,1,1，均不超过 \frac{4}{2} = 2，满意度为 4 + 4 + 5 + 5 = 18。

对于第二组测试数据，可以将四个新成员分别分配到第 1,1,2,2 个部门，则三个部门的新成员数量分别为 2,2,0，均不超过 \frac{4}{2} = 2，满意度为 0 + 0 + 2 + 2 = 4。

对于第三组测试数据，可以将两个新成员分别分配到第 2,1 个部门，则三个部门的新成员数量分别为 1,1,0，均不超过 \frac{2}{2} = 1，满意度为 9 + 4 = 13。

【样例 2】

见选手目录下的 \textbf{\textit{club/club2.in}} 与 \textbf{\textit{club/club2.ans}}。

该样例满足测试点 3,4 的约束条件。

【样例 3】

见选手目录下的 \textbf{\textit{club/club3.in}} 与 \textbf{\textit{club/club3.ans}}。

该样例满足测试点 5 \sim 8 的约束条件。

【样例 4】

见选手目录下的 \textbf{\textit{club/club4.in}} 与 \textbf{\textit{club/club4.ans}}。

该样例满足测试点 9 的约束条件。

【样例 5】

见选手目录下的 \textbf{\textit{club/club5.in}} 与 \textbf{\textit{club/club5.ans}}。

该样例满足测试点 15,16 的约束条件。

【数据范围】

对于所有测试数据，保证：

• 对于所有 1 \leq i \leq n，1 \leq j \leq 3，均有 0 \leq a_{i,j} \leq 2 \times 10^4。

::cute-table{tuack}

特殊性质 A：对于所有 1 \leq i \leq n，均有 a_{i,2} = a_{i,3} = 0。

特殊性质 B：对于所有 1 \leq i \leq n，均有 a_{i,3} = 0。

特殊性质 C：对于所有 1 \leq i \leq n，1 \leq j \leq 3，a_{i,j} 均在 [0, 2 \times 10^4] 中独立均匀随机生成。

===pagebreak===

:::align{center}

道路修复（road）

:::

【题目描述】

C 国的交通系统由 n 座城市与 m 条连接两座城市的双向道路构成，第 i (1 \leq i \leq m) 条道路连接城市 u_i 和 v_i。任意两座城市都能通过若干条道路相互到达。

然而，近期由于一场大地震，所有 m 条道路都被破坏了，修复第 i (1 \leq i \leq m) 条道路的费用为 w_i。与此同时，C 国还有 k 个准备进行城市化改造的乡镇。对于第 j (1 \leq j \leq k) 个乡镇，C 国对其进行城市化改造的费用为 c_j。在城市化改造完第 j (1 \leq j \leq k) 个乡镇后，可以在这个乡镇与原来的 n 座城市间建造若干条道路，其中在它与第 i (1 \leq i \leq n) 座城市间建造一条道路的费用为 a_{j,i}。C 国可以在这 k 个乡镇中选择任意多个进行城市化改造，也可以不选择任何乡镇进行城市化改造。

为尽快恢复城市间的交通，C 国政 府希望以最低的费用将原有的 n 座城市两两连通，也即任意两座原有的城市都能通过若干条修复或新建造的道路相互到达。你需要帮助他们求出，将原有的 n 座城市两两连通的最小费用。

【输入格式】

输入的第一行包含三个非负整数 n, m, k，分别表示原有的城市数量、道路数量和准备进行城市化改造的乡镇数量。

输入的第 i+1 (1 \leq i \leq m) 行包含三个非负整数 u_i, v_i, w_i，表示第 i 条道路连接的两座城市与修复该道路的费用。

输入的第 j+m+1 (1 \leq j \leq k) 行包含 n+1 个非负整数 c_j, a_{j,1}, a_{j,2}, \ldots, a_{j,n}，分别表示将第 j 个乡镇进行城市化改造的费用与在该乡镇与原有的城市间建造道路的费用。

【输出格式】

输出一行一个非负整数，表示将原有的 n 座城市两两连通的最小费用。

【样例 1 输入】

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

【样例 1 输出】

13

【样例 1 解释】

C 国政 府可以选择修复第 3 条和第 4 条道路，然后将第 1 个乡镇进行城市化改造，并建造它与第 1,3 座城市间的道路，总费用为 5 + 4 + 1 + 1 + 2 = 13。可以证明，不存在比 13 更小的费用能使原有的 4 座城市两两连通。

【样例 2】

见选手目录下的 \textbf{\textit{road/road2.in}} 与 \textbf{\textit{road/road2.ans}}。

该样例满足测试点 11,12 的约束条件。

【样例 3】

见选手目录下的 \textbf{\textit{road/road3.in}} 与 \textbf{\textit{road/road3.ans}}。

该样例满足测试点 13,14 的约束条件。

【样例 4】

见选手目录下的 \textbf{\textit{road/road4.in}} 与 \textbf{\textit{road/road4.ans}}。

该样例满足测试点 15,16 的约束条件。

【数据范围】

对于所有测试数据，保证：

• 对于所有 1 \leq i \leq m，均有 1 \leq u_i, v_i \leq n，u_i \neq v_i 且 0 \leq w_i \leq 10^9；
• 对于所有 1 \leq j \leq k，均有 0 \leq c_j \leq 10^9；
• 对于所有 1 \leq j \leq k，1 \leq i \leq n，均有 0 \leq a_{j,i} \leq 10^9；
• 任意两座原有的城市都能通过若干条原有的道路相互到达。

::cute-table{tuack}

特殊性质 A：对于所有 1 \leq j \leq k，均有 c_j = 0 且均存在 1 \leq i \leq n 满足 a_{j,i} = 0。

===pagebreak===

:::align{center}

谐音替换（replace）

:::

【题目描述】

小 W 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字词替换为读音相同或相近的字词。小 W 发现，谐音替换的过程可以用字符串来进行描述。具体地，小 W 将谐音替换定义为以下字符串问题：

给定 n 个字符串二元组，第 i (1 \leq i \leq n) 个字符串二元组为 (s_{i,1}, s_{i,2})，满足 |s_{i,1}| = |s_{i,2}|，其中 |s| 表示字符串 s 的长度。

对于字符串 s，定义 s 的替换如下：

• 对于 s 的某个子串 y，若存在 1 \leq i \leq n 满足 y = s_{i,1}，则将 y 替换为 y' = s_{i,2}。具体地，设 s = x + y + z，其中 x 和 z 可以为空，“+” 表示字符串拼接，则 s 的替换将得到字符串 s' = x + y' + z。

小 W 提出了 q 个问题，第 j (1 \leq j \leq q) 个问题会给定两个不同的字符串 t_{j,1}, t_{j,2}，她想知道有多少种字符串 t_{j,1} 的替换能够得到字符串 t_{j,2}。两种 s 的替换不同当且仅当子串 y 的位置不同或用于替换的二元组 (s_{i,1}, s_{i,2}) 不同，即 x, z 不同或 i 不同。你需要回答小 W 提出的所有问题。

【输入格式】

输入的第一行包含两个正整数 n, q，分别表示字符串二元组的数量和小 W 提出的问题的数量。

输入的第 i+1 (1 \leq i \leq n) 行包含两个字符串 s_{i,1}, s_{i,2}，表示第 i 个字符串二元组。

输入的第 j+n+1 (1 \leq j \leq q) 行包含两个字符串 t_{j,1}, t_{j,2}，表示小 W 提出的第 j 个问题。

【输出格式】

输出 q 行，其中第 j (1 \leq j \leq q) 行包含一个非负整数，表示替换后得到字符串 t_{j,2} 的字符串 t_{j,1} 的替换的数量。

【样例 1 输入】

4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb

【样例 1 输出】

2
0

【样例 2 输入】

3 4
a b
b c
c d
aa bb
aa b
a c
b a

【样例 2 输出】

0
0
0
0

【样例 1 解释】

对于小 W 的第一个询问，共有 2 种 t_{1,1} 的替换能够得到 t_{1,2}:

1. 令 x, z 均为空串，y = \texttt{xabcx}, i = 1，则 y' = \texttt{xadex}，替换后得到 \texttt{xadex}；
2. 令 x = \texttt{xa}, y = \texttt{bc}, z = \texttt{x}, i = 3，则 y' = \texttt{de}，替换后得到 \texttt{xadex}。

【样例 3】

见选手目录下的 replace/replace3.in 与 replace/replace3.ans。

该样例满足测试点 11, 12 的约束条件。

【样例 4】

见选手目录下的 replace/replace4.in 与 replace/replace4.ans。

该样例满足测试点 15, 16 的约束条件。

【数据范围】

设 L_1 = \sum_{i=1}^{n} |s_{i,1}| + |s_{i,2}|, L_2 = \sum_{j=1}^{q} |t_{j,1}| + |t_{j,2}|。对于所有测试数据，保证:

• 对于所有 1 \leq i \leq n, s_{i,1}, s_{i,2} 均仅包含小写英文字母，且 |s_{i,1}| = |s_{i,2}|;
• 对于所有 1 \leq j \leq q, t_{j,1}, t_{j,2} 均仅包含小写英文字母，且 t_{j,1} \neq t_{j,2}。

::cute-table{tuack}

特殊性质 A：q = 1。

特殊性质 B：定义字符串 s 为特别的，当且仅当字符串 s 仅包含字符 a 和 b，且字符 b 在 s 中出现恰好一次。对于所有 1 \leq i \leq n, s_{i,1}, s_{i,2} 均为特别的，且对于所有 1 \leq j \leq q, t_{j,1}, t_{j,2} 均为特别的。

===pagebreak===

:::align{center}

员工招聘（employ）

:::

【题目描述】

小 Z 和小 H 想要合伙开一家公司，共有 n 人前来应聘，编号为 1 \sim n。小 Z 和小 H 希望录用至少 m 人。

小 H 是面试官，将在接下来 n 天每天面试一个人。小 Z 负责决定应聘人前来面试的顺序。具体地，小 Z 可以选择一个 1 \sim n 的排列 p，然后在第 i (1 \leq i \leq n) 天通知编号为 p_i 的人前来面试。

小 H 准备了 n 套难度不一的面试题。由于 n 个前来应聘的人水平大致相同，因此对于同一套题，所有人的作答结果是一致的。具体地，第 i (1 \leq i \leq n) 天的面试题的难度为 s_i \in \{0,1\}，其中 s_i = 0 表示这套题的难度较高，没有人能够做出；s_i = 1 表示这套题的难度较低，所有人都能做出。小 H 会根据面试者的作答结果决定是否录用，即如果面试者没有做出面试题，则会拒绝，否则会录用。

然而，每个人的耐心都有一定的上限，如果在他面试之前未录用的人数过多，则他会直接放弃参加面试。具体地，编号为 i (1 \leq i \leq n) 的人的耐心上限可以用非负整数 c_i 描述，若在他之前已经有不少于 c_i 人被拒绝或放弃参加面试，则他也将放弃参加面试。

小 Z 想知道一共有多少种面试的顺序 p 能够让他们录用至少 m 人。你需要帮助小 Z 求出，能够录用至少 m 人的排列 p 的数量。由于答案可能较大，你只需要求出答案对 998\,244\,353 取模后的结果。

【输入格式】

输入的第一行包含两个正整数 n, m，分别表示前来应聘的人数和希望录用的人数。

输入的第二行包含一个长度为 n 的字符串 s_1 \dots s_n，表示每一天的面试题的难度。

输入的第三行包含 n 个非负整数 c_1, c_2, \dots, c_n，表示每个人的耐心上限。

【输出格式】

输出一行一个非负整数，表示能够录用至少 m 人的排列 p 的数量对 998\,244\,353 取模后的结果。

【样例 1 输入】

3 2
101
1 1 2

【样例 1 输出】

2

【样例 2 输入】

10 5
1101111011
6 0 4 2 1 2 5 4 3 3

【样例 2 输出】

2204128

【样例 1 解释】

共有以下 2 种面试的顺序 p 能够让小 Z 和小 H 录用至少 2 人:

【样例 3】

见选手目录下的 \textbf{\textit{employ/employ3.in}} 与 \textbf{\textit{employ/employ3.ans}}。

该样例满足测试点 6 ~ 8 的约束条件。

【样例 4】

见选手目录下的 \textbf{\textit{employ/employ4.in}} 与 \textbf{\textit{employ/employ4.ans}}。

该样例满足测试点 12 ~ 14 的约束条件。

【样例 5】

见选手目录下的 \textbf{\textit{employ/employ5.in}} 与 \textbf{\textit{employ/employ5.ans}}。

该样例满足测试点 18 ~ 21 的约束条件。

【数据范围】

对于所有测试数据，保证:

• 对于所有 1 \leq i \leq n，均有 s_i \in \{0,1\};
• 对于所有 1 \leq i \leq n，均有 0 \leq c_i \leq n。

::cute-table{tuack}

特殊性质 A: 对于所有 1 \leq i \leq n，均有 s_i = 1。

特殊性质 B: 在 s_1, s_2, \dots, s_n 中最多只有 18 个取值为 1，即 \sum_{i=1}^{n} s_i \leq 18。