CF1572B Xor of 3 题解

题目链接：Xor of 3

题意：

给出一个 \(01\) 序列，一次操作可以选择连续的三个数，把它们都变成它们的异或和。

问能否在 \(n\) 次以内把所有数变成 \(0\)，输出方案（操作 \(i\) 则修改 \(a_i,~a_{i+1},~a_{i+2}\) ）

输入格式：

多组数据，每组数据给出 \(n\) 和 \(n\) 个数。

输出格式：

有解输出一行 YES ，否则输出 NO 。

如果有解，输出一行表示步骤数（可以不是最少次数），接着一行若干个数表示操作位置

数据范围：

\(3 \le \sum n \le 2\times10^5\)

感觉这道题在哪里听过思路了，今天找到原题了。思路还是比较有意思的。（upd.其实是 CF1438D）

因为题目要全部变成 \(0\) ，所以与异或和性质就显得十分关键。

容易发现，每次操作后所有数的异或和不会改变，因此异或和为 \(0\) 是有解的一个必要条件（但是不充分）

首先考虑 \(n\) 为奇数的情况，如果我们在 \(n-2,~n-4,~\cdots,~1\) 分别操作一次

此时 \(a_1=0\) ，且其他的数呈现 AABBCCDD 的状态，即 \(a_{2k}=a_{2k+1}\) 。

接着我们再对 \(1,~3,~\cdots,~n-2\) 分别操作一次，则序列就会变成全 \(0\) 。

\(n\) 为偶数的情况也很简单。我们只需要找到一个长度为奇数的前缀，使其变成全 \(0\) 即可套用奇数的情况

说实话我觉得这道题有那么点构造的感觉，实际上手玩玩就会发现这些性质，只是可能没想到怎么做罢了

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

int n, a[N], b[N];
void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) { cin >> a[i], a[i] ^= a[i - 1]; }
    if(a[n]) { cout << "NO" << '\n'; return; }
    if(n & 1)
    {
        int now = 0, tot = 0;
        while(now < n - 3) b[++tot] = now + 1, now += 2;
        while(now >= 0) b[++tot] = now + 1, now -= 2;
        cout << "YES\n" << tot << '\n';
        for(int i = 1; i <= tot; i++) cout << b[i] << " \n"[i == tot];
        return; 
    }
    for(int k = 1; k <= n; k += 2) if(!a[k])
    {
        int now = 0, tot = 0;
        if(k != 1) {
            while(now < k - 3) b[++tot] = now + 1, now += 2;
            while(now >= 0) b[++tot] = now + 1, now -= 2;
        }  
        now = k;
        if(k + 1 != n) {
            while(now < n - 3)  b[++tot] = now + 1, now += 2;
            while(now >= k) b[++tot] = now + 1, now -= 2;
        }
        cout << "YES\n" << tot << '\n';
        for(int i = 1; i <= tot; i++) cout << b[i] << " \n"[i == tot];
        return;
    }
    cout << "NO" << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}