CF1896F Bracket Xoring

给定一个长度为 $2n$ 的二进制字符串 $s$，其中每个元素为 $\mathtt{0}$ 或 $\mathtt{1}$。你可以进行如下操作： 1. 选择一个长度为 $2n$ 的平衡括号序列 $^\dagger$ $b$。 2. 对于每个从 $1$ 到 $2n$ 的下标 $i$，如果 $b_i$ 是一个左括号，令 $p_i$ 表示最小的下标，使得 $b[i,p_i]$ 是一个平衡括号序列。然后，对 $s$ 执行一次从 $i$ 到 $p_i$ 的区间翻转操作 $^\ddagger$。注意，由于长度为 $2n$ 的平衡括号序列有 $n$ 个左括号，因此你将对 $s$ 执行 $n$ 次区间翻转操作。 你的任务是，找到不超过 $10$ 次操作的方案，将 $s$ 的所有元素都变为 $\mathtt{0}$，或者判断无法做到这一点。注意，你不需要最小化操作次数。 在给定的约束下，可以证明如果可以将所有元素变为 $\mathtt{0}$，则一定存在不超过 $10$ 次操作的方案。 $^\dagger$ 如果一个括号序列可以通过在其中插入 $+$ 和 $1$ 变成一个合法的数学表达式，则称其为平衡括号序列。例如，"(())()"、"()" 和 "(()(()))" 是平衡的，而 ")("、"(()" 和 "(()))(" 不是。 $^\ddagger$ 如果对二进制字符串 $s$ 执行从 $l$ 到 $r$ 的区间翻转操作，则将所有满足 $l \leq i \leq r$ 的 $s_i$ 取反。如果 $s_i$ 被翻转，则 $s_i := \mathtt{0}$ 如果 $s_i = \mathtt{1}$，反之亦然。例如，若 $s=\mathtt{1000101}$，对 $3$ 到 $5$ 区间翻转后，$s$ 变为 $s=\mathtt{1011001}$。

每个测试包含多组测试用例。第一行包含测试用例数 $t$（$1 \le t \le 1000$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$），其中 $2n$ 是字符串 $s$ 的长度。 第二行包含一个长度为 $2n$ 的二进制字符串 $s$（$s_i = \mathtt{0}$ 或 $s_i = \mathtt{1}$）。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例，如果无法将所有元素都变为 $\mathtt{0}$，则输出一行 $-1$。 否则，输出一个整数 $k$（$0 \le k \le 10$），表示将所有元素变为 $\mathtt{0}$ 所需的操作次数。接下来 $k$ 行，每行输出一个长度为 $2n$ 的平衡括号序列，表示将所有元素变为 $0$ 所需的操作。 如果存在多种不超过 $10$ 次操作的方案，你可以输出任意一种。

在第一个测试用例中，可以证明无法将所有元素都变为 $\mathtt{0}$。 在第二个测试用例中，第一次操作使用括号序列 $b = \mathtt{()()}$ 会将二进制字符串 $s=\mathtt{0000}$ 变为 $s=\mathtt{1111}$。然后，第二次操作使用相同的括号序列 $b = \mathtt{()()}$ 会将 $s=\mathtt{1111}$ 变回 $s=\mathtt{0000}$。注意，由于所有元素本来就是 $\mathtt{0}$，使用 $0$ 次操作也是合法答案。 在第三个测试用例中，使用括号序列 $b = \mathtt{(())()}$ 一次操作即可将所有元素变为 $\mathtt{0}$。操作过程如下： 1. $b_1$ 是左括号，$p_1 = 4$，因为 $b[1,4]=\mathtt{(())}$ 是平衡括号序列。因此，对二进制字符串 $s = \mathtt{100111}$ 执行 $1$ 到 $4$ 的区间翻转，得到 $s = \mathtt{011011}$。 2. $b_2$ 是左括号，$p_2 = 3$，因为 $b[2,3]=\mathtt{()}$ 是平衡括号序列。因此，对 $s = \mathtt{011011}$ 执行 $2$ 到 $3$ 的区间翻转，得到 $s = \mathtt{000011}$。 3. $b_3$ 不是左括号，此步不操作。 4. $b_4$ 不是左括号，此步不操作。 5. $b_5$ 是左括号，$p_5 = 6$，因为 $b[5,6]=\mathtt{()}$ 是平衡括号序列。因此，对 $s = \mathtt{000011}$ 执行 $5$ 到 $6$ 的区间翻转，得到 $s = \mathtt{000000}$。 6. $b_6$ 不是左括号，此步不操作。 在第四个测试用例中，第一次操作使用括号序列 $b = \mathtt{(((())))}$ 会将二进制字符串 $s = \mathtt{01011100}$ 变为 $s = \mathtt{11111001}$。然后，第二次操作使用括号序列 $b = \mathtt{()()(())}$ 会将 $s = \mathtt{11111001}$ 变为 $s=\mathtt{00000000}$。 由 ChatGPT 4.1 翻译