T1：P14357 [CSP-J 2025] 拼数 / NUMBER（民间数据）
题意
给定一个包含小写字母和数字的字符串 sss，要求从小写字母及数字的字符串 sss 中选出任意多个数字 ，并按任意顺序将它们拼接成一个正整数。每个数字只能使用一次。求出所有能拼成的正整数中的最大值。
1≤∣s∣≤1061 \le|s|\le10^61≤∣s∣≤106
解析：以发现，最终数字的最高位越大，这个数就越大，因而只需挑出字符串中的所有数字，再按大小降序排序即可。
答案：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2：P14358 [CSP-J 2025] 座位 / SEAT（民间数据）
题意：
考场共有 nnn 行 mmm 列座位，共有 共 n×mn × mn×m名考生。考生按照成绩由高到低，以“蛇形”顺序分配座位。蛇形分配的规则是：先从第1列第1行向下到第 nnn 行，然后转向第2列第 nnn 行向上到第1行，再转向第3列第1行向下到第 nnn 行，以此类推。给定考场的行数 nnn 、列数 mmm 和所有考生的成绩 a1a_{1}a1 ， a2a_{2}a2 ，…… ， an×ma_{n × m}an×m （其中a_{1}是小R的成绩)，要求确定小R的座位所在的列数 ccc 和行数 rrr
1≤n,m≤101≤n,m≤101≤n,m≤10
解析：
根据其他同学的成绩，可以很轻松的求出小 R 的排名（统计有多少人分数不小于他即可）。假设小 R 排名为 x，则他将位于第 (x−1)/n+1(x - 1) / n + 1(x−1)/n+1 列，第 (x−1)取余n+1(x - 1) 取余 n + 1(x−1)取余n+1 ， 当行数为奇数时，恰位于 (x−1)取余n+1(x - 1) 取余 n + 1(x−1)取余n+1 行，否则将位于第 m−(x−1)取余nm - (x - 1) 取余 nm−(x−1)取余n 行。分类讨论得出答案。
答案
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3：P14359 [CSP-J 2025] 异或和 / XOR（官方数据）
题意
给定一个长度为 nnn 的非负整数序列 a1，a2，……，ana_{1}，a_{2}，……，a_{n}a1 ，a2 ，……，an 和一个非负整数 kkk。定义一个区间 [l,r][l,r][l,r] 的权值为该区间内所有元素的二进制按位异或和。目标是选择序列中尽可能多的不相交的区间，使得每个区间的权值都等于 kkk。
解析
####思路1
令前缀异或和 Sx=a1⊕a2⊕…⊕axS_{x} = a_{1} ⊕ a_{2} ⊕ … ⊕ a_{x}Sx =a1 ⊕a2 ⊕…⊕ax ，则区间 [l,r][l,r][l,r] 异或和可以表示为 Sr⊕Sl−1S_{r} ⊕ S_{l -1}Sr ⊕Sl−1 。则在右端点固定为 RRR 时，找到任意满足 Sl−1=R⊕KS_{l - 1} = R ⊕ KSl−1 =R⊕K 的 lll 等同于为一合法区间，为使区间长度尽可能小，我们选择最大的合法 lll。可以维护 posxpos_{x}posx 表示前缀中满足 sy=xs_{y} = xsy =x 的最大的 yyy。在记动态规划状态
fxf_xfx 表示前 xxx 个数中的最大和发区间数，则有动态规划转移方程
fff 中的最大值即为答案。
思路2
前半部分推导同解法一，随后，我们考虑使用贪心法，我们要取出足够多的区间，假设我们最终取出了若干个不交区间作为答案集合，那么考虑这个答案里的最左边的集合，它的右端点一定是越靠左越好，将这个最左边的区间取出来之后，相当于我们无法再取任何左侧的点了，那么在剩下的部分中，我们依然是取一个越靠左越好的区间。因此，我们的做法就可以是，从左到右按顺序扫描，每次一旦发现一个合法的区间，就直接取出来，并让答案+1，之后再取区间只能取当前这个点右侧的区间，一直取到最后没有合法区间为止，就能得到答案。判断合法区间的方式就是判断 posxpos_{x}posx 是否在上一次取的区间右端点的右侧即可。
答案
思路1
思路2
T4：P14360 [CSP-J 2025] 多边形 / POLYGON（官方数据）
题意
有 nnn 根小木棍，长度分别为 a1,a2,⋯,ana_{1} , a_{2} , ⋯ , a_{n}a1 ,a2 ,⋯,an 。从这 nnn 根木棍中选出 mmm 根 ( m≥3m≥3m≥3 )，它们能拼成一个多边形当且仅当所有选出木棍的长度之和大于最长木棍长度的两倍。 要求计算出有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形，答案对 998244353998244353998244353 取模
解析
不妨将所有给定木棍根据其长度 aia_{i}ai 排序，假设第 iii 根木棍被选择且其长度最大，则需要在前 i−1i-1i−1 根木棍中选取部分，使选择的木棍长度和大于 aia_{i}ai ，这个无法直接求，不过我们可以考虑求其补集。即在前 i−1i-1i−1 根木棍中选取部分，使其长度和小于等于 aia_{i}ai 。 这一转换后的问题显然可以用动态规划处理，记 dpi,jdp_{i,j}dpi,j 表示前 iii 根木棍中选取若干，使其长度和为 jjj 的方案数，有 dpi,j=dpi−1,j+dpi−1,j−aidp_{i,j} = dp_{i - 1 , j} + dp_{i - 1
, j - a_{i}}dpi,j =dpi−1,j +dpi−1,j−ai 注意 ai>ja_{i} > jai >j 时，后一项视为0.最后用所用的所有选取方案数减去 2n2^n2n 减去不合法的部分即可
答案
