Codeforces Round #682 (Div. 2)D Powerful Ksenia ///思维

cf地址
题目大意：Ksenia has an array a consisting of n positive integers a1,a2,…,an.

In one operation she can do the following:

choose three distinct indices i, j, k, and then
change all of ai,aj,ak to ai⊕aj⊕ak simultaneously, where ⊕ denotes the bitwise XOR operation.
She wants to make all ai equal in at most n operations, or to determine that it is impossible to do so. She wouldn’t ask for your help, but please, help her!

Input
The first line contains one integer n (3≤n≤105) — the length of a.

The second line contains n integers, a1,a2,…,an (1≤ai≤109) — elements of a.

Output
Print YES or NO in the first line depending on whether it is possible to make all elements equal in at most n operations.

If it is possible, print an integer m (0≤m≤n), which denotes the number of operations you do.

In each of the next m lines, print three distinct integers i,j,k, representing one operation.

If there are many such operation sequences possible, print any. Note that you do not have to minimize the number of operations.

Examples
inputCopy
5
4 2 1 7 2
outputCopy
YES
1
1 3 4
inputCopy
4
10 4 49 22
outputCopy
NO
Note
In the first example, the array becomes [4⊕1⊕7,2,4⊕1⊕7,4⊕1⊕7,2]=[2,2,2,2,2].

题目大意： 每次选择3个下标 i,j，k，然后把a[i],a[j],a[k]变成a[i] ^ a[j] ^a[k] (异或)，问在n次操作内 能不能把所有的数变成一样的。

思路：把a[1]除去，然后两两配对如：（2，3），（4，5），（6，7）……；
用a[1]依次和这些对进行异或操作：（1，2，3）
这时a[1]=a[1]^a[2] ^a[3],且a[2]=a[3] (意味这a[2] ^a[3]=0);
然后（1，4，5）
这时a[1]=a[1]^a[2] ^a[3] ^a[4] ^a[5] ,且a[4]=a[5] (意味这a[4] ^a[5]=0);
进行完一轮之后 a[1]=a[1]^a[2] ^a[3] ^a[4] ^a[5]…… ^a[n];
且剩下的对中的数，都是相等的。
然后再进行一轮操作：所以有的数就会变成a[1] (最后的a[1]);
如果n是偶数，那么a[1]=a[1]^a[2] ^a[3] ^a[4] ^a[5]…… ^a[n-1]; 如果最后的这个数 !=a[n]，则无解。

代码：

#include<bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define re register #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define rep(i,n) for(int i=0;(i)<(n);i++) #define rep1(i,n) for(int i=1;(i)<=(n);i++) #define se secondusing namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int > pii; int dx[4]= {-1,1,0,0},dy[4]= {0,0,1,-1}; const ll mod=10; const ll N =2e6+10; const double eps = 1e-4; const double pi=acos(-1); ll gcd(int a,int b){return !b?a:gcd(b,a%b);} ll a[N];int main() {iosint t;t=1;while(t--){int n;cin>>n;int s=0;rep1(i,n) cin>>a[i];if(n%2==0){for(int i=1;i<=n-1;i++) s^=a[i];if(s!=a[n]) {cout<<"NO\n";return 0;}n--;}cout<<"YES\n";cout<<n-1<<endl;for(int i=2;i<n;i+=2){cout<<1<<" "<<i<<" "<<i+1<<endl;}for(int i=2;i<n;i+=2){cout<<1<<" "<<i<<" "<<i+1<<endl;}}return 0; } 创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的Codeforces Round #682 (Div. 2)D Powerful Ksenia ///思维的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。