首页 > 代码库 > 两点之间 这题有毒啊,不会做
两点之间 这题有毒啊,不会做
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; }
两点之间 这题有毒啊,不会做
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。