【洛谷P4301】新Nim游戏

题目

题目链接:https://www.luogu.com.cn/problem/P4301
传统的 Nim 游戏是这样的:有一些火柴堆,每堆都有若干根火柴(不同堆的火柴数量可以不同)。两个游戏者轮流操作,每次可以选一个火柴堆拿走若干根火柴。可以只拿一根,也可以拿走整堆火柴,但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。

本题的游戏稍微有些不同:在第一个回合中,第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿,但不可以全部拿走。第二回合也一样,第二个游戏者也有这样一次机会。从第三个回合(又轮到第一个游戏者)开始,规则和 Nim 游戏一样。

如果你先拿,怎样才能保证获胜?如果可以获胜的话,还要让第一回合拿的火柴总数尽量小。

思路

傻子题。
假设先手取完后,剩余石子堆中存在若干堆异或和为 0),显然后手必胜。所以我们需要把所有可以异或变成 0) 的石子堆都取掉。
假设没有第一回合拿的石子最少的限制,那么直接把数字依次插入线性基,如果这个数字无法插入进去就加入答案。
但是此时要求拿的尽量少,那就排个序就好了。
时间复杂度 Onlog A))

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=110,LG=30;
int n,d[N],a[N];
ll ans;

void insertint x)
{
	int tmp=x;
	for int i=LG;i>=0;i--)
		if x&1<<i))
		{
			if !d[i]) { d[i]=x; return; }
			x^=d[i];
		}
	ans+=tmp;
}

int main)
{
	scanf"%d",&n);
	for int i=1;i<=n;i++)
		scanf"%d",&a[i]);
	sorta+1,a+1+n);
	for int i=n;i>=1;i--)
		inserta[i]);
	printf"%lld",ans);
	return 0;
}

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注