BJWC 2011 元素 题解

       题目传送门
       题目大意：有n个东西，每个东西能选当且仅当它的元素序号不能通过之前选过的东西的元素序号异或得到，在此前提下，求魔力的最大值。
       如果没看过我写的关于线性基的博客，请先阅读一下吧，特别是理解其中的第三条性质。
       根据这条性质，我们可以知道，一个序列，能够插入到线性基里面的元素是一定的，那么既然只能插那么多个，显然优先插魔力值大的进去呀！
       可能有人会问，打个比方，原来是可以插5个魔力值为5的进去，但是如果优先从大开始插入，就只能插魔力值为6,1,1,1,1了，那不是显然没那么优了吗？
       这种情况是不可能有的啦。
       假如你要是提出了这种问题，那你一定是没有认真看性质3的证明。
       根据那个捞得一比的证明，我们可以知道，如果要将一个原来插入不进线性基的元素插入到线性基里面，只需要删去线性基里面的一个特定的元素就好了（这个特定的元素可能有多个，至于这个特定的元素是谁，你只需要细细品味一下我的博客就知道了~），所以，要将一个魔力值为6的插入到5个魔力值为5的里面去的话，其实只需要去掉其中一个特定的5就好了。

总的来说

       按这种贪心的做法得到的一定是最优的，不可能因为一个元素而导致多个元素不能插入，就算去掉这个元素，也只能插入那多个元素中的一个。
       代码就很简单了：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long

struct node{ll x;int y;};
node a[1010];
int n,ans=0;
ll d[70];
bool cmp(node x,node y){return x.y>y.y;}
bool add(ll x)
{
    for(int i=62;i>=0;i--)
    {
        if(x&(1ll<<i))
        {
            if(!d[i])
            {
                d[i]=x;
                return true;
            }
            else x^=d[i];
        }
    }
    return false;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%lld %d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    if(add(a[i].x))ans+=a[i].y;
    printf("%d",ans);
}