[Codeforces 325 D. Reclamation]并查集[Codeforces 325 D. Reclamation]并查集

95 阅读 0 评论 63 点赞

我是靠谱客的博主淡定芹菜，这篇文章主要介绍[Codeforces 325 D. Reclamation]并查集[Codeforces 325 D. Reclamation]并查集，现在分享给大家，希望可以做个参考。

[Codeforces 325 D. Reclamation]并查集

1. 题目链接：

[Codeforces 325 D. Reclamation]并查集

2. 题意描述：

有一个 r×c 的圆柱形方格表，左边和右边是相连的，现在有 n 次操作，每次会尝试在一个位置放上障碍物，如果放上障碍物之后上边和下边不连通，那么这个障碍物就不能放下去，求出最后有多少个障碍物。
haha

3. 解题思路：

考虑将整张表复制一份接在右边，得到一个r×2c的表，并且左右两侧是相连的。同时对两张表操作（如果在 (x,y) 处加入障碍，那么也在 (x,y+c) 处加入障碍。
每加入一个障碍，检查八连通方向是否有其他的障碍，如果有那么在两个障碍之间连一条边。
这里加边是通过并查集的合并，如果加入障碍之后不联通了，那么撤销之前并查集的操作。
最后检查 (x,y) 和 (x,y+c) 是否连通，如果连通，那么从 (x,y) 往右能走到 (x,y+c) ， (x,y+c) 往右能走到 (x,y+2∗c) = (x,y) ，这说明障碍物在侧面绕了一个圈。
直接copy qls 的题解，hah.

4. 实现代码：

复制代码

#include <bits/stdc++.h>
using namespace std;
typedef __int64 LL;
typedef pair<int, int> PII;
const int MAXN = 3e5 + 5;
const int MX = 3e3 + 5;
int r, c, n;
int fa[MX * MX * 2];
bool G[MX][MX * 2];
stack<PII> stk;
inline int id(int x, int y) { return (x - 1) * c * 2 + y; }
void I() {
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= 2 * c; j++) {
int k = id(i, j);
fa[k] = k;
G[i][j] = false;
}
}
}
int F(int x) {
if (x == fa[x]) return x;
stk.push(PII(x, fa[x]));
return fa[x] = F(fa[x]);
}
void U(int a, int b) {
a = F(a), b = F(b);
if (a == b) return;
stk.push(PII(a, fa[a]));
stk.push(PII(b, fa[b]));
fa[b] = a;
}
int DIR[][2] = {{ -1, -1}, { -1, 0}, { -1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
bool check(int x, int y) {
while (!stk.empty()) stk.pop();
int p[2][2] = {{x, y}, {x, y + c}};
for (int z = 0; z < 2; z++) {
for (int i = 0; i < 8; i++) {
int xx = p[z][0] + DIR[i][0];
int yy = p[z][1] + DIR[i][1];
if (xx < 1 || xx > r) continue;
if (yy < 1) yy = 2 * c;
else if (yy > 2 * c) yy = 1;
if (G[xx][yy] == false) continue;
U(id(p[z][0], p[z][1]), id(xx, yy));
}
}
if (F(id(p[0][0], p[0][1])) == F(id(p[1][0], p[1][1]))) {
while (!stk.empty()) {
PII tp = stk.top(); stk.pop();
fa[tp.first] = tp.second;
}
return false;
}
G[x][y] = G[x][y + c] = true;
return true;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
int x, y, ans = 0;
scanf("%d %d %d", &r, &c, &n); I();
while (n --) {
scanf("%d %d", &x, &y);
if (check(x, y)) ans ++;
}
if (c <= 1) ans = 0;
printf("%dn", ans);
return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
typedef __int64 LL;
typedef pair<int, int> PII;
const int MAXN = 3e5 + 5;
const int MX = 3e3 + 5;
int r, c, n;
int fa[MX * MX * 2];
bool G[MX][MX * 2];
stack<PII> stk;
inline int id(int x, int y) { return (x - 1) * c * 2 + y; }
void I() {
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= 2 * c; j++) {
int k = id(i, j);
fa[k] = k;
G[i][j] = false;
}
}
}
int F(int x) {
if (x == fa[x]) return x;
stk.push(PII(x, fa[x]));
return fa[x] = F(fa[x]);
}
void U(int a, int b) {
a = F(a), b = F(b);
if (a == b) return;
stk.push(PII(a, fa[a]));
stk.push(PII(b, fa[b]));
fa[b] = a;
}
int DIR[][2] = {{ -1, -1}, { -1, 0}, { -1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
bool check(int x, int y) {
while (!stk.empty()) stk.pop();
int p[2][2] = {{x, y}, {x, y + c}};
for (int z = 0; z < 2; z++) {
for (int i = 0; i < 8; i++) {
int xx = p[z][0] + DIR[i][0];
int yy = p[z][1] + DIR[i][1];
if (xx < 1 || xx > r) continue;
if (yy < 1) yy = 2 * c;
else if (yy > 2 * c) yy = 1;
if (G[xx][yy] == false) continue;
U(id(p[z][0], p[z][1]), id(xx, yy));
}
}
if (F(id(p[0][0], p[0][1])) == F(id(p[1][0], p[1][1]))) {
while (!stk.empty()) {
PII tp = stk.top(); stk.pop();
fa[tp.first] = tp.second;
}
return false;
}
G[x][y] = G[x][y + c] = true;
return true;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
int x, y, ans = 0;
scanf("%d %d %d", &r, &c, &n); I();
while (n --) {
scanf("%d %d", &x, &y);
if (check(x, y)) ans ++;
}
if (c <= 1) ans = 0;
printf("%dn", ans);
return 0;
}