线性基的简单贪心证明&新NIM游戏题解

异或线性基是一个集合可以通过异或表示原集合的所有数.线性基的贪心证明正确性(简要),假定1,4,5.
我们可以选择插入1,4|1,5,显然插入4,5更优.
简单的更下这个题题解.
我们知道原nim游戏,假如堆数异或和为0且你现在动,那么你必输.我如何才能使得到这个东西呢?换句话来说,我们制造一个别人通过取或不取一堆得都不能使异或和为0则可以,那么我们只需维护一个最大的线性基即可.
从大到小排序,然后套个线性基就好了.
至于nim游戏?这就不用讲了吧..以后会做博弈论+dp专题的.maybe退役?
代码如下:

#include <bits/stdc++.h>
using namespace std;
long long a[105];
long long b[105];
bool cmp(int a,int b)
{
    return a>b;
}

int main()
{
    int n;
    long long sum=0;
    cin>>n;
    for(int i=1;i<=n;i++)   {cin>>a[i];sum+=a[i];}
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)   b[i]=a[i];
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0) continue;
        ans+=b[i];
        for(int j=30;j>=0;j--)
        {
            if(a[i]>>j&1)
            {
                for(int k=1;k<=n;k++)
                {
                    if((a[k]>>j&1)&&i!=k)
                    {
                        a[k]^=a[i];
                    }
                }
                break;
            }
        }
    }
    cout<<sum-ans<<endl;
    return 0;
}