[CQOI2013]新NIM游戏

[CQOI2013]新NIM游戏

思路

NIM游戏，先手获胜的条件就是，所以值异或后不为0，也就是在进行完第二轮后，场面不为0即可获胜。
也就是让第二***作的人不能从这若个个数得到0，这个判断就可以用线性基来完成了，
同时我们又要保证第一轮拿的值最小，所以我们考虑贪心，优先把较大的放入线性基
这样我们就会每次都取出符合要求的较小的数字了，然后累加答案即可。

代码

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct linearbasis {
    ll base[64], flag, cnt;

    bool add(ll x) {
        for(int i = 62; ~i; i--) {
            if(x >> i & 1) {
                if(!base[i]) {
                    base[i] = x;
                    return true;
                }
                x ^= base[i];
            }
        }
        flag = 1;
        return false;
    }

    ll query_max() {
        ll ans = 0;
        for(int i = 62; ~i; i--) {
            if((ans ^ base[i]) > ans) {
                ans ^= base[i];
            }
        }
        return ans;
    }

    ll query_min() {
        for(int i = 0; i <= 62; i++) {
            if(base[i]) {
                return base[i];
            }
        }
    }

    void rebuild() {
        cnt = 0;
        for(int i = 62; i >= 0; i--) {
            for(int j = i - 1; j >= 0; j--) {
                if(base[i] >> j & 1) {
                    base[i] ^= base[j];
                }
            }
        }
        for(int i = 0; i <= 62; i++) {
            if(base[i]) {
                ll temp = base[i];
                base[i] = 0;
                base[cnt++] = temp;
            }
        }
    }

    ll query_k(ll k) {
        k -= flag;
        if(k == 0) return 0;
        if(k >= 1ll << cnt) return -1;
        ll ans = 0;
        for(int i = 62; ~i; i--) {
            if(k >> i & 1) {
                ans ^= base[i];
            }
        }
        return ans;
    }
    void init() {
        memset(base, 0, sizeof base), flag = cnt = 0;
    }
}a;

int b[110], n;

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
    }
    sort(b + 1, b + 1 + n, greater<int> ());
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        if(!a.add(b[i])) {
            ans += b[i];
        }
    }
    printf("%lld\n", ans);
    return 0;
}