題意

給定一個包含小寫字母和數(shù)字的字符串 s ，要求從小寫字母及數(shù)字的字符串 s 中選出任意多個數(shù)字 ，并按任意順序?qū)⑺鼈兤唇映梢粋€正整數(shù)。每個數(shù)字只能使用一次。求出所有能拼成的正整數(shù)中的最大值。

1≤∣s∣≤10⁶  

^解析

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

標(biāo)程

題意

考場共有 n 行 m 列座位，共 n×m 名考生。考生按照成績由高到低，以“蛇形”順序分配座位。蛇形分配的規(guī)則是：先從第1列第1行向下到第 ??n 行，然后轉(zhuǎn)向第2列第 n 行向上到第1行，再轉(zhuǎn)向第3列第1行向下到第 n 行，以此類推。給定考場的行數(shù) n、列數(shù) m 和所有考生的成績 a1,a2,?,an×m (其中 a1 是小R的成績)，要求確定小R的座位所在的列數(shù) c 和行數(shù)r。

解析

把數(shù)據(jù)排個序，找到a[1]所在的位次，然后將位次-1分別對行數(shù)相除和求余，除出來的就是列數(shù)，求余出來的就是行數(shù)，不過行數(shù)要根據(jù)列數(shù)的奇偶性正序或者倒序。

標(biāo)程

題意

給定一個長度為 n 的非負(fù)整數(shù)序列a1,a2,?,an 和一個非負(fù)整數(shù) k。定義一個區(qū)間[l,r] 的權(quán)值為該區(qū)間內(nèi)所有元素的二進(jìn)制按位異或和。目標(biāo)是選擇序列中盡可能多的不相交的區(qū)間，使得每個區(qū)間的權(quán)值都等于 k。

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

解析

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

于是先求出前綴異或和s，對于每個s[i]， 看能不能找到上一個出現(xiàn)的s[i]的位置last，可以就說明last+1到i構(gòu)成了一個區(qū)間，維護(hù)最后一次的右端點(diǎn)right，只要last>=right就說明形成一個新區(qū)間，線性掃一遍就可以了，O(n)

標(biāo)程

解法一

題意

有 n 根小木棍，長度分別為a1,a2,?,an。從這 n 根木棍中選出 m 根 (m≥3)，它們能拼成一個多邊形當(dāng)且僅當(dāng)所有選出木棍的長度之和大于最長木棍長度的兩倍。 要求計算出有多少種選擇小木棍的方案，使得選出的小木棍能夠拼成一個多邊形，答案對 998244353取模。

3≤n,ai≤5000

解析

簡單的01背包，先背包求出F[i][j]表示前i個數(shù)能夠湊成和為j的方案數(shù)，那么對于每個數(shù)a[i]，所有的F[i-1][0-a[i]]都是不合法的方案，把所有這樣的方案累加，最后再用2ⁿ    1減去不合法方案即可。

標(biāo)程