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;
}