Powerful Ksenia
Solution
CF 为什么这么喜欢构造题(
首先需要知道一些性质。
- 性质 \(1\):数列变化前后全局异或和不发生改变。
这一点很好证明,因为将原来数列中的三个数 \(a,b,c\) 全部变为 \(a\oplus b\oplus c\) 后(令 \(t=a\oplus b\oplus c\)),那么可以知道 \(t\oplus t\oplus t=t=a\oplus b\oplus c\),也就是说变化前后这三个数对全局异或和并不会产生变化,进而可以证明进行一系列变化后,数列的全局异或和不变。
- 性质 \(2\):\(x\oplus x\oplus y=y\)
这一性质很重要,如果数列长度是奇数,那么将原数列变成 \(a,a,b,b,c,c,d,d,d\) 这种形式后,可以通过 \(a\oplus a\oplus d\),\(b\oplus b\oplus d\),\(\cdots\) 这种办法将数列变成 \(d,d,d,d,d,d,d,d,d\)(其实也就是说奇数长度的数列是一定有解的)。
如果数列长度是偶数,那么根据性质 \(1\),数列的最终状态的全局异或和为 \(0\),也就是说只有当数列中所有的数全部异或起来等于 \(0\) 时才是有解的。那么根据这个结论,我们可以把这个偶数 \(n\) 长的数列拆分成为前 \(n-1\) 和最后 \(1\) 个,根据前面所说,可以得知最后 \(1\) 个一定与前 \(n-1\) 个最后变成的数是一样的(否则无法满足全局异或和为 \(0\) 这一条件),也就是说,可以不管最后那个,只要前 \(n-1\) 个构造出来即可(构造方式与奇数长相同)。
完整代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof a)
//#define int long long
using namespace std;
template<typename T> void read(T &k)
{
k=0;T flag=1;char b=getchar();
while (!isdigit(b)) {flag=(b=='-')?-1:1;b=getchar();}
while (isdigit(b)) {k=k*10+b-48;b=getchar();}
k*=flag;
}
template<typename T> void write(T k) {if (k<0) {putchar('-'),write(-k);return;}if (k>9) write(k/10);putchar(k%10+48);}
template<typename T> void writewith(T k,char c) {write(k);putchar(c);}
const int _SIZE=1e5;
int n,a[_SIZE+5],XorSum=0;
signed main()
{
read(n);
for (int i=1;i<=n;i++) read(a[i]),XorSum^=a[i];
if (n%2==0 && XorSum!=0) {puts("NO");return 0;}
puts("YES");
if (n%2==0) n--;
writewith(n-2,'\n');
for (int i=1;i<n;i+=2)
printf("%d %d %d\n",i,i+1,i+2);
for (int i=1;i<n-2;i+=2)
printf("%d %d %d\n",i,i+1,n);
return 0;
}
标签:CF1438D,Ksenia,数列,int,Powerful,异或,oplus,全局
From: https://www.cnblogs.com/hanx16msgr/p/16749195.html