传习Chuanxi

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

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

  • 场次：2025年11月
  • 考试时长：210 分钟
  • 满分：400 分
  • 编译选项：-O2 -std=c++14 -static
  • 题目来源：官方直发原件

注意事项（原卷照录）

考试时间：2025 年 11 月 1 日 08:30 ~ 12:00。

注意事项（请仔细阅读）

  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 下进行，各语言的编译器版本以此为准。

编程题

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

编程题

拼数

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

小 R 正在学习字符串处理。小 X 给了小 R 一个字符串 ss，其中 ss 仅包含小写英文字母及数字，且包含至少一个 1∼91 \sim 9 中的数字。小 X 希望小 R 使用 ss 中的任意多个数字，按任意顺序拼成一个正整数。注意：小 R 可以选择 ss 中相同的数字，但每个数字只能使用一次。例如，若 ss 为 1a01b，则小 R 可以同时选择第 1,3,41, 3, 4 个字符，分别为 1,0,11, 0, 1，拼成正整数 101101 或 110110；但小 R 不能拼成正整数 111111，因为 ss 仅包含两个数字 11。

小 R 想知道，在他所有能拼成的正整数中，最大的是多少。你需要帮助小 R 求出他能拼成的正整数的最大值。

输入格式

从文件 number.in 中读入数据。

输入的第一行包含一个字符串 ss，表示小 X 给小 R 的字符串。

输出格式

输出到文件 number.out 中。

输出一行一个正整数，表示小 R 能拼成的正整数的最大值。

样例

输入 1
5
输出 1
5

ss 仅包含一个数字 55，因此小 R 仅能拼成正整数 55。

输入 2
290es1q0
输出 2
92100

ss 包含数字 2,9,0,1,02, 9, 0, 1, 0。可以证明，小 R 拼成的正整数的最大值为 9210092100。

数据范围

设 ∣s∣|s| 为字符串 ss 的长度。对于所有测试数据，保证：

  • 1≤∣s∣≤1061 \le |s| \le 10^6；
  • ss 仅包含小写英文字母及数字，且包含至少一个 1∼91 \sim 9 中的数字。
测试点编号 ∣s∣≤\vert s \vert \le 特殊性质
11 11 A
22 22 A
33 22 无
44 1010 A
5,65, 6 1010 无
7,87, 8 10210^2 A
9∼119 \sim 11 10210^2 无
1212 10310^3 A
13,1413, 14 10310^3 无
1515 10510^5 A
16,1716, 17 10510^5 B
18,1918, 19 10510^5 无
2020 10610^6 A
21,2221, 22 10610^6 B
23∼2523 \sim 25 10610^6 无

特殊性质 A：ss 仅包含数字。

特殊性质 B：ss 仅包含不超过 10310^3 个数字。

部分分

  • 4 分

    测试点 11：∣s∣≤1|s| \le 1，特殊性质 A。

  • 4 分

    测试点 22：∣s∣≤2|s| \le 2，特殊性质 A。

  • 4 分

    测试点 33：∣s∣≤2|s| \le 2，无特殊性质。

  • 4 分

    测试点 44：∣s∣≤10|s| \le 10，特殊性质 A。

  • 8 分

    测试点 5,65, 6：∣s∣≤10|s| \le 10，无特殊性质。

  • 8 分

    测试点 7,87, 8：∣s∣≤102|s| \le 10^2，特殊性质 A。

  • 12 分

    测试点 9∼119 \sim 11：∣s∣≤102|s| \le 10^2，无特殊性质。

  • 4 分

    测试点 1212：∣s∣≤103|s| \le 10^3，特殊性质 A。

  • 8 分

    测试点 13,1413, 14：∣s∣≤103|s| \le 10^3，无特殊性质。

  • 4 分

    测试点 1515：∣s∣≤105|s| \le 10^5，特殊性质 A。

  • 8 分

    测试点 16,1716, 17：∣s∣≤105|s| \le 10^5，特殊性质 B。

  • 8 分

    测试点 18,1918, 19：∣s∣≤105|s| \le 10^5，无特殊性质。

  • 4 分

    测试点 2020：∣s∣≤106|s| \le 10^6，特殊性质 A。

  • 8 分

    测试点 21,2221, 22：∣s∣≤106|s| \le 10^6，特殊性质 B。

  • 12 分

    测试点 23∼2523 \sim 25：∣s∣≤106|s| \le 10^6，无特殊性质。

