CF1438D

Aryper · 2021-07-24 20:31:09 · 个人记录

Powerful Ksenia

构造题。

然后我们想起了异或的自反性：x\operatorname{xor}y\operatorname{xor}y=x 。

然后这个事情就变成了使这个序列每一对数中两数相同，最后留下一个不同的数，然后就是消消乐。至于怎么使得每一对数中的两数相同，我们可以对于每个奇数 i ，操作 i,i+1,i+2 。

然后我们就会发现这个序列是奇数长度时就一定会有解。

那么讨论偶数的情况，我们发现，按照上面的方法我们仍然可以调整序列到每一对数中的两个数相同，然后消消乐的时候发现会多出来一个数，那么这个数如果不和其他数相同的话，显然不论怎么操作都不能达成目标；反之则可以。

然后我的脑子大概就只能思考到这里，于是乎就看到了异或和为零才有可能这种神奇的结论。。。

至于这个操作的次数，大概是 \lfloor\frac{n-1}{2}\rfloor （使序列中的每对数中的两数相等所需的操作次数，然后偶数的时候最后的一对可不操作，故下取整）+\lfloor\frac{n-1}{2}\rfloor (消消乐的次数) =\begin{cases}n-1,n\mod 2=1\\n-2,n\mod 2=0\end{cases} 。

时间复杂度 O(n) 。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,sum_xor;

ll a[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read();sum_xor=sum_xor^a[i];
    }

    if(n%2==1) {
        printf("YES\n");
        printf("%lld\n",n-1);
        for(ll i=1;i<=n-2;i+=2) {
            printf("%lld %lld %lld\n",i,i+1,i+2);
        }
        for(ll i=1;i<=n-2;i+=2) {
            printf("%lld %lld %lld\n",n,i,i+1);
        }
    }
    else {
        if(sum_xor!=0) {
            printf("NO");
        }
        else {
            printf("YES\n");
            printf("%lld\n",n-2);
            for(ll i=1;i<=n-3;i+=2) {
            printf("%lld %lld %lld\n",i,i+1,i+2);
        }
        for(ll i=1;i<=n-3;i+=2) {
            printf("%lld %lld %lld\n",n,i,i+1);
        }
        }
    }

    return 0;
}