Complementary XOR
C++ 代码
/*
本题要求用一种操作将两个字符串都消成 0
我们可以发现,我们进行的操作一定是互补的,对于每一位都一定有一个数翻转。
因此如果设 c[i] = a[i] ^ b[i],那么每一次操作都会让整个序列 c 翻转。
而我们的目标是让所有数都变成 0,由于我们每次都只能让序列 c 整个翻转,因此要想达到
目标,序列 c 只能全是 0 或全是 1.如果存在又有 0 又有 1 的情况,直接无解。
然后对于全是 0 和全是 1 的情况,我们将全是 1 的情况通过一个任意的操作进行翻转,
这样就只需要处理全是 0 的情况了,为了方便操作我们直接用一个 [1, n] 将序列翻转。
对于全是 0 的情况,说明 a[i] == b[i],对于任意两个是 1 的位置 a[i] = b[i] = 1 和
a[j] = b[j] = 1,我们可以用两个操作 [i, i] [j, j] 来将这两个 1 消成 0。
如果 a[i] = b[i] = 1 的数量是奇数,那么我们还需要将最后一个 1 消成 0,我们可以先用
[i, i] [n, n] 将这一位移到最后一位,然后用 [1, n] [1, n - 1] 将最后这位 1 消成 0.
通过以上的操作我们就能得到一组合法操作方案,并且最大操作次数为 n + 4,没有超过题目要求
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200010;
int n;
char a[N], b[N];
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%s%s", &n, a, b);
int c = 0, one = 0; //c 表示 a[i] != b[i] 的位数,one 表示 a[i] = b[i] = 1 的位数
for(int i = 0; i < n; i++)
{
if(a[i] != b[i]) c++;
if(a[i] == '1') one++;
}
if(c != 0 && c != n) //不全是 0 或 1 就无解
{
puts("NO");
continue;
}
puts("YES");
int rev = 0; //是否需要翻转
if(c == n) //全是 1 则需要翻转
{
rev = 1;
one = n - one;
for(int i = 0; i < n; i++) a[i] = '1' - a[i] + '0';
}
//输出操作方案
int res = one + rev;
if(one & 1) res += 3;
printf("%d\n", res);
if(rev) printf("%d %d\n", 1, n);
for(int i = 0; i < n; i++)
if(a[i] == '1')
printf("%d %d\n", i + 1, i + 1);
if(one & 1)
{
printf("%d %d\n", n, n);
printf("%d %d\n", 1, n);
printf("%d %d\n", 1, n - 1);
}
}
return 0;
}