題意

給定一個包含小寫字母和數字的字符串 s ，要求從小寫字母及數字的字符串 s 中選出任意多個數字 ，并按任意順序將它們拼接成一個正整數。每個數字只能使用一次。求出所有能拼成的正整數中的最大值。

1≤∣s∣≤10⁶  

^解析

把所有的數字找出來，放在桶里面倒序輸出，或者倒序排個序輸出都可以。

標程

題意

考場共有 n 行 m 列座位，共 n×m 名考生。考生按照成績由高到低，以“蛇形”順序分配座位。蛇形分配的規(guī)則是：先從第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。定義一個區(qū)間[l,r] 的權值為該區(qū)間內所有元素的二進制按位異或和。目標是選擇序列中盡可能多的不相交的區(qū)間，使得每個區(qū)間的權值都等于 k。

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

解析

貪心，對于每個i來說，只要能夠找到前面某一個數，使得這段區(qū)間異或和是k那么就肯定選，不然往后拖的話不會讓答案更優(yōu)。

于是先求出前綴異或和s，對于每個s[i]， 看能不能找到上一個出現(xiàn)的s[i]的位置last，可以就說明last+1到i構成了一個區(qū)間，維護最后一次的右端點right，只要last>=right就說明形成一個新區(qū)間，線性掃一遍就可以了，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減去不合法方案即可。

標程