bzoj 3105: [cqoi2013]新Nim游戏【线性基+贪心】

nim游戏的先手必胜条件是所有堆的火柴个数异或和为0，也就是找一个剩下火柴堆数没有异或和为0的子集的方案，且这个方案保证剩下的火柴个数总和最大

然后我就不会了，其实我到现在也不知道拟阵是个什么玩意……

详见：https://blog.csdn.net/wyfcyx_forever/article/details/39477673

其实想2460一样用贪心证明也行

总之用按大小从大到小假如线性基然后剩下的就是答案

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=105;

int n,top,a[N],b[N],q[N];

long long sm,ans;

bool cmp(const int &a,const int &b)

{

	return a>b;

}

int main()

{

	scanf("%d\n",&n);

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]),sm+=a[i];

	sort(a+1,a+n+1,cmp);

	for(int i=1;i<=n;i++)

	{

		int t=a[i];

		for(int j=30;j>=0;j--)

			if(a[i]&(1<<j))

			{

				if(!b[j])

				{

					b[j]=i;

					break;

				}

				else

					a[i]^=a[b[j]];

			}

		if(a[i])

			ans+=t;

	}

	if(ans)

		printf("%lld\n",sm-ans);

	else

		puts("-1");

	return 0;

}

巴特西

bzoj 3105: [cqoi2013]新Nim游戏【线性基+贪心】

最新文章

热门文章