ARTICLE · 1278236
四道CSP-J 复赛真题,供信奥家长同学参考!
1、拼数（number）
【题目描述】
小 R 正在学习字符串处理。小 X 给了小 R 一个字符串 s，其中 s 仅包含小写英文字母及数字，且包含至少一个 1 ∼ 9 中的数字。小 X 希望小 R 使用 s 中的任意多个数字，按任意顺序拼成一个正整数。
注意：小 R 可以选择 s 中相同的数字，但每个数字只能使用一次。例如，若 s 为 1a01b，则小 R 可以同时选择第 1、3、4 个字符，分别为 1、0、1，拼成正整数 101 或 110；但小 R 不能拼成正整数 111，因为 s 仅包含两个数字 1。
小 R 想知道，在他所有能拼成的正整数中，最大的是多少。你需要帮助小 R 求出他能拼成的正整数的最大值。
【输入格式】
从文件 number.in 中读入数据。
输入的第一行包含一个字符串 s，表示小 X 给小 R 的字符串。
【输出格式】
输出到文件 number.out 中。
输出一行一个正整数，表示小 R 能拼成的正整数的最大值。
【样例 1】
输入：
5输出：
5【样例 1 解释】
s 仅包含一个数字 5，因此小 R 仅能拼成正整数 5。
【样例 2】
输入：
290es1q0输出：
92100【样例 2 解释】
s 包含数字 2、9、0、1、0。可以证明，小 R 拼成的正整数的最大值为 92100。
【数据范围】
设 |s| 为字符串 s 的长度。对于所有测试数据，保证：
1 ≤ |s| ≤ 10⁶； s 仅包含小写英文字母及数字，且包含至少一个 1 ∼ 9 中的数字。
特殊性质 A：s 仅包含数字。特殊性质 B：s 仅包含不超过 10³ 个数字。
2、座位（seat）
【题目描述】
CSP-J 2025 第二轮正在进行。小 R 所在的考场共有 n × m 名考生，其中所有考生的 CSP-J 2025 第一轮成绩互不相同。所有 n × m 名考生将按照 CSP-J 2025 第一轮的成绩，由高到低蛇形分配座位，排列成 n 行 m 列。
具体地，设小 R 所在的考场的所有考生的成绩从高到低分别为 s₁ > s₂ > · · · > s_{n×m}，则成绩为 s₁ 的考生的座位为第 1 列第 1 行，成绩为 s₂ 的考生的座位为第 1 列第 2 行，……，成绩为 sₙ 的考生的座位为第 1 列第 n 行，成绩为 s_{n+1} 的考生的座位为第 2 列第 n 行，……，成绩为 s_{2n} 的考生的座位为第 2 列第 1 行，成绩为 s_{2n+1} 的考生的座位为第 3 列第 1 行，以此类推。
也就是说：奇数列从上往下填，偶数列从下往上填，填完一列再填下一列。
给定小 R 所在的考场座位的行数 n 与列数 m，以及小 R 所在的考场的所有考生 CSP-J 2025 第一轮的成绩 a₁, a₂, . . . , a_{n×m}，其中 a₁ 为小 R 的成绩，你需要帮助小 R 求出，他的座位为第几列第几行。
【输入格式】
从文件 seat.in 中读入数据。
输入的第一行包含两个正整数 n, m，分别表示小 R 所在的考场座位的行数与列数。
输入的第二行包含 n × m 个正整数 a₁, a₂, . . . , a_{n×m}，分别表示所有考生的成绩，其中 a₁ 为小 R 的成绩。
【输出格式】
输出到文件 seat.out 中。
输出一行两个正整数 c, r，表示小 R 的座位为第 c 列第 r 行。
【样例 1】
输入：
22991009798输出：
12【样例 1 解释】
按照成绩从高到低的顺序，成绩为 100 的考生坐第 1 列第 1 行，99 坐第 1 列第 2 行，98 坐第 2 列第 2 行，97 坐第 2 列第 1 行。小 R 成绩为 99，因此座位为第 1 列第 2 行。
【样例 2】
输入：
22989910097输出：
22【样例 2 解释】
小 R 成绩为 98，排第 3 名，座位为第 2 列第 2 行。
【样例 3】
输入：
339495969798991009392输出：
31【数据范围】
对于所有测试数据，保证：
1 ≤ n ≤ 10，1 ≤ m ≤ 10； 对于所有 1 ≤ i ≤ n × m，均有 1 ≤ aᵢ ≤ 100，且 a₁, a₂, . . . , a_{n×m} 互不相同。
特殊性质 A：对于所有 1 ≤ i ≤ n × m，均有 aᵢ = i。特殊性质 B：对于所有 1 ≤ i ≤ n × m，均有 aᵢ = n × m − i + 1。
3、异或和（xor）
【题目描述】
小 R 有一个长度为 n 的非负整数序列 a₁, a₂, . . . , aₙ。定义一个区间 [l, r] (1 ≤ l ≤ r ≤ n) 的权值为 aₗ, aₗ₊₁, . . . , aᵣ 的二进制按位异或和，即 aₗ ⊕ aₗ₊₁ ⊕ · · · ⊕ aᵣ，其中 ⊕ 表示二进制按位异或。
小 X 给了小 R 一个非负整数 k。小 X 希望小 R 选择序列中尽可能多的不相交的区间，使得每个区间的权值均为 k。两个区间 [l₁, r₁]、[l₂, r₂] 相交当且仅当两个区间同时包含至少一个相同的下标。
例如，对于序列 [2, 1, 0, 3]，若 k = 2，则小 R 可以选择区间 [1, 1] 和区间 [2, 4]，权值分别为 2 和 1 ⊕ 0 ⊕ 3 = 2；若 k = 3，则小 R 可以选择区间 [1, 2] 和区间 [4, 4]，权值分别为 2 ⊕ 1 = 3 和 3。
你需要帮助小 R 求出他能选出的区间数量的最大值。
【输入格式】
从文件 xor.in 中读入数据。
输入的第一行包含两个非负整数 n, k，分别表示序列的长度和小 X 给的整数。
输入的第二行包含 n 个非负整数 a₁, a₂, . . . , aₙ，表示这个序列。
【输出格式】
输出到文件 xor.out 中。
输出一行一个非负整数，表示小 R 能选出的区间数量的最大值。
【样例 1】
输入：
422103输出：
2【样例 1 解释】
可以选区间 [1, 1] 和 [2, 4]，异或和分别为 2 和 1 ⊕ 0 ⊕ 3 = 2。最多能选 2 个。
【样例 2】
输入：
432103输出：
2【样例 2 解释】
可以选区间 [1, 2] 和 [4, 4]，异或和分别为 2 ⊕ 1 = 3 和 3。最多能选 2 个。
【样例 3】
输入：
402103输出：
1【样例 3 解释】
可以选区间 [3, 3]，异或和为 0。最多能选 1 个。注意：不能同时选 [3, 3] 和 [1, 4]，因为这两个区间都包含下标 3。
【数据范围】
对于所有测试数据，保证：
1 ≤ n ≤ 5 × 10⁵，0 ≤ k < 2²⁰； 对于所有 1 ≤ i ≤ n，均有 0 ≤ aᵢ < 2²⁰。
特殊性质 A：所有 aᵢ = 1。特殊性质 B：所有 0 ≤ aᵢ ≤ 1。特殊性质 C：所有 0 ≤ aᵢ ≤ 255。
4、多边形（polygon）
【题目描述】
小 R 喜欢玩小木棍。小 R 有 n 根小木棍，第 i (1 ≤ i ≤ n) 根小木棍的长度为 aᵢ。
小 X 希望小 R 从这 n 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：对于长度分别为 l₁, l₂, . . . , lₘ 的 m 根小木棍，这 m 根小木棍能拼成一个多边形当且仅当 m ≥ 3 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍，即
∑ᵢ₌₁ᵐ lᵢ > 2 × maxᵢ₌₁ᵐ lᵢ
由于小 R 知道了条件，小 X 提出了一个更难的问题：有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？两种方案不同当且仅当选择的小木棍的下标集合不同。由于答案可能较大，你只需要求出答案对 998244353 取模后的结果。
【输入格式】
从文件 polygon.in 中读入数据。
输入的第一行包含一个正整数 n，表示小木棍的数量。
输入的第二行包含 n 个正整数 a₁, a₂, . . . , aₙ，表示每根小木棍的长度。
【输出格式】
输出到文件 polygon.out 中。
输出一行一个非负整数，表示方案数对 998244353 取模后的结果。
【样例 1】
输入：
512345输出：
9【样例 1 解释】
共有 9 种方案：{2,3,4}、{2,4,5}、{3,4,5}、{1,2,3,4}、{1,2,3,5}、{1,2,4,5}、{1,3,4,5}、{2,3,4,5}、{1,2,3,4,5}（数字为木棍下标）。例如选第 2、3、4 根，长度和 2 + 3 + 4 = 9，最大值 4，9 > 8，成立。
【样例 2】
输入：
5223810输出：
6【样例 2 解释】
共 6 种方案：{1,2,3}、{3,4,5}、{1,2,4,5}、{1,3,4,5}、{2,3,4,5}、{1,2,3,4,5}。
【数据范围】
对于所有测试数据，保证：
3 ≤ n ≤ 5000； 对于所有 1 ≤ i ≤ n，均有 1 ≤ aᵢ ≤ 5000。
推荐阅读：
