CF1935 A-C题解

A

设 \(s\) 翻转后的字符串为 \(t\)，考虑进行 \(n\) 次操作可能生成出哪些字符串：

1. 只进行翻转操作——\(s\)；
2. 先复制再 \(n-1\) 次翻转——\(s+t\)；
3. 先翻转，再复制，再翻转 \(n-2\) 次，\(t+s\)；
4. 多次复制的情况。

情况 2 显然劣于情况 1；情况 4 得到的字符串的开头一定是 \(s\) 或者 \(t\)，分别劣于情况 1,3。所以答案一定在情况 1,3 中选择——不难发现，如果 \(s\) 字典序小于 \(t\)，答案是情况 1 的 \(s\)，否则答案是情况 3 的 \(t+s\)。

B

不难发现，但凡能分成多段，一定可以分成两段。分成两段，朴素的想法是枚举分界点，对两段分别求 mex。恰好前缀 mex 可以 \(O(n)\) 求，故求出前缀 mex \(pre_i\) 和后缀 mex \(suf_i\)，枚举找到到 \(pre_i=suf_{i+1}\) 位置即可。

求前缀 mex：开 bool 数组 \(v\) 和 mex 指针 \(p\)。遍历到 \(a_i\) 时将 \(v_{a_i}\) 设为 true，并将 \(p\) 向后移动到 \(v_i\) 为 false 的位置，\(pre_i\gets p\)。在不断添加 \(a_i\) 的过程中，\(p\) 一定单调递增，复杂度为 \(O(n)\)。

C

重要性质：如果将信息按照 \(b_i\) 排序，在选定了最小的 \(b_l\) 和最大的 \(b_r\) 的情况下，我们任选 \(l<i<r\) 都不会对式子关于 \(b_i\) 的部分产生影响，只需要考虑含 \(a_i\) 的部分即可。

一个显然的想法是枚举 \(l,r\)，然后对 \(i\in [l,r]\) 的 \(a_i\) 排序，贪心地从小到大选取，使总和不超过 \(L\)，选出的信息条数与答案取 max。这个复杂度是 \(O(n^3\log n)\) 的，考虑怎么优化。

在定了 \(l\)，枚举 \(r\) 的过程中，我们可以记录一下经过的 \(a_i\) 的和 \(sum\)。一旦 \(sum+\sum\mid b_{p_{i+1}}-b_{p_i}\mid>L\)，就从 \(sum\) 里从大到小减掉一些 \(a_i\)，这可以用优先队列维护。然后用当前队列 size 对答案取 max 即可。