首页 > 其他分享 >CF1438D Powerful Ksenia

CF1438D Powerful Ksenia

时间:2022-10-02 18:34:32浏览次数:75  
标签:CF1438D Ksenia 数列 int Powerful 异或 oplus 全局

Powerful Ksenia

Codeforces CF1438D

Luogu CF1438D

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

相关文章

  • NC15832 Most Powerful
    题目链接题目题目描述Recently,researchersonMarshavediscoveredNpowerfulatoms.Allofthemaredifferent.Theseatomshavesomeproperties.Whentwoof......