首页 > 代码库 > 两点之间 这题有毒啊,不会做

两点之间 这题有毒啊,不会做

https://biancheng.love/problem/640/index

一直re

不是并查集吗

技术分享
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e6 + 20;
const LL MOD = 10007;
int n, m, q;
string str[maxn];
int fa[maxn];
int Size[maxn];
int first[MOD + 20];
int num;
void init(int tot) {
    for (int i = 0; i <= MOD; ++i) {
        fa[i] = i;
        Size[i] = 1;
    }
    memset(first, 0, sizeof first);
    num = 0;
}
struct node {
    LL val;
    int id;
    int u;
    int tonext;
} e[maxn * 2];
void add(int x, int y) {
    ++num;
    e[num].val = 1LL * x * 1000000 + y;
    assert(e[num].val >= 0);
    e[num].id = num;
    e[num].u = e[num].val % MOD;
    e[num].tonext = first[e[num].u];
    first[e[num].u] = num;
}
int tohash(int x, int y) {
    LL val = 1LL * x * 1000000 + y;
    int u = val % MOD;
    for (int i = first[u]; i; i = e[i].tonext) {
        if (e[i].val == val) return e[i].id;
    }
    while(1);
//    assert(false);
}
int tofind(int x) {
    if (fa[x] == x) return x;
    else return fa[x] = tofind(fa[x]);
}
void tomerge(int x, int y) {
    x = tofind(x);
    y = tofind(y);
    if (x != y) {
        fa[y] = x;
        Size[x] += Size[y];
    }
}
int tonext[4][2] = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}};
struct data {
    int val, fa;
} gg[12];
void work() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", str[i].c_str() + 1);
    }
    init(n * m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            add(i, j);
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (i - 1 >= 1 && str[i - 1][j] == str[i][j]) {
                int x = tofind(tohash(i, j));
                int y = tofind(tohash(i - 1, j));
                tomerge(x, y);
            }
            if (j - 1 >= 1 && str[i][j - 1] == str[i][j]) {
                int x = tofind(tohash(i, j - 1));
                int y = tofind(tohash(i, j));
                tomerge(x, y);
            }
        }
    }
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        memset(gg, 0, sizeof gg);
        int ans = Size[tofind(tohash(x, y))];
        for (int i = 0; i < 4; ++i) {
            int tx = x + tonext[i][0];
            int ty = y + tonext[i][1];
            if (tx >= 1 && tx <= n && ty >= 1 && ty <= m) {
                int father = tofind(tohash(tx, ty));
                if (gg[str[tx][ty] - 0].fa == father) continue;
                gg[str[tx][ty] - 0].val += Size[father];
                gg[str[tx][ty] - 0].fa = father;
            }
        }
        int id = str[x][y];
        for (int i = 0; i < 4; ++i) {
            int tx = x + tonext[i][0];
            int ty = y + tonext[i][1];
            if (tx >= 1 && tx <= n && ty >= 1 && ty <= m) {
//                int father = tofind(tohash(tx, ty));
                if (ans < gg[str[tx][ty] - 0].val) {
                    ans = gg[str[tx][ty] - 0].val;
                    id = str[tx][ty];
                } else if (ans == gg[str[tx][ty] - 0].val) {
                    if (id == str[x][y]) {
                        id = str[tx][ty];
                    }
                }
            }
        }
        printf("%d\n", ans + (id != str[x][y]));
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    int t;
    scanf("%d", &t);
    while (t--) work();
    return 0;
}
View Code

 

两点之间 这题有毒啊,不会做