题意

给定一个包含小写字母和数字的字符串 s ，要求从小写字母及数字的字符串 s 中选出任意多个数字 ，并按任意顺序将它们拼接成一个正整数。每个数字只能使用一次。求出所有能拼成的正整数中的最大值。

1≤∣s∣≤10⁶  

^解析

把所有的数字找出来，放在桶里面倒序输出，或者倒序排个序输出都可以。

标程

题意

考场共有 n 行 m 列座位，共 n×m 名考生。考生按照成绩由高到低，以“蛇形”顺序分配座位。蛇形分配的规则是：先从第1列第1行向下到第 𝑛n 行，然后转向第2列第 n 行向上到第1行，再转向第3列第1行向下到第 n 行，以此类推。给定考场的行数 n、列数 m 和所有考生的成绩 a1,a2,⋯,an×m (其中 a1 是小R的成绩)，要求确定小R的座位所在的列数 c 和行数r。

解析

把数据排个序，找到a[1]所在的位次，然后将位次-1分别对行数相除和求余，除出来的就是列数，求余出来的就是行数，不过行数要根据列数的奇偶性正序或者倒序。

标程

题意

给定一个长度为 n 的非负整数序列a1,a2,⋯,an 和一个非负整数 k。定义一个区间[l,r] 的权值为该区间内所有元素的二进制按位异或和。目标是选择序列中尽可能多的不相交的区间，使得每个区间的权值都等于 k。

1≤n≤5×10⁵ 0≤k, ai<2²⁰

解析

贪心，对于每个i来说，只要能够找到前面某一个数，使得这段区间异或和是k那么就肯定选，不然往后拖的话不会让答案更优。

于是先求出前缀异或和s，对于每个s[i]， 看能不能找到上一个出现的s[i]的位置last，可以就说明last+1到i构成了一个区间，维护最后一次的右端点right，只要last>=right就说明形成一个新区间，线性扫一遍就可以了，O(n)

标程

解法一

题意

有 n 根小木棍，长度分别为a1,a2,⋯,an。从这 n 根木棍中选出 m 根 (m≥3)，它们能拼成一个多边形当且仅当所有选出木棍的长度之和大于最长木棍长度的两倍。 要求计算出有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形，答案对 998244353取模。

3≤n,ai≤5000

解析

简单的01背包，先背包求出F[i][j]表示前i个数能够凑成和为j的方案数，那么对于每个数a[i]，所有的F[i-1][0-a[i]]都是不合法的方案，把所有这样的方案累加，最后再用2ⁿ    1减去不合法方案即可。

标程