Solution [CQOI2013]新Nim游戏

，线性基，贪心

分析:

首先明确先手必胜，证明：

假设有\(n\)堆，先手取\(n-1\)堆，第二个人因为不能取完只能不取，只剩一堆石子显然\(Nim\)和大于\(0\)，因此先手必胜

再来看如何求解，假如先手取几堆石子后，第二个人想要获胜，操作后剩下石子的\(Nim\)和就必须为\(0\)

于是问题转化如下

先手取若干堆石子，使得剩下石子数不存在一个子集使得石子数量异或和为\(0\)，换句话说，剩下的石头数在异或意义下是线性无关的

求第一次取的石头数可以反过来，求剩下的石子数，要使第一次取的石头数尽量少，剩下的石头权值和就要尽量大。也就是说，我们要求权值和最大的线性无关子集

考虑贪心，将石子数从大到小排序，依次插入线性基，插入失败说明选了该堆石子就构成了线性相关子集，必须第一次取掉它

因为异或是不进位意义下的加法，所以第一次取该堆石子一定比取和它线性相关的那多堆石子要优秀，其实就是[BJWC2011]元素这题

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
inline int read(){
    int x = 0;char c = getchar();
    while(!isdigit(c))c = getchar();
    while(isdigit(c))x = x * 10 + c - '0',c = getchar();
    return x;
}
int n,val[128],base[32];
long long ans;
inline bool insert(int x){
    for(int i = 30;i >= 0;i--){
        if(!(x >> i))continue;
        if(!base[i]){
            base[i] = x;
            return true;
        }
        x ^= base[i];
    }
    return false;
}
int main(){
    n = read();
    for(int i = 1;i <= n;i++)val[i] = read();
    sort(val + 1,val + 1 + n,[](int a,int b){return a > b;});
    for(int i = 1;i <= n;i++)
        if(!insert(val[i]))ans += val[i];
    printf("%lld\n",ans);
    return 0;
}

石子

题解 P4301 【[CQOI2013]新Nim游戏】

Solution [CQOI2013]新Nim游戏