元素
Time Limit: 20 Sec Memory Limit: 128 MB[][][]Description
相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。
那时人们就认识到，一个法杖的法力取决于使用的矿石。 一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消”。 特别地，如果在炼制过程中使用超过一块同一种矿石，那么一定会发生“魔法抵消”。 后来，随着人们认知水平的提高，这个现象得到了很好的解释。 经过了大量的实验后，著名法师 Dmitri 发现：如果给现在发现的每一种矿石进行合理的编号（编号为正整数，称为该矿石的元素序号），那么，一个矿石组合会产生“魔法抵消”当且仅当存在一个非空子集，那些矿石的元素序号按位异或起来为零。 并且人们有了测定魔力的有效途径，已经知道了：合成出来的法杖的魔力等于每一种矿石的法力之和。人们已经测定了现今发现的所有矿石的法力值，并且通过实验推算出每一种矿石的元素序号。 现在，给定你以上的矿石信息，请你来计算一下当时可以炼制出的法杖最多有多大的魔力。Input
第一行包含一个正整数N，表示矿石的种类数。
接下来 N行，每行两个正整数Numberi 和 Magici，表示这种矿石的元素序号和魔力值。Output
仅有一行，一个整数：最大的魔力值
Sample Input
3 1 10 2 20 3 30
Sample Output
50
explain: 由于有“魔法抵消”这一事实，每一种矿石最多使用一块。 如果使用全部三种矿石，由于三者的元素序号异或起来：1 xor 2 xor 3 = 0 ， 则会发生魔法抵消，得不到法杖。 可以发现，最佳方案是选择后两种矿石，法力为 20+30=50。
HINT
对于全部的数据：N ≤ 1000，Numberi ≤ 10^18，Magici ≤ 10^4。
Main idea
给出若干元素带两个属性a,b，求出添加若干个元素使得b最大（可加入的条件是加入的任意元素（不限制个数）XOR起来不为0）。
Solution
考虑贪心，从最大到最小加入肯定最优，发现线性基的性质内含“无法表示出0”，所以可以使用线性基处理。（线性基是可以用内部元素XOR出来答案和原来的相当的结构）。
加入方式：判断i的这一位是否为1，如果为1，判断线性基中这一位是否已经有匹配元，如果没有则将i当做这一位的匹配元，停止判断，Ans+=b[i]。
Code
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 const int ONE=1005;10 11 int n;12 int len=64;13 long long Link[65];14 int Ans;15 16 struct power17 {18 long long a;19 int b;20 }a[ONE];21 22 bool cmp(const power &a,const power &b)23 {24 return a.b>b.b;25 }26 27 int get() 28 { 29 int res,Q=1; char c;30 while( (c=getchar())<48 || c>57)31 if(c=='-')Q=-1;32 if(Q) res=c-48; 33 while((c=getchar())>=48 && c<=57) 34 res=res*10+c-48; 35 return res*Q; 36 }37 38 int main()39 { 40 n=get();41 42 for(int i=1;i<=n;i++)43 {44 scanf("%lld",&a[i].a);45 a[i].b=get();46 }47 48 sort(a+1,a+n+1,cmp);49 50 for(int i=1;i<=n;i++)51 {52 for(int pos=len;pos>=1;pos--)53 {54 if( ((a[i].a>>(pos-1))&1) )55 {56 if(!Link[pos])57 {58 Link[pos]=a[i].a;59 Ans+=a[i].b;60 break;61 }62 else a[i].a^=Link[pos];63 }64 }65 }66 67 printf("%d",Ans);68 }