题目
题目链接: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;
}