HDU 2509 Nim博弈变形

时间:2021-07-17 14:56:34

1、HDU 2509  

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

3、总结: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 ;
}