CF1572B 题解

· · 题解

提供一种比较好想好写，不容易错的方法。教你将 *2500 的题做成 *1500

题目链接

思路

显然，当存在奇数个 1 时，原式无解。

证明：设对 a_i,a_{i+1},a_{i+2} 进行操作，记 a_i\oplus a_{i+1}\oplus a_{i+2}=sum，则操作之后三数的异或和为 sum\oplus sum\oplus sum=sum，不变。由此可得，所有数的异或和，经任意次操作后不变。故要求初始状态的所有数异或和为 0。

更进一步地，记 s_i=\bigoplus\limits_{k=1}^ia_k，我们有 s_0,s_1,\cdots,s_{i-1} 以及 s_{i+2},s_{i+3},\cdots,s_n 均不发生变化。此时只有 s_i,s_{i+1} 变化了。设 x=s_{i-1}，我们此时又有 s_i=x\oplus sum,s_{i+1}=s_i\oplus sum=x,s_{i+2}=s_{i+1}\oplus sum=x\oplus sum。所以，操作后 s_{i-1}=s_{i+1},s_i=s_{i+2}。我们又知道 s_{i-1},s_{i+2} 均不变，所以原题转化成了：

给定 s_0,s_1,\cdots s_n，保证 s_0=s_n=0，每次操作可以选定一个数 i\in[1,n-2]，使得 s_{i+1}\gets s_{i-1},s_i\gets s_{i+2}，要求 n 次操作后最终所有数变为 0。

这就很好做了。显然每次赋值都只能在下标奇偶性相同的相邻位置上进行，且不能给 s_0,s_n 赋值，那么只需要分下标的奇偶即可。下标为偶数的位置显然无论如何都可以被赋值成 0，那么先考虑奇数位置：找到数值为 0 的位置，然后向两边赋值即可，找不到即无解。

代码实现

#include <cstdio>
int T, n, a[200007], s[200007], ans[200007], tot, idx;
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for(int i = 1; i <= n; i++)
            s[i] = s[i - 1] ^ a[i];
        if(s[n]) {
            puts("NO"); continue;
        }
        tot = 0, idx = 0;
        for(int i = 1; i <= n; i += 2) {
            if(!s[i]) {
                idx = i; break;
            }
        }
        if(!idx) {
            puts("NO"); continue;
        }
        for(int i = idx - 2; i >= 1; i -= 2)
            ans[++tot] = i;
        for(int i = idx + 2; i < n; i += 2)
            ans[++tot] = i - 1;
        for(int i = 2; i < n; i += 2)
            ans[++tot] = i - 1;
        puts("YES");
        printf("%d\n", tot);
        for(int i = 1; i <= tot; i++)
            printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}