首页 > 代码库 > [原博客] POJ 2975 Nim 统计必胜走法个数

[原博客] POJ 2975 Nim 统计必胜走法个数

题目链接
题意介绍了一遍Nim取石子游戏,可以看上一篇文章详细介绍。
问当前状态的必胜走法个数,也就是走到必败状态的方法数。

我们设sg为所有个数的Xor值。
首先如果sg==0,它不可能有必胜走法,输出0.

对于任意一堆有a[i]个石子,若sg Xor a[i] <= a[i] ,那么我们就可以在a[i]里面取出sg Xor a[i]个石子,使得剩下石子Xor和为0,于是ans++。然后输出ans。

注意C/C++语言中^操作比<操作优先级低。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring> //by zrt//problem:using namespace std;typedef long long LL;const int inf(0x3f3f3f3f);const double eps(1e-9);int a[1005];int n;int main(){    #ifdef LOCAL    freopen("in.txt","r",stdin);    freopen("out.txt","w",stdout);    #endif    while(scanf("%d",&n),n){        int sg=0;        for(int i=0;i<n;i++){            scanf("%d",&a[i]);sg^=a[i];        }        int ans=0;        for(int i=0;i<n;i++){            if((sg^a[i])<=a[i]) ans++;        }        if(!sg) {            puts("0");continue;        }else printf("%d\n",ans);    }        return 0;}
View Code

 

[原博客] POJ 2975 Nim 统计必胜走法个数