【POJ2975】Nim (博弈)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 04 月 11 日

n堆石子,然后问如果必胜的话有多少种移动方法(一步)。
因为答案最多只有n,令ans=a1^a2^...^an,如果需要构造出异或值为0的数,
而且由于只能操作一堆石子,所以对于某堆石子ai,现在对于ans^ai,就是除了ai以外其他的石子
的异或值,如果ans^ai<=ai,那么对于ai的话,是可以减小到ans^ai的值,然后使得所有数 的异或值为0,也即转移到了必败态。

#include<cstdio>  
using namespace std;  
int piles[1005];  
int main()  
{freopen("1.txt","r",stdin);  
    int n,temp,ans,sumcount;  
    while(scanf("%d",&n)!=EOF && n)  
    {  
        sumcount=0;  
        for (int i=0;i<n;i++)  
        {  
            scanf("%d",&piles[i]);  
        }  
        ans=piles[0];  
        for (int i=1;i<n;i++)  
        {  
            ans ^=piles[i];  
        }  
        if(ans==0) {printf("0\n"); continue;}  
        for (int i=0;i<n;i++)  
        {  
            if((ans^piles[i])<=piles[i]) sumcount++;  
        }  
        printf("%d\n",sumcount);  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期日, 2017 年 12 月 17 日