poj2975--Nim

时间:2021-07-17 16:07:34

题意:对于一个给定的取石子游戏,有多少种先手策略获胜?

Ans:若无法获胜,则输出0。

若能获胜我们只要找到一堆石子,使得我们能取它的一部分让总和的异或和变为0。我们先将整个游戏的值异或起来为s

则a[i]^s就是除了第i堆以外的其他所有堆的异或和,如果这个异或和小于a[i],说明我们可以通过取这堆石子让异或和等于0。

(为什么不能取等号?,因为一堆石子我们如果取,不能取0个石子)

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
int n,ans,x,a[];
int main(){
while (~scanf("%d",&n)){
if (n==) break;
int s=;
for (int i=;i<=n;i++){
scanf("%d",&a[i]);
s^=a[i];
}
ans=;
for (int i=;i<=n;i++)
if ((s^a[i])<a[i]) ans++;
printf("%d\n",ans);
}
}

相关文章