BZOJ2460 [BJWC2011]元素(线性基,贪心)

题目链接

洛谷

darkbzoj

题意简述

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

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

简要做法

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

然后…过了?

仔细一想发现也不难证。

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

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

参考代码

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
#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 游戏的经典结论。