bzoj 1299 [LLH邀请赛]巧克力棒
内容
Description
TBL和X用巧克力棒玩游戏。每次一人可以从盒子里取出若干条巧克力棒，或是将一根取出的巧克力棒吃掉正整数长度。TBL先手两人轮流，无法操作的人输。 他们以最佳策略一共进行了10轮（每次一盒）。你能预测胜负吗？
Input
输入数据共20行。 第2i-1行一个正整数Ni，表示第i轮巧克力棒的数目。 第2i行Ni个正整数Li,j，表示第i轮巧克力棒的长度。
Output
输出数据共10行。 每行输出“YES”或“NO”，表示TBL是否会赢。如果胜则输出”NO”,否则输出”YES”
Sample Input
3
11 10 15
5
13 6 7 15 3
2
15 12
3
9 7 4
2
15 12
4
15 12 11 15
3
2 14 15
3
3 16 6
4
1 4 10 3
5
8 7 7 5 12
Sample Output
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
HINT
20%的分数，N<=5，L<=100。
40%的分数，N<=7。 50%的分数，L<=5,000。
100%的分数，N<=14，L<=1,000,000,000。
题解
这道题的题意就是有n堆石子，之后你每次操作有两种做法
第一种是在已经建立的nim游戏上进行nim游戏。
第二种是在未被选的堆中选取若干堆加入这个nim游戏中。
然而这道题的必败态可以这么建:
如果是先手的话，我可以建立出来一个异或和为0的nim游戏，此时后者有两种做法：
第一种是在该nim游戏上游戏，则先手又可以将这个游戏的异或和变为0
第二种是选取新的石子堆加入原来的nim游戏。
如果是先手的话不会给后手机会来添加一组异或和为0的石子堆。所以先手建立的一定是选取最多的元素的异或和为0的nim游戏，此时，在剩下的堆里，一定不能有一组石子堆的异或和为0，这很显然。
所以如果后者选取第二种做法，那么会使得原有的Nim游戏的异或和不为0，所以先手又可以将这个游戏的异或和变为0。
即如果先手开始选取最多石子堆来建立一个异或和为0的nim游戏，则后者必败。
又可以转化一下，如果先手可以选出一个任意数量的石子堆建立的异或和为0的nim游戏，则后者必败。
然后枚举一下所有的状态就可以了，$2^14$
#include <cstdio>
#include <cstring>
using namespace std;
int vis[20],a[20],flag,T,n;
void dfs(int now)
{
if (now>n)
{
int ans=0,p=0;
for (int i=1;i<=n;i++)
if (vis[i])
ans^=a[i],p=1;
if (!ans&&p)
flag=1;
return;
}
if (!flag)
vis[now]=1,dfs(now+1),
vis[now]=0,dfs(now+1);
}
main()
{
// scanf("%d",&T);
T=10;
while(T--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(vis,0,sizeof vis);
flag=0;
dfs(1);
if (flag) puts("NO");
else puts("YES");
}
}