从题意来看,是个博弈论
这种题需要我们去寻找必胜状态和必败状态,又要去比较大小,
我们可以发现其实就是寻找从后向前(二进制)第一个为1的数目
这里有个核心就是不仅可以给自己或上也可以给对面或上
若为奇数时我们可知要拿到一个1然后即使对面将这个1或掉也能有多一个1
而对面若给自己或上1,我们最后将1给对面或上为0
而若为偶数则最好的情况便是两边都不选这个1
所以和第一个为奇数的1的数目有关,
但我们发现若选0的话也就是在我们选了1后对面不在抢1而是选择权给我们
但是我们已经有1了再选就浪费了,所以选择权就变成我们是保留自己的1选个其他的还是将自己的1消掉还是将1给对面
注意这里无论怎么选因为1的个数是奇数除非我们选择保留自己的1选个其他否则都是必败,但是否有零给我们选呢
也就是说我们能否把选择权扔给了对面呢,所以和0也有关
这里可以知道若0的个数是奇数且1的个数是奇数除非奇数的数目是1否则我们必败
所以必胜的条件便是偶数个零加奇数个1也就是n是奇数或者1的个数是奇数我们必胜
所有其实和1的数目与0的数目均有关系(也就是n的数目)若为奇数则先手必胜否则必败
这里有两点例外:
第一我们可以发现若最后异或为零时无论怎么选都是相同的
第二我们可以知道若第一个位置为1的1的数目是1时,就和n的数目无关了肯定必胜
#include<iostream>
#include<cstring>
using namespace std;
const int N=32;
int su[N];
int res,n;
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
res=0;
memset(su,0,sizeof su);
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
res^=x;
int cnt=0;
while(x)
{
if(x&1)su[cnt]++;
cnt++;
x>>=1;
}
}
if(!res)
{
cout<<0<<endl;
continue;
}
int y=0;
for(int i=N-1;i>=0;i--)
{
if(su[i]%2==1)
{
y=i;
break;
}
}
if(n%2==1||su[y]==1)cout<<1<<endl;
else cout<<-1<<endl;
}
return 0;
}
如果有三个,一两个零,一开始分配两个一,那两个人都为一,然后a给b一个0,b给a一个0,这不就打成平局了吗?
看了半天没看懂啊
请问是哪个地方没有理解呢?可能表述有些问题
强
终于看懂了6666666
66666666666