BZOJ2460 [BJWC2011]元素（线性基，贪心）

题目链接

洛谷

darkbzoj

题意简述

给你 $n$ 个带权值的数（数和权值是两个东西），求一个权值最大的异或线性无关子集，即取这个子集的任意一个非空子集，异或和都不为零。

原题 $n\le1000$，实际上可以轻松 $n\le10^5$。数 $10^{18}$，权值 $10^4$。

简要做法

看到这题，就随便贪心一下：按权值排序，插入到线性基所在的线性空间的元素集合里（说的这么绕口是因为“插入到线性基里”是一种极不严谨的表述，而且无法和真正的“插入到线性基里”区分开），如果插入到了线性基里，就把答案加上这个数的权值。

然后…过了？

仔细一想发现也不难证。

首先，一堆线性无关的向量中，如果加进来一个线性相关的，一定可以删掉这些向量（包括刚加进来这个）中的某一个（并不是任意一个，但只要一个就可以了），让它们变得线性无关。这个性质在异或中可能不那么显然，但线性相关就相当于方程组中有一个多余的方程（可以由其它方程推出来），这时只要删掉一个方程就不会有多余的方程了，这样就是大家所熟知的了。

因此，考虑加入一个元素时删掉谁呢？当然是权值小的那一个。如果事先排好序，加不进去的时候不加就好了。

参考代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair<int, ll> pil; 

const int N = 1010;

pil a[N];
ll p[70];
int n, ans;

int main()
{
    int i, j;

    scanf("%d", &n);

    for (i = 1; i <= n; ++i) scanf("%lld%d", &a[i].second, &a[i].first);

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

    for (i = n; i >= 1; --i)
    {
        ll x = a[i].second;
        for (j = 59; ~j; --j)
        {
            if ((x >> j) & 1)
            {
                if (p[j]) x ^= p[j];
                else
                {
                    p[j] = x;
                    ans += a[i].first;
                    break;
                }
            }
        }
    }

    cout << ans;

    return 0;
}

三倍经验

[JLOI2015]装备购买 和 [CQOI2013]新Nim游戏 是两道和此题几乎完全一样的题，前者是用一个类似高斯消元的过程代替异或，后者要利用到 Nim 游戏的经典结论。