poj 3480 John anti-SG博弈

题意：

跟经典的nim除了胜利条件不一样（nim当游戏者面对空的决策集判负，anti-SG当游戏者面对空的决策集判负），其他都一样。

分析：

设全局状态为s,单个游戏为t。先手必胜条件：(g(s)!=0&&Existg(t)>1)||(g(s)==0&&Anyg(t)<=1) g(w)指状态w的grundy值。这个定理用必胜态可到必败态，必败态必到必胜态的思想易证。

代码：

//poj 3480
//sep9
#include <iostream>
using namespace std;int main()
{int cases;scanf("%d",&cases);while(cases--){int n,maxx=0;scanf("%d",&n);int ans=0;while(n--){int x;scanf("%d",&x);maxx=max(maxx,x);ans=ans^x;}if((ans!=0&&maxx>1)||(ans==0&&maxx<=1)) puts("John");else puts("Brother");}return 0;	
}