你的代码（C++）

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

76 B / 64 KB

判题结果

编程题

座位

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

CSP-J 2025 第二轮正在进行。小 R 所在的考场共有 n×mn \times m 名考生，其中所有考生的 CSP-J 2025 第一轮成绩互不相同。所有 n×mn \times m 名考生将按照 CSP-J 2025 第一轮的成绩，由高到低蛇形分配座位，排列成 nn 行 mm 列。具体地，设小 R 所在的考场的所有考生的成绩从高到低分别为 s1>s2>⋯>sn×ms_1 > s_2 > \cdots > s_{n \times m}，则成绩为 s1s_1 的考生的座位为第 11 列第 11 行，成绩为 s2s_2 的考生的座位为第 11 列第 22 行，……，成绩为 sns_n 的考生的座位为第 11 列第 nn 行，成绩为 sn+1s_{n+1} 的考生的座位为第 22 列第 nn 行，……，成绩为 s2ns_{2n} 的考生的座位为第 22 列第 11 行，成绩为 s2n+1s_{2n+1} 的考生的座位为第 33 列第 11 行，以此类推。

例如，若 n=4n = 4，m=5m = 5，则所有 4×5=204 \times 5 = 20 名考生将按照 CSP-J 2025 第一轮成绩从高到低的顺序，根据下图中的箭头顺序蛇形分配座位。

座位蛇形分配示意图

给定小 R 所在的考场座位的行数 nn 与列数 mm，以及小 R 所在的考场的所有考生 CSP-J 2025 第一轮的成绩 a1,a2,…,an×ma_1, a_2, \ldots, a_{n \times m}，其中 a1a_1 为小 R CSP-J 2025 第一轮的成绩，你需要帮助小 R 求出，他的座位为第几列第几行。

输入格式

从文件 seat.in 中读入数据。

输入的第一行包含两个正整数 n,mn, m，分别表示小 R 所在的考场座位的行数与列数。

输入的第二行包含 n×mn \times m 个正整数 a1,a2,…,an×ma_1, a_2, \ldots, a_{n \times m}，分别表示小 R 所在的考场的所有考生 CSP-J 2025 第一轮的成绩，其中 a1a_1 为小 R CSP-J 2025 第一轮的成绩。

输出格式

输出到文件 seat.out 中。

输出一行两个正整数 c,rc, r，表示小 R 的座位为第 cc 列第 rr 行。

样例

输入 1
2 2
99 100 97 98
输出 1
1 2

按照成绩从高到低的顺序，成绩为 100100 的考生的座位为第 11 列第 11 行，成绩为 9999 的考生的座位为第 11 列第 22 行，成绩为 9898 的考生的座位为第 22 列第 22 行，成绩为 9797 的考生的座位为第 22 列第 11 行。小 R 的成绩为 9999，因此座位为第 11 列第 22 行。

输入 2
2 2
98 99 100 97
输出 2
2 2

按照成绩从高到低的顺序，成绩为 100100 的考生的座位为第 11 列第 11 行，成绩为 9999 的考生的座位为第 11 列第 22 行，成绩为 9898 的考生的座位为第 22 列第 22 行，成绩为 9797 的考生的座位为第 22 列第 11 行。小 R 的成绩为 9898，因此座位为第 22 列第 22 行。

输入 3
3 3
94 95 96 97 98 99 100 93 92
输出 3
3 1

