0%

「UVALive 4487」Exclusive OR

正经写了一个带权并查集的简单题。

这个题的操作一共有两种:第一种是告诉你$X_p \text{xor} X_q = v$,要判断与之前的信息是否矛盾。第二种是让你求一系列$X$的xor和,同时也要判断不知道的情况。

不要问我为什么题目中是三个操作,因为第一个操作就是第二个操作。

首先你需要读入,这个可以用sscanf。然后就可以开始带权并查集搞了。

首先并查集里维护$xor_{u}$,代表$X_u \text{xor} X_{f_u}$的值。这个东西一开始都不知道,所以都设成0.

当进行路径压缩的时候这么写:

1
2
3
4
5
6
int find(int x) {
if (x == f[x]) return x;
int get = find(f[x]);
xor_[x] ^= xor_[f[x]];
return f[x] = get;
}

这个东西成立是因为$(a xor b) xor (b xor c)=a xor c$.

然后如果他告诉你了一条关系,你先找到对应并查集的代表,然后合并一下,注意要特判下恒0的情况。

这里合并要判断他俩在不在一个集合里,可以结合代码理解:

1
2
3
4
5
6
7
8
9
10
11
bool merge(int p, int q, int v) {
int fp = find(p), fq = find(q);
if (fp == fq) {
if ((xor_[p] ^ xor_[q]) != v) return 0;
return 1;
}
if (fp == n) swap(fp, fq);
f[fp] = fq;
xor_[fp] = (xor_[p] ^ xor_[q] ^ v);
return 1;
}

求那个东西也挺有意思的。

考虑把在一个森林里的所有东西一块计算。

注意到我们能搞出来的xor和=x1 xor xf xor x2 xor xf xor…xor xp xor xf

如果我们消不掉xf,除非xf=0,否则一定无解。

否则直接消即可。不知道为啥uva一直过不了,但是hdu就能过…

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>

#define test(...) fprintf(stderr, __VA_ARGS__)
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef unsigned int ui;
typedef vector <pair <int, int> > edges;

const int N = 1000005;
char s[N], from[N];
int f[N], xor_[N], n, q;
// xor_[x]: x -> fa[x]这条边的xor值
// 路径压缩的时候顺带维护
int find(int x) {
if (x == f[x]) return x;
int get = find(f[x]);
xor_[x] ^= xor_[f[x]];
return f[x] = get;
}
int case_num;
bool merge(int p, int q, int v) {
int fp = find(p), fq = find(q);
if (fp == fq) {
if ((xor_[p] ^ xor_[q]) != v) return 0;
return 1;
}
if (fp == n) swap(fp, fq);
f[fp] = fq;
xor_[fp] = (xor_[p] ^ xor_[q] ^ v);
return 1;
}

int ans(vi now) {
int k = now.size(), ans = 0;
vi ind(k);
for (int i = 0; i < k; ++i) {
if (ind[i]) continue;

int fi = find(now[i]), cnt = 0;
for (int j = i; j < k; ++j) {
int fj = find(now[j]);
if (!ind[j] && fi == fj) {
cnt++;
ind[j] = 1;
ans ^= xor_[now[j]];
}
}
if ((cnt & 1) && fi != n) return -1;
}
return ans;
}
void solve() {
printf("Case %d:\n", ++case_num);
for (int i = 0; i <= 1000000; ++i)
f[i] = i, xor_[i] = 0;
bool flag = 0;
int facts = 0;
while (q--) {
char op[3];
scanf("%s", op);
if (op[0] == 'I') {
gets(from);
int space = 0, p, q, v;
for (int i = 1; from[i] != '\0'; ++i)
if (from[i] == ' ') ++space;
// dbg(space);
if (space == 1) {
sscanf(from, "%d%d", &p, &v);
q = n;
} else if (space == 2)
sscanf(from, "%d%d%d", &p, &q, &v);
++facts;
if (flag) continue;
if (!merge(p, q, v)) {
printf("The first %d facts are conflicting.\n", facts);
flag = 1;
}
} else if (op[0] == 'Q') {
int k;
scanf ("%d", &k);
vi q(k);
for (int i = 0; i < k; ++i) scanf ("%d", &q[i]);

if (flag) continue;
int result = ans(q);
if (result == -1) {
puts("I don't know.");
}
else printf("%d\n", result);
}
}
puts("");
}

int main() {
#ifdef LOCAL
freopen("sample.in", "r", stdin);
#endif
while (~scanf("%d%d", &n, &q) && (n || q)) solve();
return 0;
}