「CF1438D」 Powerful Ksenia 「CF1438D」 Powerful Ksenia

题目大意

给定 (n) 个正整数，你可以任选三个数 (a_i,a_j,a_k)，使这三个数都变为 (a_ioplus a_joplus a_k)（(oplus) 代表异或）。

问是否能构造一种方案，使得在 (n) 次操作内使所有数相等。

---

构造题。

显然我们有这样两种方式：

• 选择三个数 (a,b,c)，将他们变成 (d)。
• 选择三个数 (a,a,b)，将他们变为 (b)。

这启发我们将 ((1,2,3),(3,4,5),(5,6,7),...) 这样的三元组进行操作，这样若原数列长度为奇数，则一定能构造出一种方案使得所有数相等。

下面考虑原数列长度为偶数的情况。

注意到我们的操作不会让原数列所有数的异或和发生改变，即若原数列长度为偶数且存在一种方案让所有数相等，则其所有数异或和一定为 (0)。

这可以作为我们判定是否有解的必要条件。

那么若所有数异或和为 (0)，是否一定能构造出一种方案呢？

答案是肯定的。此时我们忽略掉数列的最后一个数，使其变为奇数长度的序列即可，由于数列异或和为 (0)，且操作不会改变原数列异或和，故前 (n-1) 个数进行操作后得到的值一定等于数列的第 (n) 个数。

代码：

/*---Author:HenryHuang---*/
/*---Never Settle---*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn],sum;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i],sum^=a[i];
	if(n%2==0){
		--n;
		if(sum) cout<<"NO
",exit(0);
	}
	cout<<"YES
";
	cout<<n-2<<'
';
	for(int i=1;i+2<=n;i+=2) cout<<i<<' '<<i+1<<' '<<i+2<<'
';
	for(int i=1;i+1<=n-3;i+=2) cout<<i<<' '<<i+1<<' '<<n<<'
'; 
	return 0;
}