题目描述：
$ 2^N - 1 $ 种物品，每种物品有价格 $ a_i $ ，其中如果 $ j = i \oplus p \oplus q \cdots \oplus z $ （都为下标）那么第 $ j $ 种物品能够用其他的物品合成出来。求得到所有物品，所花费的最小代价是多少。
数据范围：
- $ 2 \le N \le 16 $
- $ 1 \le c_i \le 10^9 $
题解：
很显然，是线性基。
直接贪心，对价格排序。然后从最便宜的开始，插入线性基，如果插入成功，则购买（说明不能合成），插入失败，则跳过（说明可以通过其他的线性表出），得到总价格。
代码：
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
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
vector<PII> a;
ll p[64];
inline bool insert(ll x)
{
for (int i = 63; i >= 0; i--)
{
if (x & (1LL << i))
{
if (!p[i])
{
p[i] = x;
break;
}
x ^= p[i];
}
}
return x != 0;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
n = (1 << n) - 1;
for (int i = 1, x; i <= n; i++)
{
cin >> x;
a.push_back({x, i});
}
sort(a.begin(), a.end());
ll ans = 0;
for (auto x : a)
{
if (insert(x.second))
{
ans += x.first;
}
}
cout << ans << endl;
return 0;
}
|