大致题意： 有(n)个物品，每个物品有两个属性：编号和价值。现让你选出一个物品集合，使得其不存在某个子集编号异或和为(0)，求出满足条件的集合中物品价值总和的最大值。
前言
(Jan 28th)刷题计划（6/6），算法标签：贪心、线性基。
以这道有趣的贪心题结尾，终于完成了今天的任务！
性质
考虑已知一个合法集合({a_1,a_2,...,a_k}(Val(a_1)ge Val(a_2)ge...ge Val(a_k)))，现在加进去一个新的元素(x)，结果所得到的集合就不合法了。
仔细推一推，我们可以发现一个性质：这个新集合中仅有一个子集编号异或和为(0)。
假设如果有两个子集({a_{i_1},a_{i_2},...,a_{i_{ki}},x})和({a_{j_1},a_{j_2},...,a_{j_{kj}},x})编号异或和为(0)。
则有：
把两个式子合并起来，就得到：
约掉式子两边相同的部分，假设得到一个新的等式：
其中，(u_1,u_2,...,u_{k_u},v_1,v_2,...,v_{k_v})互不相同。
然后把这个等式两边同时异或上(Pos(a_{v_1}) xor Pos(a_{v_2}) xor ... xor Pos(a_{v_{kv}}))，右式就变成了(0)，得到：
也就是说，子集({u_1,u_2,...,u_{k_u},v_1,v_2,...,v_{k_v}})的编号异或和为(0)，这与({a_1,a_2,...,a_k})是合法的矛盾。
所以，这一性质得证。
利用性质
我们假设这个子集为({a_{i_1},a_{i_2},...,a_{i_{ki}},x})。
如果(Val(a_{i_{ki}})ge Val(x))，那么(x)的加入完全是没有意义的。
否则，(Val(a_{i_{ki}})<Val(x))。
考虑如果我们用(x)去替换(a_{ki})，由于：
所以：
而根据我们之前得到的性质，其余的子集编号异或和也皆不为(0)，所以得到的这个新的集合是合法的。
而由于(Val(x)>Val(a_{i_{ki}}))，所以得到的新的集合比原集合的价值总和更大。
贪心
综上所述，我们可以得到一个贪心的想法：把所有物品按照价值从大到小排序，然后能加就加入集合。
根据我们之前推出来的性质，这个想法显然是正确的。
那么新的问题就是如何判断一个物品能否加入当前集合。
这就需要用到线性基了。
如果一个数字能够加入线性基，那么它就能加入当前集合，否则就不能。
具体实现可以详见代码。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000
#define LV 64
#define LL long long
using namespace std;
int n;LL v[LV+5];struct Item {LL x;int y;I bool operator < (Con Item& o) Con {return y>o.y;}}s[N+5];//把物品绑成结构体便于排序
I bool Ins(LL x) {for(RI i=LV;~i;--i) if((x>>i)&1) {if(!v[i]) return v[i]=x;else x^=v[i];}return 0;}//插入线性基
int main()
{
RI i,t=0;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%lld%d",&s[i].x,&s[i].y);
for(sort(s+1,s+n+1),i=1;i<=n;++i) Ins(s[i].x)&&(t+=s[i].y);return printf("%d",t),0;//能加就加
}