bzoj 3105 新Nim游戏

Posted on | Views:

贪心求解最大权值线性无关组.

$A$ 先拿走一堆石子, $B$ 再拿走一堆石子,然后做 $Nim$ 游戏.

如果 $A$ 拿了之后给 $B$ 留下的石子中存在一个子集,它们的异或和为 $0$ , $B$ 就可以把其它的石子拿走, $A$ 就败了.

所以 $A$ 要拿走最少的石子,使剩下的石子在异或意义下线性无关.

那么就是要求解最大权值线性无关组,用拟阵的那一套理论,贪心处理.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=100+10;
int n,a[MAXN],c[32];
ll ans=0;
void ins(int x,int val)
{
	for(int i=31;i>=0;--i)
		if((x>>i)&1)
		{
			if(!c[i])
			{
				c[i]=x;
				break;
			}
			else
				x^=c[i];
		}
	if(!x)
		ans+=val;
}
int main()
{
	n=read();
	if(!n)
		return puts("-1")&0;
	for(int i=1;i<=n;++i)
		a[i]=read();
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	for(int i=1;i<=n;++i)
		ins(a[i],a[i]);
	cout<<ans<<endl;
	return 0;
}