CF1572B 题解

王熙文 · 2023-08-28 14:27:53 · 题解

昨天做题做到的套路今天就又遇到了。

思路

注意到一次操作三个数的异或和不变，考虑对序列求异或前缀和 a，并观察操作在 a 上是什么样的。

因为异或和不变，所以一次操作 i 只会改两个数，a_i 和 a_{i+1}。因为原序列操作后 i+1 与 i+2 位置上的数相同，且 i 与 i+1 位置上的数相同，所以一次操作后 a_i \gets a_{i+2},a_{i+1} \gets a_{i-1}。

考虑如果 a_x=a_y=0，中间全是 1，区间是否可以覆盖为 0。当 x 与 y 同奇偶时，因为每一次操作赋值的两边都是同奇偶的，所以与 x,y 不同奇偶的位置不可能被覆盖到，无解。否则，可以先从前到后用 a_x 把与 x 同奇偶的位置覆盖为 0，那么在最后一定有 a_{y-1}=a_y=0，再覆盖回去即可。

比如 011110，先操作 2，变成 010110，再操作 4，变成 010000，再操作 2，变成 000000，实现清零。

还可以发现如果 a_n \ne 0，则无法操作使它变为 0，一定无解。那么，当 n 为奇数时，直接按照上面的方式操作 x=0,y=n 即可。

如果 n 为偶数，如果序列中没有一个奇数的位置为 0，一定无解，因为奇数位置不可能被覆盖到。否则，设位置为 i，先操作 x=0,y=i，再操作 y=i,x=n 即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[200010];
int tot,ans[200010];
void output(int l,int r)
{
    if(l+1==r) return;
    int now=l;
    while(now<r-3) ans[++tot]=now+1,now+=2;
    while(now>=l) ans[++tot]=now+1,now-=2;
}
int main()
{
    int t; cin>>t; while(t--)
    {
        cin>>n;
        for(int i=1; i<=n; ++i) cin>>a[i],a[i]^=a[i-1];
        if(a[n]!=0) { cout<<"NO\n"; continue; }
        if(n%2==1)
        {
            cout<<"YES\n";
            tot=0,output(0,n);
            cout<<tot<<'\n';
            for(int i=1; i<=tot; ++i) cout<<ans[i]<<' '; cout<<'\n';
        }
        else
        {
            bool flag=0;
            for(int i=1; i<=n; i+=2)
            {
                if(a[i]==0)
                {
                    cout<<"YES\n";
                    tot=0,output(0,i),output(i,n);
                    cout<<tot<<'\n';
                    for(int i=1; i<=tot; ++i) cout<<ans[i]<<' '; cout<<'\n';
                    flag=1;
                    break;
                }
            }
            if(!flag) cout<<"NO\n";
        }
    }
    return 0;
}