【转载】尼姆博弈 - dblank

【转载】尼姆博弈

尼姆博弈:

http://www.cnblogs.com/kuangbin/archive/2011/08/28/2156426.html

题目1:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根,

可将一堆全取走,但不可不取,最后取完者为胜,求必胜的方法。

题目2:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根,

可将一堆全取走,但不可不取,最后取完者为负,求必胜的方法。

对应问题一:

HDU 1850:Being a Good Boy in Spring Festival

http://acm.hdu.edu.cn/showproblem.php?pid=1850

除此之外还要求出先手的人如果想赢,第一步有几种选择

我们将情景设为取苹果,设k[i]表示第i个框里有k[i]个苹果,再设ans = a[i]^a[2]^……^a[n]

那么显然有以下三点规律:

①:当ans==0时为必输态T态(谁面对这种状态谁必输),否则为必赢态S态,其中所有苹果全被取完的状态

就是T态

②:对于T态,无论怎么取都将变为S态,对于S态,一定有方法取成T态,这也是①的证明

③:对于S态每一项k[i],如果ans^k[i]<k[i],就说明可以从k[i]堆中取出一定数量的苹果使其剩下ans^k[i]个苹

果,这样就成功转为了T态(显然(ans^k[i])^(ans^k[i])==0)

#include<stdio.h>  
int main(void)  
{  
    int n, i, k[105], ans, sum;  
    while(scanf("%d", &n), n!=0)  
    {  
        ans = sum = 0;  
        for(i=1;i<=n;i++)  
        {  
            scanf("%d", &k[i]);  
            ans ^= k[i];  
        }  
        for(i=1;i<=n;i++)  
        {  
            if((ans^k[i])<=k[i])  
                sum++;  
        }  
        if(ans==0)  
            printf("0n");  
        else  
            printf("%dn", sum);  
    }  
    return 0;  
}

对应问题2:

HDU 2509:Be the Winner

http://acm.hdu.edu.cn/showproblem.php?pid=2509

与情况1极其相似,若面对T态还是必输,面对S态还是必赢,但是有特例!

如果每一堆苹果要不没有,要不就只有一个,那么当苹果总数为偶数时必赢,否则必输

#include<stdio.h>  
int main(void)  
{  
    int n, i, k[105], ans, flag, sum;  
    while(scanf("%d", &n)!=EOF)  
    {  
        ans = flag = sum = 0;  
        for(i=1;i<=n;i++)  
        {  
            scanf("%d", &k[i]);  
            ans ^= k[i];  
            if(k[i]>1)  
                flag = 1;  
            if(k[i]>0)  
                sum++;  
        }  
        if(flag==0)  
        {  
            if(sum%2==0)  
                printf("Yesn");  
            else  
                printf("Non");  
        }  
        else  
        {  
            if(ans==0)  
                printf("Non");  
            else  
                printf("Yesn");  
        }  
    }  
    return 0;  
}  

 

相关文章

发表新评论