元素

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;

const int ONE=1005;

int n;
int len=64;
long long Link[65];
int Ans;

struct power
{
    long long a;
    int b;
}a[ONE];

bool cmp(const power &a,const power &b)
{
    return a.b>b.b;
}

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int main()
{
    n=get();

    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].a);
        a[i].b=get();
    }

    sort(a+1,a+n+1,cmp);

    for(int i=1;i<=n;i++)
    {
        for(int pos=len;pos>=1;pos--)
        {
            if( ((a[i].a>>(pos-1))&1) )
            {
                if(!Link[pos])
                {
                    Link[pos]=a[i].a;
                    Ans+=a[i].b;
                    break;
                }
                else a[i].a^=Link[pos];
            }
        }
    }

    printf("%d",Ans);
}