题解 CF325D 【Reclamation】

· · 题解

题意

就是说，给了一个空心的圆柱，把上面的方格往下抠。但是不能把圆柱抠断了，求能够成功抠掉的方格数。

做法

由于这里是个圆柱，首尾相接的，所以我们需要断环为链（复制一份）

其次，可以发现，如果出现了“抠断”的情况，说明出现了一个环，也就是说从(i,j)这个点和(i,j + c)这个点之间打通了。

要维护这样的连通性，我们可以用并查集。

详细过程

1 判断一个点可不可以删除

我们现在知道要判断的目标点(x,y)和断环为链后的对应点(x,y+c)。

现在我们需要检查这两个点八连通且已删除的相邻点中有没有在同一集合中的。如果存在，那么说明如果抠掉这个点，圆柱就断了。

2 删除一个点

同样，我们只需要将(x,y)、(x,y+c)与他们八连通且已删除的相连点合并到同一集合即可。

3 注意的细节

这样就可以过了

代码

#include<bits/stdc++.h>
using namespace std;

inline int get() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int N = 2e7 + 5;
int r, c, n, f[N], ans = 0;
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; //八个方向
bool delt[3005][6005];

inline int id(int x, int y) { //降维打击
    return (x - 1) * c * 2 + y;
}

inline bool ok(int &x, int &y) { //判断越界和已删除
    if(y == 0) y = c * 2;
    else if(y == c * 2 + 1) y = 1;
    return (x > 0 && x <= r && delt[x][y]);
}

inline int find(int x) { //并查集路劲压缩
    return x == f[x]? x : f[x] = find(f[x]);
}

inline bool chk(int x, int y) { //检查能否删除这个点
    int x1 = x, y1 = y + c;
    for(register int i = 0; i < 8; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if(!ok(nx, ny)) continue;
        for(register int j = 0; j < 8; j++) {
            int nx1 = x1 + dx[j], ny1 = y1 + dy[j];
            if(!ok(nx1, ny1)) continue;
            if(find(id(nx, ny)) == find(id(nx1, ny1))) { return 0; }
        }
    }
    return 1;
}

inline void merge(int a, int b) { //并查集的合并操作
    int x = find(a), y = find(b);
    f[x] = y;
}

inline void del(int x, int y) { //删除某个点
    int x1 = x, y1 = y + c;
    for(register int i = 0; i < 8; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if(ok(nx, ny)) merge(id(x, y), id(nx, ny));
        int nx1 = x1 + dx[i], ny1 = y1 + dy[i];
        if(ok(nx1, ny1)) merge(id(x1, y1), id(nx1, ny1));
    }
    delt[x][y] = 1;
    delt[x1][y1] = 1;
}

int main() {
    r = get(), c = get(), n = get();
    if(c == 1) { // 特判
        printf("0");
        return 0;
    }
    for(register int i = 1; i <= r; i++)
        for(register int j = 1; j <= c * 2; j++)
            f[id(i, j)] = id(i, j);
    while(n--) {
        int x = get(), y = get();
        if(chk(x, y)) del(x, y), ans++;
    }
    printf("%d\n", ans);
    return 0;
}

如有问题 & Bug，欢迎在评论区反馈