G59 台阶型 Nim游戏【博弈论】

/*
解析：只考虑奇数位，偶数位只当作容器（偶数位的硬币数目是不管的），游戏的SG值为所有奇数位硬币数的异或和。
证明一个问题：我如果能让SG=0，那么不管你怎么操作，我也能一次让SG再次等于0。
证明开始：如果先手可以让当前SG和为0，那么对方有以下两种操作：
一：如果对方在奇数位上取硬币，那么我们也类似nim在奇数位上取硬币使SG值回到0；
二：如果对方在偶数位上取硬币。那么我们就把他刚刚从偶数位上传到奇数位上的硬币数。原封不动的再传回偶数位。
所以得证。
*/
#include <cstdio>//by Lofty
#include <cstring>
#include <algorithm>
using namespace std;
using LL = long long;
constexpr int N = 1e6 + 5;
LL n, a[N];
int main()
{
    while (scanf("%lld", &n) != EOF)
    {
        LL ans = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            if (i & 1)//相当于i为奇数
                ans ^= a[i];//奇数阶梯就相当于石子堆 
        }
        if (!ans) { puts("0"); continue; }
        LL res = 0;
        for (int i = 1; i <= n; i++)
        {
            if (i & 1)//奇数阶梯就尝试减少一些硬币来达到平衡态 
            {
                if ((ans ^ a[i]) <= a[i])//方案是否合法 
                    res++;
            }
            else//偶数阶梯就尝试向奇数阶梯增加一些硬币来达到平衡态 
            {
                LL s = (ans ^ a[i - 1]) - a[i - 1];
                if (s > 0 && s <= a[i])//方案是否合法 
                    res++;
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}

G59 台阶型 Nim游戏【博弈论】

/*
解析：只考虑奇数位，偶数位只当作容器（偶数位的硬币数目是不管的），游戏的SG值为所有奇数位硬币数的异或和。
证明一个问题：我如果能让SG=0，那么不管你怎么操作，我也能一次让SG再次等于0。
证明开始：如果先手可以让当前SG和为0，那么对方有以下两种操作：
一：如果对方在奇数位上取硬币，那么我们也类似nim在奇数位上取硬币使SG值回到0；
二：如果对方在偶数位上取硬币。那么我们就把他刚刚从偶数位上传到奇数位上的硬币数。原封不动的再传回偶数位。
所以得证。
*/
#include<cstdio>//by Lofty
#include<cstring>
#include<algorithm>
using namespace std;
using LL=long long;
constexpr int N=1e6+5;
LL n,a[N];
int main()
{
	while(scanf("%lld",&n)!=EOF)
	{
		LL ans=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			if(i&1)//相当于i为奇数
			ans^=a[i];//奇数阶梯就相当于石子堆 
		}
		if(!ans){puts("0");continue;}
		LL res=0;
		for(int i=1;i<=n;i++)
		{
			if(i&1)//奇数阶梯就尝试减少一些硬币来达到平衡态 
			{
				if((ans^a[i])<=a[i])//方案是否合法 
					res++;
			}
			else//偶数阶梯就尝试向奇数阶梯增加一些硬币来达到平衡态 
			{
				LL s=(ans^a[i-1])-a[i-1];
				if(s>0&&s<=a[i])//方案是否合法 
					res++;
			}
		}
		printf("%lld\n",res);
	}
	return 0;
}