数据范围

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

  • 1≤n≤101 \le n \le 10，1≤m≤101 \le m \le 10；
  • 对于所有 1≤i≤n×m1 \le i \le n \times m，均有 1≤ai≤1001 \le a_i \le 100，且 a1,a2,…,an×ma_1, a_2, \ldots, a_{n \times m} 互不相同。
测试点编号 n≤n \le m≤m \le 特殊性质
11 11 11 AB
2,32, 3 11 1010 无
4,54, 5 1010 11 无
66 22 22 A
77 22 22 B
8,98, 9 22 22 无
1010 22 1010 A
1111 22 1010 B
12∼1412 \sim 14 22 1010 无
15∼1715 \sim 17 1010 22 无
18∼2018 \sim 20 1010 1010 无

特殊性质 A：对于所有 1≤i≤n×m1 \le i \le n \times m，均有 ai=ia_i = i。

特殊性质 B：对于所有 1≤i≤n×m1 \le i \le n \times m，均有 ai=n×m−i+1a_i = n \times m - i + 1。

部分分

  • 5 分

    测试点 11：n≤1n \le 1，m≤1m \le 1，特殊性质 A、B。

  • 10 分

    测试点 2,32, 3：n≤1n \le 1，m≤10m \le 10，无特殊性质。

  • 10 分

    测试点 4,54, 5：n≤10n \le 10，m≤1m \le 1，无特殊性质。

  • 5 分

    测试点 66：n≤2n \le 2，m≤2m \le 2，特殊性质 A。

  • 5 分

    测试点 77：n≤2n \le 2，m≤2m \le 2，特殊性质 B。

  • 10 分

    测试点 8,98, 9：n≤2n \le 2，m≤2m \le 2，无特殊性质。

  • 5 分

    测试点 1010：n≤2n \le 2，m≤10m \le 10，特殊性质 A。

  • 5 分

    测试点 1111：n≤2n \le 2，m≤10m \le 10，特殊性质 B。

  • 15 分

    测试点 12∼1412 \sim 14：n≤2n \le 2，m≤10m \le 10，无特殊性质。

  • 15 分

    测试点 15∼1715 \sim 17：n≤10n \le 10，m≤2m \le 2，无特殊性质。

  • 15 分

    测试点 18∼2018 \sim 20：n≤10n \le 10，m≤10m \le 10，无特殊性质。

你的代码（C++）

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

76 B / 64 KB

判题结果

编程题

异或和

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

小 R 有一个长度为 nn 的非负整数序列 a1,a2,…,ana_1, a_2, \ldots, a_n。定义一个区间 [l,r][l, r] (1≤l≤r≤n)(1 \le l \le r \le n) 的权值为 al,al+1,…,ara_l, a_{l+1}, \ldots, a_r 的二进制按位异或和，即 al⊕al+1⊕⋯⊕ara_l \oplus a_{l+1} \oplus \cdots \oplus a_r，其中 ⊕\oplus 表示二进制按位异或。

小 X 给了小 R 一个非负整数 kk。小 X 希望小 R 选择序列中尽可能多的不相交的区间，使得每个区间的权值均为 kk。两个区间 [l1,r1],[l2,r2][l_1, r_1], [l_2, r_2] 相交当且仅当两个区间同时包含至少一个相同的下标，即存在 1≤i≤n1 \le i \le n 使得 l1≤i≤r1l_1 \le i \le r_1 且 l2≤i≤r2l_2 \le i \le r_2。

例如，对于序列 [2,1,0,3][2, 1, 0, 3]，若 k=2k = 2，则小 R 可以选择区间 [1,1][1, 1] 和区间 [2,4][2, 4]，权值分别为 22 和 1⊕0⊕3=21 \oplus 0 \oplus 3 = 2；若 k=3k = 3，则小 R 可以选择区间 [1,2][1, 2] 和区间 [4,4][4, 4]，权值分别为 1⊕2=31 \oplus 2 = 3 和 33。

