Nim游戏
BZOJ 1299: [LLH邀请赛]巧克力棒 对于一个初始局面,如果我们可以把它分成一个P态和一个N态.我们一次头把P态全部取出,对于这个P态我们就是后手了.我们强迫对方取出N态的巧克力,这样对于这个N态我们变成了先手,可以保证必胜了.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=20; int n; int num[Maxn]; int sum; bool dfs(int now,int uesd,int sg){ if (sg==0 && uesd>0) return true; if (now>n) return false; return dfs(now+1,uesd,sg)||dfs(now+1,uesd+1,sg^num[now]); } int main(){ for (int i=1;i<=10;i++){ scanf("%d",&n); for (int j=1;j<=n;j++){ scanf("%d",&num[j]); } if (!dfs(1,0,0)) printf("YES\n"); else printf("NO\n"); } return 0; } |
