HDU 2509 Nim博弈变形

２、题意：n堆苹果，两个人轮流，每次从一堆中取连续的多个，至少取一个，最后取光者败。

３、总结：Nim博弈的变形，还是不知道怎么分析，，，，看了大牛的博客。　传送门　

首先给出结论:先手胜当且仅当（1）所有堆石子数都为1且游戏的SG值为0,（2）存在某堆石子数大于1且游戏的SG值不为0。
证明：
（1）若所有堆石子数都为1且SG值为0，则共有偶数堆石子，故先手胜。
（2）　i)只有一堆石子数大于1时，我们总可以对该堆石子操作，使操作后石子堆数为奇数且所有堆得石子数均为1 ii)有超过一堆石子数大于1时，先手将SG值变为0即可，且总还存在某堆石子数大于1。因而，先手胜。

#include<bits/stdc++.h>

#define F(i,a,b) for (int i=a;i<b;i++)

#define FF(i,a,b) for (int i=a;i<=b;i++)

#define mes(a,b) memset(a,b,sizeof(a))

#define INF 0x3f3f3f3f

using namespace std;

typedef long long LL;

const int N=;

int main()

{

    int n,a[];

    while(~scanf("%d",&n)) {

        int ans=,flag=;

        F(i,,n) {

            scanf("%d",&a[i]);

            ans^=a[i];

            if(a[i]>) flag=;

        }

        if(!flag) {

            if(ans) puts("No");

            else puts("Yes");

        } else {

            if(ans) puts("Yes");

            else puts("No");

        }

    }

    return ;

}

巴特西

HDU 2509 Nim博弈变形

最新文章

热门文章