你需要帮助小 R 求出他能选出的区间数量的最大值。

输入格式

从文件 xor.in 中读入数据。

输入的第一行包含两个非负整数 n,kn, k，分别表示小 R 的序列长度和小 X 给小 R 的非负整数。

输入的第二行包含 nn 个非负整数 a1,a2,…,ana_1, a_2, \ldots, a_n，表示小 R 的序列。

输出格式

输出到文件 xor.out 中。

输出一行一个非负整数，表示小 R 能选出的区间数量的最大值。

样例

输入 1
4 2
2 1 0 3
输出 1
2

小 R 可以选择区间 [1,1][1, 1] 和区间 [2,4][2, 4]，异或和分别为 22 和 1⊕0⊕3=21 \oplus 0 \oplus 3 = 2。可以证明，小 R 能选出的区间数量的最大值为 22。

输入 2
4 3
2 1 0 3
输出 2
2

小 R 可以选择区间 [1,2][1, 2] 和区间 [4,4][4, 4]，异或和分别为 1⊕2=31 \oplus 2 = 3 和 33。可以证明，小 R 能选出的区间数量的最大值为 22。

输入 3
4 0
2 1 0 3
输出 3
1

小 R 可以选择区间 [3,3][3, 3]，异或和为 00。可以证明，小 R 能选出的区间数量的最大值为 11。注意：小 R 不能同时选择区间 [3,3][3, 3] 和区间 [1,4][1, 4]，因为这两个区间同时包含下标 33。

数据范围

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

  • 1≤n≤5×1051 \le n \le 5 \times 10^5，0≤k<2200 \le k < 2^{20}；
  • 对于所有 1≤i≤n1 \le i \le n，均有 0≤ai<2200 \le a_i < 2^{20}。
测试点编号 n≤n \le kk 特殊性质
11 22 =0= 0 A
22 1010 ≤1\le 1 B
33 10210^2 =0= 0 A
4,54, 5 10210^2 ≤1\le 1 B
6∼86 \sim 8 10210^2 ≤255\le 255 C
9,109, 10 10310^3 ≤255\le 255 C
11,1211, 12 10310^3 <220< 2^{20} 无
1313 2×1052 \times 10^5 ≤1\le 1 B
14,1514, 15 2×1052 \times 10^5 ≤255\le 255 C
1616 2×1052 \times 10^5 <220< 2^{20} 无
1717 5×1055 \times 10^5 ≤255\le 255 C
18∼2018 \sim 20 5×1055 \times 10^5 <220< 2^{20} 无

特殊性质 A：对于所有 1≤i≤n1 \le i \le n，均有 ai=1a_i = 1。

特殊性质 B：对于所有 1≤i≤n1 \le i \le n，均有 0≤ai≤10 \le a_i \le 1。

特殊性质 C：对于所有 1≤i≤n1 \le i \le n，均有 0≤ai≤2550 \le a_i \le 255。

部分分

  • 5 分

    测试点 11：n≤2n \le 2，k=0k = 0，特殊性质 A。

  • 5 分

    测试点 22：n≤10n \le 10，k≤1k \le 1，特殊性质 B。

  • 5 分

    测试点 33：n≤102n \le 10^2，k=0k = 0，特殊性质 A。

  • 10 分

    测试点 4,54, 5：n≤102n \le 10^2，k≤1k \le 1，特殊性质 B。

  • 15 分

    测试点 6∼86 \sim 8：n≤102n \le 10^2，k≤255k \le 255，特殊性质 C。

  • 10 分

    测试点 9,109, 10：n≤103n \le 10^3，k≤255k \le 255，特殊性质 C。

  • 10 分

    测试点 11,1211, 12：n≤103n \le 10^3，k<220k < 2^{20}，无特殊性质。

  • 5 分

    测试点 1313：n≤2×105n \le 2 \times 10^5，k≤1k \le 1，特殊性质 B。

  • 10 分

    测试点 14,1514, 15：n≤2×105n \le 2 \times 10^5，k≤255k \le 255，特殊性质 C。

  • 5 分

    测试点 1616：n≤2×105n \le 2 \times 10^5，k<220k < 2^{20}，无特殊性质。

  • 5 分

    测试点 1717：n≤5×105n \le 5 \times 10^5，k≤255k \le 255，特殊性质 C。

  • 15 分

    测试点 18∼2018 \sim 20：n≤5×105n \le 5 \times 10^5，k<220k < 2^{20}，无特殊性质。

