本文共 1851 字，大约阅读时间需要 6 分钟。

子正方形

题目链接：

题目大意

有两个正方形矩阵，问你这两个矩形的最大公共子正方形矩阵的边长。

思路

这道题矩阵大小才 $50$ 一下，我们可以直接用 hash 暴搜。

先枚举两个矩阵所选的矩阵的右下角，然后再二分枚举矩阵大小。
然后取最大值即可。

代码

#include<cstdio>#include<iostream>#define mi1 97ull#define mi2 103ull#define ull unsigned long longusing namespace std;int n, a[51][51], b[51][51], l, r, mid, ans, answer;ull a_hash[51][51], b_hash[51][51], t1[51], t2[51];bool compair(int sx, int sy, int tx, int ty, int mid) {   //看两个矩阵是不是	return (a_hash[sx][sy] - a_hash[sx][sy - mid] * t1[mid] - a_hash[sx - mid][sy] * t2[mid] + a_hash[sx - mid][sy - mid] * t1[mid] * t2[mid])			==			(b_hash[tx][ty] - b_hash[tx][ty - mid] * t1[mid] - b_hash[tx - mid][ty] * t2[mid] + b_hash[tx - mid][ty - mid] * t1[mid] * t2[mid])			;}int main() {   	scanf("%d", &n);		for (int i = 1; i <= n; i++)		for (int j = 1; j <= n; j++)			scanf("%d", &a[i][j]);	for (int i = 1; i <= n; i++)		for (int j = 1; j <= n; j++)			scanf("%d", &b[i][j]);		t1[0] = t2[0] = 1ull;	for (int i = 1; i <= n; i++) t1[i] = t1[i - 1] * mi1;	for (int i = 1; i <= n; i++) t2[i] = t2[i - 1] * mi2;	for (int i = 1; i <= n; i++)		for (int j = 1; j <= n; j++) {   			a_hash[i][j] = a_hash[i][j - 1] * mi1 + a[i][j];			b_hash[i][j] = b_hash[i][j - 1] * mi1 + b[i][j];		}	for (int i = 1; i <= n; i++)//得出两个矩阵的hash值		for (int j = 1; j <= n; j++) {   			a_hash[i][j] += a_hash[i - 1][j] * mi2;			b_hash[i][j] += b_hash[i - 1][j] * mi2;		}		for (int sx = 1; sx <= n; sx++)//枚举第一个矩阵右下角选哪里		for (int sy = 1; sy <= n; sy++)			for (int tx = 1; tx <= n; tx++)//枚举第二个矩阵右下角选哪里				for (int ty = 1; ty <= n; ty++) {   					l = 0;					r = min(min(sx, sy), min(tx, ty));					ans = 0;					while (l <= r) {   //二分出最大的大小						mid = (l + r) >> 1;						if (compair(sx, sy, tx, ty, mid)) {   							ans = mid;							l = mid + 1;						}						else r = mid - 1;					}					answer = max(answer, ans);				} 		printf("%d", answer);		return 0;}