题目链接
题目描述
给出$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;
}