你的代码（C++）

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

76 B / 64 KB

判题结果

编程题

多边形

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

小 R 喜欢玩小木棍。小 R 有 nn 根小木棍，第 ii (1≤i≤n)(1 \le i \le n) 根小木棍的长度为 aia_i。

小 X 希望小 R 从这 nn 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：对于长度分别为 l1,l2,…,lml_1, l_2, \ldots, l_m 的 mm 根小木棍，这 mm 根小木棍能拼成一个多边形当且仅当 m≥3m \ge 3 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍，即 ∑i=1mli>2×max⁡i=1mli\sum_{i=1}^{m} l_i > 2 \times \max_{i=1}^{m} l_i。

由于小 R 知道了小木棍能拼成多边形的条件，小 X 提出了一个更难的问题：有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？你需要帮助小 R 求出选出的小木棍能够拼成一个多边形的方案数。两种方案不同当且仅当选择的小木棍的下标集合不同，即存在 1≤i≤n1 \le i \le n，使得其中一种方案选择了第 ii 根小木棍，但另一种方案未选择。由于答案可能较大，你只需要求出答案对 998,244,353998,244,353 取模后的结果。

输入格式

从文件 polygon.in 中读入数据。

输入的第一行包含一个正整数 nn，表示小 R 的小木棍的数量。

输入的第二行包含 nn 个正整数 a1,a2,…,ana_1, a_2, \ldots, a_n，表示小 R 的小木棍的长度。

输出格式

输出到文件 polygon.out 中。

输出一行一个非负整数，表示小 R 选出的小木棍能够拼成一个多边形的方案数对 998,244,353998,244,353 取模后的结果。

样例

输入 1
5
1 2 3 4 5
输出 1
9

共有以下 99 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：

  1. 选择第 2,3,42, 3, 4 根小木棍，长度之和为 2+3+4=92 + 3 + 4 = 9，长度最大值为 44；
  2. 选择第 2,4,52, 4, 5 根小木棍，长度之和为 2+4+5=112 + 4 + 5 = 11，长度最大值为 55；
  3. 选择第 3,4,53, 4, 5 根小木棍，长度之和为 3+4+5=123 + 4 + 5 = 12，长度最大值为 55；
  4. 选择第 1,2,3,41, 2, 3, 4 根小木棍，长度之和为 1+2+3+4=101 + 2 + 3 + 4 = 10，长度最大值为 44；
  5. 选择第 1,2,3,51, 2, 3, 5 根小木棍，长度之和为 1+2+3+5=111 + 2 + 3 + 5 = 11，长度最大值为 55；
  6. 选择第 1,2,4,51, 2, 4, 5 根小木棍，长度之和为 1+2+4+5=121 + 2 + 4 + 5 = 12，长度最大值为 55；
  7. 选择第 1,3,4,51, 3, 4, 5 根小木棍，长度之和为 1+3+4+5=131 + 3 + 4 + 5 = 13，长度最大值为 55；
  8. 选择第 2,3,4,52, 3, 4, 5 根小木棍，长度之和为 2+3+4+5=142 + 3 + 4 + 5 = 14，长度最大值为 55；
  9. 选择第 1,2,3,4,51, 2, 3, 4, 5 根小木棍，长度之和为 1+2+3+4+5=151 + 2 + 3 + 4 + 5 = 15，长度最大值为 55。
