标题问题链接：LuoguP4398

二维哈希 \(+\) 哈希表

\[\Large\texttt{description}\]

给出一个\(n\)，再给出\(2\)个\(n * n\)的矩阵

求最大的\(k\)满足\(2\)个矩阵中都有\(k * k\)的矩阵不异

数据范畴 \(n \leq 50\)

\[\Large\texttt{Solution}\]

\(\bullet\) 做法\(1:\)

我们枚举一个边长\(k\)， 枚举第一个矩阵的一个坐标\((x, y)\)，再枚举第二个矩阵的一个坐标\((x_1, y_1)\)然后\(O(n ^ 2)\)判断两个矩阵是否不异

时间庞大度:\(O(n ^ 7)\)

也可以二分\(k\)

时间庞大度\(O(\log~n* n ^ 6)\)没啥用

吸氧即可过

\(\bullet\) 做法\(2:\)

我们可以用二维哈希来优化\(2\)个矩阵是否不异的庞大度

先介绍一下二维哈希

二维哈希就是一维哈希的进化版

我们先进行一次哈希把\(n\)行\(m\)列的数组变为\(n\)行\(1\)列的数组

然后再进行一次哈希即可

for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) Hash[i][j] = Hash[i][j - 1] * mul_fir + a[i][j]; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) Hash[i][j] += Hash[i - 1][j] * mul_sec;

然后我们要盘问\((x, y)(x_1, y_1)\)就为

Hash[x_1][y_1] - Hash[x_1][y_1 - 1] * pow_fir[y_1 - y + 1] - Hash[x - 1][y_1] * pow_sec[x_1 - x + 1] + Hash[x - 1][y - 1] * pow_fir[y_1 - y + 1] * pow_sec[x_1 - x + 1]

时间庞大度：\(O(\log~n * n ^ 4)\)

可以过

\(\bullet\) 做法\(3:\)

我们照样考虑二维哈希

我们把第一个矩阵中边长为\(k (k <= n)\)的所有正方形的哈希值与\(k\)都存入哈希表

最后在第二个矩阵中找出边长和值不异的最大矩阵即可

时间庞大度:\(O(n ^ 3)\)

\[\Large\texttt{Code}\]

#include <bits/stdc++.h> #define ull unsigned long long const int MaxN = 50 + 10; const int mul_fir = 9191891; const int mul_sec = 6893911; const int Mod = 999983; using namespace std; inline int read() { int cnt = 0, opt = 1; char ch = getchar(); for (; ! isalnum(ch); ch = getchar()) if (ch == '-') opt = 0; for (; isalnum(ch); ch = getchar()) cnt = cnt * 10 + ch - 48; return opt ? cnt : -cnt; } int n, m, ans; ull AHash[MaxN][MaxN], BHash[MaxN][MaxN]; ull pow_fir[MaxN], pow_sec[MaxN]; int a[MaxN][MaxN], b[MaxN][MaxN]; struct Hash { int nxt; ull to_value; int to_k; } table[MaxN * MaxN * MaxN]; int head[Mod + 10], tot; inline ull calc(int x, int y, int X, int Y, int opt) { return opt == 1 ? AHash[X][Y] - AHash[x - 1][Y] * pow_sec[X - x + 1] - AHash[X][y - 1] * pow_fir[Y - y + 1] + AHash[x - 1][y - 1] * pow_sec[X - x + 1] * pow_fir[Y - y + 1] : BHash[X][Y] - BHash[x - 1][Y] * pow_sec[X - x + 1] - BHash[X][y - 1] * pow_fir[Y - y + 1] + BHash[x - 1][y - 1] * pow_sec[X - x + 1] * pow_fir[Y - y + 1]; } inline void insert(ull v, int k) { int u = v % Mod; table[++tot].nxt = head[u]; head[u] = tot; table[tot].to_value = v; table[tot].to_k = k; } inline int query(ull v, int k) { int u = v % Mod; for (int i = head[u]; i; i = table[i].nxt) if (table[i].to_k == k && table[i].to_value == v) return 1; return 0; } int main() { n = read(); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[i][j] = read(); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) b[i][j] = read(); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) AHash[i][j] = AHash[i][j - 1] * mul_fir + a[i][j]; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) AHash[i][j] += AHash[i - 1][j] * mul_sec; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) BHash[i][j] = BHash[i][j - 1] * mul_fir + b[i][j]; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) BHash[i][j] += BHash[i - 1][j] * mul_sec; pow_fir[0] = 1, pow_sec[0] = 1; for (int i = 1; i <= MaxN - 10; ++ i) pow_fir[i] = pow_fir[i - 1] * mul_fir, pow_sec[i] = pow_sec[i - 1] * mul_sec; for (int k = 1; k <= n; ++ k) for (int i = 1; i <= n - k + 1; ++ i) for (int j = 1; j <= n - k + 1; ++ j) insert(calc(i, j, i + k - 1, j + k - 1, 1), k); for (int k = n; k >= 1; k --) for (int i = 1; i <= n - k + 1; ++ i) for (int j = 1; j <= n - k + 1; ++ j) if (query(calc(i, j, i + k - 1, j + k - 1, 0), k)) { printf("%d\n", k); return 0; } return 0; }

题解 P4398 【[JSOI2008]Blue Mary的战役舆图】

标签：

原文地点：https://www.cnblogs.com/chz-hc/p/12221311.html

，