2026 Summer Day24

415pts/600pts 因为没有交上爆零直接爆炸

前两题比较简单，就不写了。

C - 终究还是一场梦

题目链接

显然最优策略是第 $i$ 次操作把当前未归位的数字归位，用链表维护一下前后位置关系和删除即可。复杂度 $O(n)$。

D - 大家会再次相遇吗

题目链接

给定一个十进制数字串，问其中有几个不包含前导零的子串的值为 $2$ 的非负整数幂次。多组数据。

赛时直接 $O(n^2)$ 暴力，本来加高精度可以拿更多分的，但是来不及了。只有 $15pts$。

发现题解是什么玩意，乱搞做法。通过惊人的注意力可以发现，随机字符串中存在的 $2$ 的非负整数次幂数量特别少。所以我们可以设定阈值 $lim$，只检查所有长度 $< lim$ 的子串，可以通过暴力和特殊性质。

正解同样是考虑限制长度阈值 $lim$，对于长度 $> lim$ 的子串依然使用惊人的注意力发现：

$2^k \bmod 10^t$ 存在周期 $P = 4 \times 5^{t-1}$

所以只需要考查当前子串的最后 $l$ 位，通过周期性就可以知道这个二进制字符串的形态，然后做字符串匹配即可。

E - 大家仍会记得我吗

题目链接

发现如果直接做二进制优化的多重背包会爆炸，因为还有 每取 $l_i$ 个 $i$ 可以额外获得 $b_i$ 的收益，所以考虑将每个卡牌拆成 $(l_i \times p_i, l_i \times v_i, l_i \times s_i + b_i, \lfloor \frac{c_i}{l_i} \rfloor - 1)$ 和 $(p_i, v_i, s_i, c_i \bmod l_i + l_i)$ 两种卡牌，然后对第一类做多重背包，第二种需要特殊考虑。

对于第二种，考虑取不取 $l_i$，有两个转移：

• 强制钦定选 $l_i$，对剩下的 $c_i \bmod l_i$ 做多重背包。

• 选 $< l_i$ 个，以 $l_i - 1$ 为数量做多重背包。

复杂度 $O(nmk \log \max(m, k))$，可以过