CF1438D Powerful Ksenia 题解

题意：

Ksenia拥有一个由 \(n\) 个正整数组成的数组 \(a\)，分别为 \(a_1, a_2, \ldots, a_n\)。

在一次操作中，她可以执行以下操作：

选择三个不同的索引 \(i,j,k\)，然后

同时将 \(a_i, a_j, a_k\) 全部更改为 \(a_i \oplus a_j \oplus a_k\) ，其中 \(\oplus\) 表示按位异或操作。

她希望在最多 \(n\) 次操作中使所有 \(a_i\) 相等，或者确定这样做是不可能的。她不会主动请求您的帮助，但请帮助她！

输入格式：

第一行包含一个整数 \(n\) \((3 \leq n \leq 10^5)\)——数组 \(a\) 的长度。

第二行包含 \(n\) 个整数，\(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) ——数组 \(a\) 的元素。

输出格式：

根据是否可以在最多 \(n\) 次操作中使所有元素相等，在第一行打印YES或NO。

如果可能，打印一个整数 \(m\) \((0 \leq m \leq n)\)，表示您执行的操作次数。

在接下来的 \(m\) 行中，每行打印三个不同的整数 \(i, j, k\)，表示一次操作。

如果存在多个这样的操作序列，可以打印任意一个。注意，您不必最小化操作次数。

差点以为是 CF1572B ，然后发现这题是先在我待办清单里的，因此这题才是我所谓的原题。

总之这两题的区别在于，本题可以任取三个数操作，并且只要求最后所有的数变成一样。

对于奇数的情况，容易发现，我们对 \(1,3,5,\cdots\) 的位置每三个数操作一下，就可以得到 \[ \langle a,a,b,b,c,c,\cdots,x,x,x \rangle \] 于是我们只需要让 \(i,~i+1\) 和 \(n\) 操作一下就行了，

甚至我们可以从 \(n-2\) 开始 \(i,~i-1,~i-2\) 操作，这样甚至不用随意选 \(i,j,k\) ，只用相邻即可。

对于偶数的情况，需要一个显然的结论，如果所有数的异或和不为 \(0\) 一定无解，否则一定有解。

那么如果我们按照奇数的方式处理，可以得到 \[ \langle a,a,b,b,c,c,\cdots,x,x,x,y \rangle \] 因为异或和为 \(0\) ，所以 \(x=y\) ，于是构造方式类似。

时间复杂度 \(\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];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    if(n & 1)
    {
        cout << "YES\n" << n - 1 << '\n';
        for(int i = 1; i <= n - 2; i += 2) cout << i << ' ' << i + 1 << ' ' << i + 2 << '\n';
        for(int i = 1; i <= n - 2; i += 2) cout << i << ' ' << i + 1 << ' ' << n << '\n';
    }else
    {
        for(int i = 1; i <= n - 2; i += 2) a[i] = a[i + 1] = a[i + 2] = a[i] ^ a[i + 1] ^ a[i + 2];
        if(a[n] != a[n - 1]) cout << "NO" << '\n';
        else
        {
            cout << "YES\n" << n - 3 << '\n';
            for(int i = 1; i <= n - 2; i += 2) cout << i << ' ' << i + 1 << ' ' << i + 2 << '\n';
            for(int i = 1; i <= n - 4; i += 2) cout << i << ' ' << i + 1 << ' ' << n << '\n';
        }
    }
    return 0;
}