Codeforces Round 717 (Div. 2) B. AGAGA XOOORRR(位运算)

发布时间 2023-04-04 17:42:41作者: 高尔赛凡尔娟

https://codeforces.com/contest/1516/problem/B

题目大意:

给定长度为n的数组a,问我们能不能一直选择两个相邻的元素进行异或后,删除这两个值,把异或值留下来,

最后剩下>=2个数字,它们都是相同的?

可以做到输出YES,不能的话输出NO。
input 
2
3
0 2 2
4
2 3 1 10
output 
YES
NO

题目中说:留下的数字至少有两个,所以我们可以从2开始推:
当留下两个数字相同时(eg:1 1),说明我们把这两个数字异或后就变成了0,也就是说,我把全部数字异或后等于0,可以满足条件;
当留下三个数字相同时(eg:2 2 2),说明我们可以把数组分成三个段,前中后,一旦异或前缀中这三段相等,即可满足条件;
当留下四个数字相同时(eg:3 3 3 3),我们可以先对它们进行深入思考,相邻两两合并,不就又成了3 3,所以也可以满足条件;
当留下五个数字相同时(eg:1 1 1 1 1),我们先思考,当相邻两个异或就变成了0,0再和旁边一个数字异或就又变成了1,就可以变成3个相同数字(eg:1 1 1),满足条件;
偶数依此类推,全部数字异或即可;
奇数以此类推,分成三个段相等即可。

如何判断三个段相等,那必须是异或前缀嘎嘎好用!

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e7+10,M=2023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL a[N],b[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
    	LL n;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    	     cin>>a[i];
       	     b[i]=b[i-1]^a[i];
	}
	if(b[n]==0) cout<<"YES"<<endl;//两段
	else
	{
 	      bool flag=false;
	      for(int i=1;i<=n;i++)
	      {
 		   for(int j=i+1;j<=n;j++)
		   {			
                        if(b[i]==(b[j]^b[i])&&(b[j]^b[i])==(b[n]^b[j]))//三段
			{
			     //cout<<i<<" "<<j<<endl;
			     flag=true;
			     break;
			}
  		   }
		   if(flag==true) break;
	      }
	      if(flag==true) cout<<"YES"<<endl;
	      else cout<<"NO"<<endl;
	 }
    }
    return 0;
}