[BZOJ3759] Hungergame

2018-08-11

lolifamily

题解

线性基 Nim

转载自joyouth

首先我们不难看出如果存在一个异或和为 $0$ 的子集，那么先手必胜，否则先手必败

证明如下：

首先如果至少存在一个异或和为 $0$ 的子集，那么一定存在一个异或和为 $0$ 的子集使得选取之后剩下的数的任意子集异或和不为 $0$
假设我们已经选取了一个异或和为 $0$ 的子集，无论后手怎么做，我们总是有办法使得当前选取的子集异或和为 $0$ ，因为后手无论是拿石子还是取石子之后，当前子集异或和不等于 $0$ ，根据 Nim 游戏可知，此时先手一定有方案使得异或和为 $0$

至此，我们证明了如果至少存在一个异或和为 $0$ 的子集，先手必胜

那么题目就转化为求是否存在一个子集异或和为 $0$ ，用线性基即可

Description

由于施惠国的统治极其残暴，每年从 $13$ 个区中每个区中选出 $2$ 名” 贡品” 参加饥饿游戏，而参加游戏的人必须在险恶的自然环境中杀死其余的人才能存活。游戏只会有一个人活下来。凯特尼斯・伊夫狄恩和同区的皮塔・麦拉克在历经千难万阻后活了下来，然而残忍的游戏只允许一人存活，正当两人准备同时吃下有毒的果实自杀的时候，统治者被打动了，他说：你们两个人跟我玩一个游戏，你赢了，我就让你们两个都活下来。女主角凯特尼斯・伊夫狄恩接受了挑战。

这个游戏是这样的，有 $𝑛$ ( $𝑛 \leq 20$ ) 个箱子，每个箱子里面有 $𝑎 𝑖$ ( $𝑎 𝑖 \leq 109$ ) 个石头（怎么放进去的我就不知道了），两个人轮流进行操作（女主角先手），每一次操作可以将任意个（大于 $0$ 个）未打开的箱子打开（一开始所有的箱子都是关闭的），或者在已经打开的一个箱子里拿走任意个（大于 $0$ 个）石头（不能超过这个箱子现有的石头数）。最后谁无法操作谁就输了。

现在给出 $𝑛$ ，和这 $𝑛$ 个箱子里的石头数 $𝑎 𝑖$ ，女主角想知道她是否有绝对的把握取得胜利（很明显她的对手” 统治者” 是绝顶聪明的）。

Input

第一行有一个正整数 $𝑇$ （表示有 $𝑇$ 组测试数据），对于每组测试数据有两行，第一行为一个正整数 $𝑛$ ，接下来有 $𝑛$ 个数，第 $𝑖$ 个数表示 $𝑎 𝑖$ 。

Output

有 T 行：对于每一个测试数据，如果先手可以必胜则输出 “Yes”，否则输出 “No”（没有引号）。

Sample Input

1
5
2
5
3
18 11 16 19 15
4
5
5
18 12 17 10 18
6
5
7
17 7 1 10 1
8
5
9
19 5 16 19 8
10
5
11
18 18 7 4 9

Sample Output

1
No
2
Yes
3
Yes
4
Yes
5
Yes

HINT

$100 %$ 的数据： $𝑛 \leq 20$ ， $𝑇 \leq 10$ ， $𝑎 𝑖$ 不超过 $109$ ；

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
int pos[35];
7
inline bool Insert(int x)
8
{
9
  int i;
10
  for(i=31;i>=0;--i)
11
  {
12
    if((x>>i)&1)
13
    {
14
      if(!pos[i]){pos[i]=x;break;}
15
      else x^=pos[i];
16
    }
17
  }
18
  if(x)return false;
19
  else return true;
20
}
21
int main(void)
22
{
23
  int i,T,n,x,ans;
24
  scanf("%d",&T);
25
  while(T--)
26
  {
27
    memset(pos,0,sizeof(pos));
28
    scanf("%d",&n);ans=0;
29
    for(i=1;i<=n;++i)
30
    {
31
      scanf("%d",&x);
32
      ans+=Insert(x);
33
    }
34
    if(ans)printf("Yes\n");
35
    else printf("No\n");
36
  }
37
  return 0;
38
}