题目地址：洛谷：【P4570】[BJWC2011]元素 – 洛谷、BZOJ：Problem 2460. — [BeiJing2011]元素

题目描述

相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。
一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消” 。特别地，如果在炼制过程中使用超过一块同一种矿石，那么一定会发生“魔法抵消”。后来，随着人们认知水平的提高，这个现象得到了很好的解释。经过了大量的实验后，著名法师 Dmitri 发现：如果给现在发现的每一种矿石进行合理的编号（编号为正整数，称为该矿石的元素序号），那么，一个矿石组合会产生“魔法抵消”当且仅当存在一个非空子集，那些矿石的元素序号按位异或起来为零。（如果你不清楚什么是异或，请参见下一页的名词解释。 ）
例如，使用两个同样的矿石必将发生“魔法抵消”，因为这两种矿石的元素序号相同，异或起来为零。并且人们有了测定魔力的有效途径，已经知道了：合成出来的法杖的魔力等于每一种矿石的法力之和。人们已经测定了现今发现的所有矿石的法力值，并且通过实验推算出每一种矿石的元素序号。
现在，给定你以上的矿石信息，请你来计算一下当时可以炼制出的法杖最多有多大的魔力。

输入输出格式

输入格式：
第一行包含一个正整数N，表示矿石的种类数。
接下来 N 行，每行两个正整数 Numberi 和 Magici ，表示这种矿石的元素序号和魔力值。

输出格式：
仅包含一行，一个整数代表最大的魔力值。

输入输出样例

输入样例#1：

3 
1 10 
2 20 
3 30

输出样例#1：

50

说明

样例解释
由于有“魔法抵消”这一事实，每一种矿石最多使用一块。
如果使用全部三种矿石，由于三者的元素序号异或起来：1 xor 2 xor 3=0 ，则会发生魔法抵消，得不到法杖。
可以发现，最佳方案是选择后两种矿石，法力为 20+30=50 。
数据范围
对于全部的数据： N≤1000，Numberi≤10^18，Magici≤10^4。

题解

本题是一个线性基的应用裸题。我们考虑将所有矿石的魔力值按从大到小的顺序排序，类似Kruskal的思想，贪心地从大到小计算是否可以作为元素序号的线性基，如果可以，则将其魔力值加入答案中。
这个算法的复杂度是$O(n \log n)$的。注意需要处处使用long long。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 1005;

int n, mat[65];

struct Data {
    LL num, mag;
    inline bool operator<(const Data &rhs) const {
        return mag > rhs.mag;
    }
} a[MAXN];

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        a[i].num = readint(); a[i].mag = readint();
    }
    std::sort(a + 1, a + n + 1);
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 63; j >= 0; j--) {
            if(a[i].num & (1ll << j)) {
                if(!mat[j]) {
                    mat[j] = i; break;
                } else {
                    a[i].num ^= a[mat[j]].num;
                }
            }
        }
        if(a[i].num) ans += a[i].mag;
    }
    printf("%lld", ans);
    return 0;
}