MX-S5 T3 官方题解
vegetaBle_king
·
·
题解
IMAWANOKIWA (Construction ver.)（FeOI 命题组）
可能更好的阅读体验
题意简述
给你一个初始长度为 n，只包含 \mathbf{0, 1, 2} 的序列 a_{1 \sim n}，你每次可以选择两个相邻的数 p, q，删去它们，并在原位置插入 \mathrm{popc}(p + q)。其中，\mathrm{popc}(x) 表示 x 在二进制表示下 1 的个数。
显然每次操作后序列长度都会减少 1，所以执行 n - 1 次操作后，这个序列会恰好剩下一个数。请你最小化剩下的这个数，并给出字典序最小的操作位置序列。
此题多测，设 T 为组数，对所有数据，满足 1 \le T \le 200，1 \le n \le 10^5。
算法 1
我会爆搜！
时间复杂度：\mathcal O(Tn! \times poly(n))。
期望得分：12。
算法 2
我会区间 DP！设 f_{i, j, k} 表示区间 [i, j] 是否能得到 k \ (0 \le k \le 2)，枚举最小转移点即可。
时间复杂度：\mathcal O(Tn^3)。
期望得分：24。
算法 3
我会特殊性质 A！发现 a 序列中只有 1, 2 的时候 \mathrm{popc}(p + q) = ((p - 1) \oplus (q - 1)) + 1，其中 \oplus 表示异或运算。
那么无论操作顺序答案都是一样的，答案也可以直接求出，最小字典序直接操作 n - 1 次开头即可。
时间复杂度：\mathcal O(Tn)。
期望得分：12，结合区间 DP 后 36。
算法 4
我会判断答案！首先给出结论：
- 当且仅当 a 序列全为 0 时答案为 0；
- 序列 a 没有 0 时答案为 2 的个数对 2 取模的余数 +1；
- 否则，当且仅当在序列 a 为“一段 1，2, 0, 2，一段 1”（左右两边的一段 1 都可以为空）的形式时，答案为 2，其余情况为 1。
证明
前两个情况是显然的。先证明第三种情况的对应形式无法合成 1，可以发现如果 0 不参与操作只是相当于减少了一个 1，还是该形式；而 0 若参与操作，序列 a 就会变为第二种情况，并且只有奇数个 2，显然答案为 2。所以该情况一定只能合成 2。
再证明非对应形式一定可以合成。考虑归纳，如果我们能找到一个 0，然后将其左右两边合成，只要左右两边不都是 2，最终就可以合出 1。
假设 0 的个数大于两个，那么选择最左边的 0 即可，右边至少有两个 0，一定可以得到 1；
假设 0 的个数恰好有两个，那么序列 a 一定是 A0B0C 的形式，其中 A, B 都是不存在 0 的序列。如果 B 为 [2]，那么先将 B 和旁边一个 0 合成即可得到 A01C 的形式，该形式答案一定为 1；否则左右两个 0 肯定有一个合法。
假设 0 的个数只有一个。如果 0 两边至少有一个不是 2，那么我们就有操作空间了：当 2 有奇数个时，我们让最靠近 0 的 2 把经过的 1 都干掉，与 0 合并。否则我们直接让 0 与它旁边的那个 1 合并。假设这个 0 的左右两边都不合法，那么一定有一边至少有三个 2，我们把最靠近 0 的两个 2 合并，0 两边就至少有一个 1；否则可以直接合出 1。
这样所有情况都被考虑到了，证毕。
时间复杂度：\mathcal O(Tn)。
期望得分：25，结合前面算法后 52。
算法 5
考虑直接贪心，从前往后依次尝试合并，每次合并完之后重新扫一遍序列，判断答案是否变大，如果变大了就撤销这个操作。
这样时间复杂度看似是 \mathcal O(Tn^3) 的，实际上是 \mathcal O(Tn^2) 的。感性理解一下，第一个可以合并的位置出现的一般不会太晚，实际上第一个可以合并的位置最多不会超过 3。证明还是需要分讨，这里就不放了。
时间复杂度：\mathcal O(Tn^2)。
期望得分：36，结合前面算法后 61。
算法 6
使用平衡树一类的数据结构维护序列，每次快速找出下一个能操作的位置，或者直接暴力枚举位置。
时间复杂度：\mathcal O(Tn \log n)。
期望得分：视实现有 48 \sim 92，结合前面算法后 70 \sim 94。
算法 7
根据前面的结论，可以直接暴力维护前几个位置，后面的位置一定是连续的，这样就可以省掉 \log。
时间复杂度：\mathcal O(Tn)。
期望得分：100。