题目链接:
洛谷
BZOJ
题意
给定 $n$ 个矿石,每个矿石有编号和魔力值两种属性,选择一些矿石,使得魔力值最大且编号的异或和不为 0。
思路
线性基 贪心
根据矿石的魔力值从大到小排序。
线性基的所有异或和都不为零。因此维护一个线性基,每次插入编号 $i$,如果 $i$ 与之前的线性基都线性无关,也就是能插入,就插入并将魔力值累加到 $ans$。
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
| #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3 + 5; const int maxbit = 63;
struct M { ll number, magic; }m[maxn];
int cmp(M a, M b) { return a.magic > b.magic; }
ll p[maxbit];
bool judge(ll x) { for(int i = maxbit - 1; i >= 0; --i) { if((x >> i) & 1) { if(p[i] == 0) { p[i] = x; break; } x ^= p[i]; } } if(x) { return true; } else { return false; } }
int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for(int i = 0; i < n; ++i) { cin >> m[i].number >> m[i].magic; } sort(m, m + n, cmp); ll ans = 0; for(int i = 0; i < n; ++i) { if(judge(m[i].number)) { ans += m[i].magic; } } cout << ans << endl; return 0; }
|