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$。