输入 2
5
2 2 3 8 10
输出 2
6

共有以下 66 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：

  1. 选择第 1,2,31, 2, 3 根小木棍，长度之和为 2+2+3=72 + 2 + 3 = 7，长度最大值为 33；
  2. 选择第 3,4,53, 4, 5 根小木棍，长度之和为 3+8+10=213 + 8 + 10 = 21，长度最大值为 1010；
  3. 选择第 1,2,4,51, 2, 4, 5 根小木棍，长度之和为 2+2+8+10=222 + 2 + 8 + 10 = 22，长度最大值为 1010；
  4. 选择第 1,3,4,51, 3, 4, 5 根小木棍，长度之和为 2+3+8+10=232 + 3 + 8 + 10 = 23，长度最大值为 1010；
  5. 选择第 2,3,4,52, 3, 4, 5 根小木棍，长度之和为 2+3+8+10=232 + 3 + 8 + 10 = 23，长度最大值为 1010；
  6. 选择第 1,2,3,4,51, 2, 3, 4, 5 根小木棍，长度之和为 2+2+3+8+10=252 + 2 + 3 + 8 + 10 = 25，长度最大值为 1010。

数据范围

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

  • 3≤n≤5,0003 \le n \le 5,000；
  • 对于所有 1≤i≤n1 \le i \le n，均有 1≤ai≤5,0001 \le a_i \le 5,000。
测试点编号 n≤n \le max⁡i=1nai≤\max_{i=1}^{n} a_i \le
1∼31 \sim 3 33 1010
4∼64 \sim 6 1010 10210^2
7∼107 \sim 10 2020 10210^2
11∼1411 \sim 14 500500 10210^2
15∼1715 \sim 17 500500 11
18∼2018 \sim 20 5,0005,000 11
21∼2521 \sim 25 5,0005,000 5,0005,000

部分分

  • 12 分

    测试点 1∼31 \sim 3：n≤3n \le 3，max⁡i=1nai≤10\max_{i=1}^{n} a_i \le 10。

  • 12 分

    测试点 4∼64 \sim 6：n≤10n \le 10，max⁡i=1nai≤102\max_{i=1}^{n} a_i \le 10^2。

  • 16 分

    测试点 7∼107 \sim 10：n≤20n \le 20，max⁡i=1nai≤102\max_{i=1}^{n} a_i \le 10^2。

  • 16 分

    测试点 11∼1411 \sim 14：n≤500n \le 500，max⁡i=1nai≤102\max_{i=1}^{n} a_i \le 10^2。

  • 12 分

    测试点 15∼1715 \sim 17：n≤500n \le 500，max⁡i=1nai≤1\max_{i=1}^{n} a_i \le 1。

  • 12 分

    测试点 18∼2018 \sim 20：n≤5,000n \le 5,000，max⁡i=1nai≤1\max_{i=1}^{n} a_i \le 1。

  • 20 分

    测试点 21∼2521 \sim 25：n≤5,000n \le 5,000，max⁡i=1nai≤5,000\max_{i=1}^{n} a_i \le 5,000。

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

  • 原卷印刷如此其它数据范围

    原卷作 | $15 \sim 17$ | $500$ | $1$ |

    原卷测试点表中该档 max a_i 上界印作单独一个 1（原件第 13 页，900 dpi 复核确认无上标、无千分位，文本层同样只有 1）。上界存疑但不与整体范围矛盾（所有木棍长度均为 1 时拼成条件退化为 m>2，是自洽的纯组合特例档），照录不改；下游不得据此改写为 10^3 / 1,000。

  • 原卷印刷如此其它数据范围

    原卷作 | $18 \sim 20$ | $5,000$ | $1$ |

    同上：该档 max a_i 上界亦印作单独一个 1，照录不改。

你的代码（C++）

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

76 B / 64 KB

判题结果