P4301 [CQOI2013] 新Nim游戏 线性基

题目链接

题意：

两个人进行游戏，有 \(n\) 堆火柴，每堆有若干根，在第一个回合中，双方可以直接拿走若干个整堆的火柴，可以一堆不拿，但不可以全部拿走。接下来的回合进行 \(Nim\) 游戏。 现在你是先手，第一回合如何拿才能保证获胜，并且让第一回合拿的数量尽量少。

思路：

我们知道 \(Nim\) 游戏火柴数异或和为 \(0\) 则先手必败。所以我们想要获胜，必须保证后手无论怎么操作无法使剩余火柴数异或和为 \(0\) 即可。考虑线性基，如果这个数可以被已经插入的数表示出来，那么我们就必须第一回合把这堆取走，反之，则直接插入线性基即可。为了使得第一回合拿的火柴总数尽量小，我们从大到小进行枚举。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 0;

int p[M];
void insert(int x){
    for(int i=63;i>=0;i--){
        if(x>>i&1){
            if(!p[i]){
                p[i]=x;
                return;
            }
            x^=p[i];
        }
    }
}

bool find(int x){
    for(int i=63;i>=0;i--){
        if(x>>i&1){
            if(!p[i]) return false;
            x^=p[i];
        }
    }
    return true;
}
void Showball(){
   int k;
   cin>>k;
   vector<int> a(k);
   for(int i=0;i<k;i++){
     cin>>a[i];
   }
   sort(all(a));
   LL res=0;
   for(int i=k-1;i>=0;i--){
     if(find(a[i])) res+=a[i];
     else insert(a[i]);
   }
   cout<<res<<endl;   
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}