[CQOI2013]新NIM游戏（线性基）

链接：https://ac.nowcoder.com/acm/problem/19928
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。

本题的游戏稍微有些不同：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和Nim游戏一样。如果你先拿，怎样才能保证获胜？如果可以获胜的话，还要让第一回合拿的火柴总数尽量小。

输入描述:

第一行为整数k。即火柴堆数。

第二行包含k个不超过109的正整数，即各堆的火柴个数。

输出描述:

输出第一回合拿的火柴数目的最小值。如果不能保证取胜，输出-1。

示例1

输入

复制

6
5 5 6 6 5 5

输出

复制

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
struct L_B
{
    long long d[63],p[63];
    long long cnt;
    long long flag;//插入的能不能用已有数表示注意0的情况
    L_B()
    {
        memset(d,0,sizeof(d));
        memset(p,0,sizeof(p));
        cnt=0;
        flag=0;
    }
    void insert(long long val)
    {
        for (long long i=62; i>=0; i--)
            if (val&(1LL<<i))
            {
                if (!d[i])
                {
                    d[i]=val;
                    return ;
                }
                val^=d[i];
            }
        flag=1;
        return ;
    }
    long long query_max()
    {
        long long ret=0;
        for (long long i=62; i>=0; i--)
            if ((ret^d[i])>ret)
                ret^=d[i];
        return ret;
    }
    long long query_min()
    {
        for (long long i=0; i<=62; i++)
            if (d[i])
                return d[i];
        return 0;
    }
    void rebuild()
    {
        for (long long i=62; i>=0; i--)
            for (long long j=i-1; j>=0; j--)
                if (d[i]&(1LL<<j))
                    d[i]^=d[j];
        for (long long i=0; i<=62; i++)
            if (d[i])
                p[cnt++]=d[i];
    }
    long long kthquery(long long k)//第k小  2^cnt-k就是第k大
    {
        if(flag)
            k--;
        if(k==0)
            return 0;
        long long ret=0;
        if (k>=(1LL<<cnt))
            return -1;
        for (long long i=62; i>=0; i--)
            if (k&(1LL<<i))
                ret^=p[i];
        return ret;
    }
};
L_B merge(const L_B &n1,const L_B &n2)
{
    L_B ret=n1;
    for (long long i=62; i>=0; i--)
        if (n2.d[i])
            ret.insert(n1.d[i]);
    return ret;
}
vector<ll>v;
int main()//思想就是拿走基底的堆，让它无法异或等于0
{
    int k;
    ll n,x,sum=0;
    cin>>n;
    L_B p;
   for(int i=0;i<n;i++)
    {

        scanf("%lld",&x);
        v.push_back(x);
    }
    sort(v.begin(),v.end(),greater<ll>());//贪心倒着排
    for(int i=0; i<v.size(); i++)
    {
        int flag=0;
        ll num=v[i];
            ll x=num;
        for (long long i=62; i>=0; i--)//看集合中有没有这个数，有的话拿走
            if (x&(1LL<<i))
            {
                if (!p.d[i])
                {
                    flag=1;
                    break;
                }
                x^=p.d[i];
            }
        if(flag==0)
        {
            sum+=num;
        }
        else
            p.insert(num);
    }
cout<<sum;
}