2025年CSP-J2复赛试题
__SECTIONS__:[{"name": "编程题", "count": 4}] 从PDF导入：2025年CSP-J2复赛试题
试卷题目预览
拼数（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 求出他能拼成的正整数的最大值。
输入的第一行包含一个字符串 s，表示小 X 给小 R 的字符串。
输出一行一个正整数，表示小 R 能拼成的正整数的最大值。
5 290es1q0
5 92100
座位（seat）
CSP-J 2025 第二轮正在进行。小 R 所在的考场共有 n × m 名考生，其中所有考生的 CSP-J 2025 第一轮成绩互不相同。所有 n × m 名考生将按照 CSP-J 2025 第一轮的成绩，由高到低蛇形分配座位，排列成 n 行 m 列。
具体地，设小 R 所在的考场的所有考生的成绩从高到低分别为 s₁ > s₂ > ⋯ > sn×m，则成绩为 s₁ 的考生的座位为第 1 列第 1 行，成绩为 s₂ 的考生的座位为第 1 列第 2 行，……，成绩为 sn 的考生的座位为第 1 列第 n 行，成绩为 sn+1 的考生的座位为第 2 列第 n 行，……，成绩为 s2n 的考生的座位为第 2 列第 1 行，成绩为 s2n+1 的考生的座位为第 3 列第 1 行，以此类推。
例如，若 n = 4, m = 5，则所有 4 × 5 = 20 名考生将按照 CSP-J 2025 第一轮成绩从高到低的顺序，根据蛇形顺序分配座位。
给定小 R 所在的考场座位的行数 n 与列数 m，以及小 R 所在的考场的所有考生 CSP-J 2025 第一轮的成绩 a₁, a₂, ⋯, an×m，其中 a₁ 为小 R CSP-J 2025 第一轮的成绩，你需要帮助小 R 求出，他的座位为第几列第几行。
输入的第一行包含两个正整数 n, m，分别表示小 R 所在的考场座位的行数与列数。 输入的第二行包含 n × m 个正整数 a₁, a₂, ⋯, an×m，分别表示小 R 所在的考场的所有考生 CSP-J 2025 第一轮的成绩，其中 a₁ 为小 R CSP-J 2025 第一轮的成绩。
输出一行两个正整数 c, r，表示小 R 的座位为第 c 列第 r 行。
2 2 99 100 97 98 2 2 98 99 100 97 3 3 94 95 96 97 98 99 100 93 92
1 2 2 2 3 1
异或和（xor）
小 R 有一个长度为 n 的非负整数序列 a₁, a₂, ⋯, an。定义一个区间 [l, r] (1 ≤ l ≤ r ≤ n) 的权值为 al, al+1, ⋯, ar 的二进制按位异或和，即 al ⊕ al+1 ⊕ ⋯ ⊕ ar，其中 ⊕ 表示二进制按位异或。
小 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 求出他能选出的区间数量的最大值。
输入的第一行包含两个非负整数 n, k，分别表示小 R 的序列长度和小 X 给小 R 的非负整数。 输入的第二行包含 n 个非负整数 a₁, a₂, ⋯, an，表示小 R 的序列。
输出一行一个非负整数，表示小 R 能选出的区间数量的最大值。
4 2 2 1 0 3 4 3 2 1 0 3 4 0 2 1 0 3
2 2 1
多边形（polygon）
小 R 喜欢玩小木棍。小 R 有 n 根小木棍，第 i (1 ≤ i ≤ n) 根小木棍的长度为 ai。
小 X 希望小 R 从这 n 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：对于长度分别为 l₁, l₂, ⋯, lm 的 m 根小木棍，这 m 根小木棍能拼成一个多边形当且仅当 m ≥ 3 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍。
由于小 R 知道了小木棍能拼成多边形的条件，小 X 提出了一个更难的问题：有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？你需要帮助小 R 求出选出的小木棍能够拼成一个多边形的方案数。
两种方案不同当且仅当选择的小木棍的下标集合不同。由于答案可能较大，你只需要求出答案对 998,244,353 取模后的结果。
输入的第一行包含一个正整数 n，表示小 R 的小木棍的数量。 输入的第二行包含 n 个正整数 a₁, a₂, ⋯, an，表示小 R 的小木棍的长度。
输出一行一个非负整数，表示小 R 选出的小木棍能够拼成一个多边形的方案数对 998,244,353 取模后的结果。
5 1 2 3 4 5 5 2 2 3 8 10
9 6