P12651 [KOI 2024 Round 2] 最大异或

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

在一个字符串中，选择一个或多个连续位置的字符，并保持其顺序排列后得到的字符串，称为该字符串的子字符串。 例如，$\tt{001}$ 是字符串 $X = \tt{10011}$ 的子字符串，但不是字符串 $Y = \tt{10101}$ 的子字符串。 两个非负整数 $A$ 和 $B$ 的异或（XOR）$A \oplus B$ 定义如下： - 从二进制的角度来看，若 $A$ 的第 $2^k$ 位与 $B$ 的第 $2^k$ 位不同，则 $A \oplus B$ 的第 $2^k$ 位为 1；若相同，则该位为 0。（其中 $k \ge 0$） - 例如，$12 \oplus 10$ 的计算如下： $12 = 1100_2$，$10 = 1010_2$，因此 $1100_2 \oplus 1010_2 = 0110_2 = 6$ 给定一个仅由 0 和 1 组成、长度为 $N$ 的字符串 $S$。 你需要计算从 $S$ 的子字符串 $s_1$ 和 $s_2$ 中可以构造出的 $g(s_1, s_2)$ 的最大值。函数 $g(s_1, s_2)$ 定义如下： - 对于 $S$ 的子字符串 $s$，$f(s)$ 表示将 $s$ 视为二进制数后对应的十进制数值。例如，若 $s = 11010$，则 $f(s) = 26$。 - $g(s_1, s_2) = f(s_1) \oplus f(s_2)$ 此处 $s_1$ 和 $s_2$ 不需要不同。换句话说，$s_1$ 和 $s_2$ 可以在 $S$ 中部分重叠，甚至可以是完全相同的字符串。 给定一个仅由 0 和 1 组成的字符串 $S$，请编写一个程序来计算可能的 $g(s_1, s_2)$ 的最大值。

第一行输入测试用例的个数 $T$。 接下来的每个测试用例包含两行： - 第一行：字符串长度 $N$ - 第二行：一个长度为 $N$ 的仅由 0 和 1 组成的字符串 $S$

对于每个测试用例，输出可能的 $g(s_1, s_2)$ 的最大值，用二进制表示，每行输出一个结果。 注意，结果前不应输出无意义的前导 0。

**样例 1 说明** 在第一个测试用例中，将 $s_1 = 010$，$s_2 = 01$，可以得到 $g(s_1, s_2) = 11_2$。 尽管也可以写作 $011_2$，但因为不能有无意义的前导 0，因此应输出 11，而不是 011。 在第四个测试用例中，将 $s_1 = 11111$，$s_2 = 1$，可以得到 $g(s_1, s_2) = 11110_2$。 **约束条件** - 所有给定数均为整数。 - $1 \le T \le 100$ - $2 \le N \le 10^7$ - 所有测试用例中 $N$ 的总和 $\le 10^7$ - $S$ 是一个由 0 和 1 组成、长度为 $N$ 的字符串。 **子问题** 1. （17 分）$N \le 30$，所有测试用例中 $N$ 的总和 $\le 300$ 2. （20 分）$N \le 200$，所有测试用例中 $N$ 的总和 $\le 2000$ 3. （13 分）$N \le 3000$，所有测试用例中 $N$ 的总和 $\le 30000$ 4. （12 分）$N \le 2 \times 10^5$，所有测试用例中 $N$ 的总和 $\le 2 \times 10^6$ 5. （38 分）无额外约束条件 翻译由 ChatGPT-4o 完成