0%

[PA2014] Kuglarz

题目

题目链接

题目大意:有 $n$ 个杯子,每次可以选一个区间 $l, r$ 并知道 $l, r$ 之间球的总数的奇偶性,求猜出哪些杯子下藏着球需要的最小花费。$1 \le n \le 2 \times 10^3$。

思路

每个杯子下只可能有或没有球,每个区间的球的总数模 $2$ 只可能为 $1$ 或 $0$。

每一个区间 $l, r$ 的奇偶性相当于 $a_l \operatorname{xor} a_{l + 1} … \operatorname{xor} a_{r - 1} \operatorname{xor} a_r$。考虑前缀和,设 $a$ 的异或前缀和数组为 $b$,则 $l, r$ 的奇偶性就为 $b_{l-1} \operatorname{xor} b_{r}$。

考虑如何求出 $a$。显然,求出 $b$ 之后就可以一一求出 $a$。

题目中相当于给出了每组 $i, j$ 之间的代价。但此时由于是前缀和数组,连边的结点不再是 $i, j$,而是 $i - 1, j$。之后不难发现求出 $b$ 需要整个图连通,对建出的图求 MST 即可。

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return;
}

struct Edge {
int u, v, dis;
friend bool operator < (const Edge &a, const Edge &b) {
return a.dis < b.dis;
}
} edge[4000010];

long long ans;
int find[2010];
int n, m;

int unionFind(int x) {
return find[x] == x ? x : find[x] = unionFind(find[x]);
}

int main() {
read(n);
for (int i = 1; i <= n; ++i) {
find[i] = i;
for (int j = i; j <= n; ++j) {
int c;
read(c);
edge[++m].u = i - 1;
edge[m].v = j;
edge[m].dis = c;
}
}
std::sort(edge + 1, edge + m + 1);
for (int i = 1; i <= m; ++i) {
int u = unionFind(edge[i].u), v = unionFind(edge[i].v);
if (u != v) {
find[u] = v;
ans += edge[i].dis;
}
}
printf("%lld\n", ans);
return 0;
}