[BZOJ1299]巧克力棒
一.前言
这是一道博弈论的题。
二.题意简述
进行10次游戏，每次有若干个巧克力棒，长度不一。可以的操作是抽出若干个巧克力棒放入游戏局面，或者从当前的局面当中选一个巧克力棒吃掉（nim游戏），问先手是否会败。
三.解题思路
现在我先手，对面也是个心理肮脏的家伙。既然是一个nim游戏，我必定要构造一手使得当前局面异或起来为0，且就算你抽出其他棒也会nim值在我下一步变回0.实际上，就是这样的思路。
那么第一手很明显了，我要取一个组合，且他们的异或值为0.这样的组合可以随便取吗？显然不行，为了达到目的我要取一个最长的，不然我取一个0，对手又取出一个0，就是我要输了。
取了一个最长的组合之后，若是对手抽棒，对于一个不为0的nim值来讲，一步之内你就又会变为0.对手必败无疑了。
在代码实现方面，由于n<14，可以深搜，但是虽然上文说要找一个最长的，但是我只需要找到一个为0的就行（可以想想为什么）。
四.CODE
#include<bits/stdc++.h>
#define m_for(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
int n,a[15];
bool vis[15];
bool dfs(int last,int nim){
if(last!=0&&nim==0)return 1;
m_for(i,last+1,n){
if(!vis[i]){
vis[i]=1;
bool res=dfs(i,nim^a[i]);
vis[i]=0;
if(res==1)return res;
}
}
return 0;
}
int main(){
m_for(u,1,10){
cin>>n;memset(vis,0,sizeof(vis));
m_for(i,1,n)cin>>a[i];
if(dfs(0,0))cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}