题目链接

BJWC2011元素

题目描述

给出$n$对数字，每对第一个为$num$，每对第二个为$val$，求在若干个$num$异或和不为$0$的时候的$val$和的最大值。

题目思路

我们对每对数据的val进行排序，然后插入每个的$num$，如果能插入就加上此时的$val$，这运用了贪心的思想。

为什么呢？我一开始也提问，如果有$a,b,c,d,e$多组数据按照$val$依次递减，有没有可能不选$a$呢？（因为$a$的$num$是第一个插入的，必定选）

你认为$b$和$c$在一起搭配$val$的和可能比a的和大，错了，那么我$a$和$b$肯定更大，这样可能不能理解，那么我们这样看：假如$a,b,c$的$num$异或和为$0$，说明不能同时取，这是和最优解肯定是$a,b$一起然后不选$c$，这时候我们找下面的d,e，这样的话有两种情况：1）如果d ^ e = c的话我们只能选其中一个，不然a ^ b ^ d ^ e = 0，那我们肯定选d；2）如果d ^ e != c那么我们都可以选。

能不能选a的问题还是没有解决，假如我选了$b,c$不选$a$，此时也是两种情况，一种只能选一个，一种多选，那么我肯定选择$a$而不是选择$c$，因为$a.val \geq c.val$，所以这种贪心是正确的。

代码

ll p[N],x,ans,d[N],cnt,flag;
int n,m;
struct node
{
    ll num,val;
}a[N];
inline bool insert(ll x)
{
    for (int i=62;i>=0;i--)
        if (x>>i)
            if (p[i])
                x^=p[i];
            else
            {
                p[i]=x;
                return 1;//插入成功
            }
    return 0; //插入失败
}
bool cmp(node x,node y)
{
    return x.val>y.val;
}
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i].num>>a[i].val;
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<=n;i++)
        if (insert(a[i].num))//插入成功
            ans+=a[i].val;
    cout<<ans;
}