UVa 1665 – Islands [并查集+离线处理]

点击打开vjudge题目链接

题意:给定一个N×M的矩阵,每个格子都有一个正整数,再输入T个整数ti,对于每个ti输出大于ti的正整数组成多少个四连块。

UVa的并查集果然不一样,还得判断四连块,刚开始没往并查集那儿想,后来看到说用到某个数据结构才想到的,并查集应该算是ACM中最基本的数据结构吧。

由于查询次数很大,并且是按照升序查询的,但是用并查集算四连块是逆序的,所以要离线查询,就是从大到小处理完后统一输出。注意输出的地方比较坑,感觉题目没有说清楚,每次查询后都有一个空格。

C++代码:

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

struct Node {
    int val, r, c;
};
struct Query {
    int val, i, ans;
};
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const int maxn = 1024;
int n, m, t, mp[maxn][maxn], pa[maxn*maxn];
bool vis[maxn][maxn];
Node v[maxn*maxn];
Query query[100005];

int Find(int x) { return x == pa[x] ? x : pa[x] = Find(pa[x]); }

inline bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
void input() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            scanf("%d", &mp[i][j]);
            v[i*m+j].r = i, v[i*m+j].c = j, v[i*m+j].val = mp[i][j];
        }
    }
    sort(v, v + n * m, [](const Node &a, const Node &b) { return a.val > b.val; });
    scanf("%d", &t);
    for(int i = 0; i < t; ++i) {
        scanf("%d", &query[i].val);
        query[i].i = i;
    }
}
int judge(int x, int y) {
    list<int> pas;
    for(int i = 0; i < 4; ++i) {
        int vx = x+dir[i][0], vy = y+dir[i][1];
        if(in(vx, vy) && vis[vx][vy])
            pas.push_back(Find(vx * m + vy));
    }
    pas.sort();
    pas.erase(unique(pas.begin(), pas.end()), pas.end());
    for(auto i : pas)
        pa[i] = x * m + y;
    return 1 - pas.size();
}
void solve() {
    for(int i = 0; i < maxn*maxn; ++i)
        pa[i] = i;
    int cnt = 0;
    memset(vis, 0, sizeof(vis));
    for(int i = t-1, p = 0; i >= 0; --i) {
        int cur = query[i].val;
        for(; p < n*m && v[p].val > cur; ++p) {
            cnt += judge(v[p].r, v[p].c);
            vis[v[p].r][v[p].c] = true;
        }
        query[i].ans = cnt;
    }
}
void output() {
    for(int i = 0; i < t; ++i)
        printf("%d ", query[i].ans);
    printf("\n");
}
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        input();
        solve();
        output();
    }
    return 0;
}

欢迎留言