嘟嘟嘟
当看到n <= 50 的时候就乐呵了，暴力就行了，不过最暴力的方法是O(n7)……然后加一个二分边长达到O(n6logn)，然后我们接着优化，把暴力比对改成O(1)的比对hash值，能达到O(n5logn),到勉强能过……不过我们还可以在优化一下，把第一个矩阵中所有边长为 l 的子矩阵的hash值都存到一个数组中，然后sort一下，接着我们在枚举第二个矩阵的子矩阵，然后在数组中用lower_bound的查询就行。这样的话复杂度应该是O(n3log(n2) * logn)了。
~~求一个矩阵的哈希值就是每一行的哈希值之和~~
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack>10 #include<queue>11 using namespace std;12 #define enter puts("") 13 #define space putchar(‘ ‘)14 #define Mem(a) memset(a, 0, sizeof(a))15 typedef long long ll;16 typedef unsigned long long ull;17 typedef double db;18 const int INF = 0x3f3f3f3f;19 const int eps = 1e-8;20 const int maxn = 55;21 const ull base = 19260817; ???//请无视 22 inline ll read()23 {24 ????ll ans = 0;25 ????char ch = getchar(), last = ‘ ‘;26 ????while(!isdigit(ch)) {last = ch; ch = getchar();}27 ????while(isdigit(ch)) {ans = ans * 10 + ch - ‘0‘; ch = getchar();}28 ????if(last == ‘-‘) ans = -ans;29 ????return ans;30 }31 inline void write(ll x)32 {33 ????if(x < 0) x = -x, putchar(‘-‘);34 ????if(x >= 10) write(x / 10);35 ????putchar(x % 10 + ‘0‘);36 }37 38 int n, a[2][maxn][maxn];39 ull has[2][maxn][maxn];40 ull f[maxn], b[maxn * maxn];41 int cnt = 0;42 43 44 ull calc(int x, int y, int l, bool flag)45 {46 ????ull ret = 0;47 ????for(int i = x; i <= x + l - 1; ++i) ret += has[flag][i][y + l - 1] - has[flag][i][y - 1] * f[l];48 ????return ret;49 }50 bool judge(int x)51 {52 ????cnt = 0;53 ????for(int i = 1; i <= n - x + 1; ++i)54 ????????for(int j = 1; j <= n - x + 1; ++j)55 ????????????b[++cnt] = calc(i, j, x, 0);56 ????sort(b + 1, b + cnt + 1);57 ????for(int i = 1; i <= n - x + 1; ++i)58 ????????for(int j = 1; j <= n - x + 1; ++j)59 ????????{60 ????????????ull ha = calc(i, j, x, 1);61 ????????????if(*lower_bound(b + 1, b +cnt + 1, ha) == ha) return 1;62 ????????}63 ????return 0;64 }65 66 int main()67 {68 ????n = read();69 ????for(int k = 0; k <= 1; k++)70 ????????for(int i = 1; i <= n; ++i)71 ????????????for(int j = 1; j <= n; ++j) a[k][i][j] = read();72 ????f[0] = 1;73 ????for(int i = 1; i <= n; ++i) f[i] = f[i - 1] * base;74 ????for(int k = 0; k <= 1; ++k)75 ????????for(int i = 1; i <= n; ++i)76 ????????????for(int j = 1; j <= n; ++j) has[k][i][j] = has[k][i][j - 1] * base + a[k][i][j];77 ????int L = 1, R = n;78 ????while(L + 1 < R)79 ????{80 ????????int mid = (L + R) >> 1;81 ????????if(judge(mid)) L = mid;82 ????????else R = mid - 1;83 ????}84 ????write(judge(L + 1) ? L + 1 : L); enter; ???????85 ????return 0;86 }[JSOI2008]Blue Mary的战役地图
原文地址：https://www.cnblogs.com/mrclr/p/9549230.html