P4301 [CQOI2013] 新Nim游戏
题目：
在传统的Nim游戏基础上加一步，在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和 Nim 游戏一样。
题解：
传统的Nim游戏策略：非空石子数量xor和等于0，则必败
A的目的是：不论B怎么拿，都无法剩下一个xor和等于0的子集。也就是A拿完后剩下一个线性基即可，因为线性基是线性无关的，肯定不为0，题目又要求A拿走尽量少的石头，先按照从大->小排序，求最大的线性基
代码：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);
return s*w;
}
const int maxn=1030;
ll a[maxn];
int L=60;
ll c[maxn];
bool insert(ll x){
for(int j=L;j>=0;--j){//从最高位开始看
if((x&(1ll<<j))==0) continue;
if(a[j]){//若如主元j已经存在，用a[j]消去x的第j位然后继续
x ^= a[j];
continue;
}
//让x当主元j，需要先用第k(k<j)个主元消去x的第k位
for(int k=j-1;k>=0;k--){
if(x & (1ll<<k)) x ^= a[k];
}
//接着用x去消掉第k(k>j)个主元的第j位
for(int k=L;k>j;k--){
if(a[k] & (1ll<<j)) a[k] ^= x;
}
a[j] = x;
return 1;
}
return 0;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>c[i];
}
sort(c+1,c+1+n,greater<int>());
ll ans=0;
for(int i=1;i<=n;i++)
{
bool w=insert(c[i]);
if(w==0)
{
ans+=c[i];
}
}
if(ans==0)cout<<-1<<endl;
else cout<<ans;
}
查看10道真题和解析
