CF1750C Complementary XOR

你有两个长度为 $n$ 的二进制字符串 $a$ 和 $b$。你希望将这两个字符串的所有元素都变为 $0$。不幸的是，你只能使用如下操作来修改这两个字符串： - 你选择两个下标 $l$ 和 $r$（$1 \le l \le r \le n$）； - 对于所有满足 $l \le i \le r$ 的 $i$，将 $a_i$ 取反，即 $a_i := 1 - a_i$； - 对于所有满足 $1 \le i < l$ 或 $r < i \le n$ 的 $i$，将 $b_i$ 取反，即 $b_i := 1 - b_i$。 你的任务是判断是否有可能通过若干次操作将两个字符串的所有元素都变为 $0$。如果可以，请给出一组不超过 $n+5$ 次操作的方案。可以保证，如果存在可行方案，则一定存在不超过 $n+5$ 次操作的方案。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示字符串的长度。 第二行包含一个长度为 $n$ 的二进制字符串 $a$，仅由字符 $0$ 和 $1$ 组成。 第三行包含一个长度为 $n$ 的二进制字符串 $b$，仅由字符 $0$ 和 $1$ 组成。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，首先输出一行 "YES"（如果可以将两个字符串都变为 $0$），否则输出 "NO"。如果输出 "YES"，则在下一行输出一个整数 $k$（$0 \le k \le n+5$），表示操作次数。接下来的 $k$ 行，每行输出两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示一次操作。 如果有多种正确答案，可以输出任意一种。

在第一个测试用例中，我们可以对 $l=2$ 且 $r=2$ 执行一次操作。这样 $a_2 := 1 - 1 = 0$，字符串 $a$ 变为 000。$b_1 := 1 - 1 = 0$，$b_3 := 1 - 1 = 0$，字符串 $b$ 变为 000。 在第二个和第三个测试用例中，可以证明无法将两个字符串的所有元素都变为 $0$。 在第四个测试用例中，我们可以先对 $l=1$ 且 $r=2$ 执行一次操作，此时字符串 $a$ 变为 01，字符串 $b$ 不变。然后对 $l=2$ 且 $r=2$ 执行一次操作，此时 $a_2 := 1 - 1 = 0$，$b_1 = 1 - 1 = 0$。最终 $a$ 和 $b$ 都变为 00。 在第五个测试用例中，我们可以先对 $l=1$ 且 $r=1$ 执行一次操作，此时 $a$ 变为 011，$b$ 变为 100。然后对 $l=2$ 且 $r=3$ 执行一次操作，最终 $a$ 和 $b$ 都变为 000。 由 ChatGPT 4.1 翻译