[异或] cf1572b

_Cheems · 2024-02-02 19:06:13 · 个人记录

套路：放在异或前缀和数组上讨论。

于是 [i,i+2] 的异或和是 s_{i+2} \oplus s_{i-1}，可以推出不少性质。

性质 1：显然操作后 [i,i+2] 的异或和不变，观察 s_i,s_{i+1},s_{i+2}，发现操作后 s_i=s_{i+2},s_{i+1}=s_{i-1}。

性质 2：操作不会改变原序列 1 的数目的奇偶性，于是得出 s_n=0，否则无解。

由性质 2，得知 s 的奇偶位不会互相影响。显然可以 n-2,n-4... 操作使得与 n 奇偶性相同的位全变成 0；以此类推，可以在 n-1,n-3... 中找到一个 0，使得它们全变成 0。

由于无论怎么操作 s_n 不会改变，但是与 n 奇偶不同的位是有可能出现在操作时 0 被后面的 1 覆盖的情况，所以我们优先操作与 n 奇偶不同的位。

代码

注意一个细节：s_2 可以由 s_0 赋值从而得到 0。

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int t, n, a[N], b[N], n_;

inline void solve(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) 
        scanf("%d", &a[i]), a[i] ^= a[i - 1];
    if(a[n]) {printf("No\n"); return ;}
    n_ = 0;
    for(int i = n - 1; i >= 0; i -= 2)
        if(!a[i]){
            for(int j = i - 2; j >= 1; j -= 2) if(j + 2 <= n) b[++n_] = j, a[j] = a[j + 2], a[j + 1] = a[j - 1];
            for(int j = i + 1; j <= n; j += 2) if(j + 2 <= n) b[++n_] = j, a[j] = a[j + 2], a[j + 1] = a[j - 1];
            break;
        }
    for(int i = n - 2; i >= 1; i -= 2) if(i + 2 <= n) b[++n_] = i, a[i] = a[i + 2], a[i + 1] = a[i - 1];
    for(int i = 1; i <= n; ++i) 
        if(a[i]) {printf("No\n"); return ;}
    printf("Yes\n%d\n", n_);
    for(int i = 1; i <= n_; ++i) printf("%d ", b[i]);
    printf("\n");
}
int main(){
    cin >> t;
    while(t--) solve();
    return 0;
}