BZOJ 3105: [cqoi2013]新Nim游戏

• 线性基+贪心

即求一个异或线性无关的集合的元素和的最大值

贪心的正确性见拟阵

CODE

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int n, v[MAXN], a[30];
inline bool ins(int x) {
    for(int i = 29; ~i; --i)
        if(x&(1<<i)) {
            if(a[i]) x ^= a[i];
            else {
                a[i] = x;
                return 1;
            }
        }
    return 0;
}
int main() {
    scanf("%d", &n);
    if(n == 1) return puts("-1"), 0;
    long long ans = 0;
    for(int i = 1; i <= n; ++i)
        scanf("%d", &v[i]), ans += v[i];
    sort(v + 1, v + n + 1);
    for(int i = n; i; --i)
        if(ins(v[i])) ans -= v[i];
    printf("%lld
", ans);
}