题目大意
找到所有的上下左右都相同的正方形。
思路：二分+二维Hash
这道题我们首先想到不能暴力判断一个正方形是否合法。
然后我们发现当一个正方形合法时，以这个正方形为中心且比它小的正方形也合法。
所以我们可以枚举每个正方形的中心点，二分求出以这个点为中心点的最大合法正方形的边长L，其贡献是 $\frac{L+1}{2}$
我们再回过来讨论如何判断一个正方形是否合法。
如果这个正方形的原来的、上下翻转的和左右翻转的矩阵都一样，那么这个正方形就是合法的。
以这个思路为出发点，我们可以用二维Hash预处理出这个正方形原来的、上下翻转的、左右反转的矩阵，每次判断的时候只要判断这三个矩阵是否相同就可以了。
在枚举中心点的时候要分类讨论奇偶情况，具体见代码。
二维Hash的求法：
先处理行，在处理列，查询和二维前缀和基本相似，但要注意二维Hash的加减有所不同。
部分代码：
void init() {
//一行的哈希值
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
a[i][j] = a[i][j - 1] * B1 + _a[i][j];
//一列的哈希值
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
a[i][j] += a[i - 1][j] * B2;
}
//查询
unsigned long long query(int x, int y, int X, int Y) {
unsigned long long res = a[x][y] - a[X][Y - 1] * pow1[y - Y + 1] - a[X - 1][Y] * pow2[x - X + 1] + a[X - 1][Y - 1] * pow1[y - Y + 1] * pow2[x - X + 1];
return res;
}
代码
#include <cstdio>
#include <iostream> #define RI register int
#define mid (l + r >> 1) using namespace std; template <class T>
inline void read(T &x) {
x = 0; T f = 1; char c = getchar();
while(c > '9' || c < '0') {
if(c == '-')
f = -f;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
x *= f;
} typedef unsigned long long ull;
const int N = 1e3 + 1;
const int B1 = 233;
const int B2 = 332;
int n, m, ans;
ull a[N][N], b[N][N], c[N][N];
ull pow1[N], pow2[N]; inline void Read() {
read(n), read(m);
for(RI i = 1; i <= n; i++)
for(RI j = 1; j <= m; j++)
read(a[i][j]),
b[i][m - j + 1] = a[i][j],//左右翻转
c[n - i + 1][j] = a[i][j];//上下翻转
}
//二维哈希预处理
inline void init() {
for(RI i = 1; i <= n; i++)
for(RI j = 1; j <= m; j++)
a[i][j] += a[i][j - 1] * B1,
b[i][j] += b[i][j - 1] * B1,
c[i][j] += c[i][j - 1] * B1;
for(RI i = 1; i <= n; i++)
for(RI j = 1; j <= m; j++)
a[i][j] += a[i - 1][j] * B2,
b[i][j] += b[i - 1][j] * B2,
c[i][j] += c[i - 1][j] * B2;
pow1[0] = pow2[0] = 1;
for(RI i = 1, tmp = max(n, m); i <= tmp; i++)
pow1[i] = pow1[i - 1] * B1,
pow2[i] = pow2[i - 1] * B2;
}
//判断三个矩阵是否相同
inline bool check(int x, int y, int le) {
//因为会自然溢出的缘故，unsigned 没有小于0的时候 所以不能写x-le<0 （细节
if(x > n || y > m || x < le || y < le)
return false;
ull res1 = a[x][y] - a[x][y - le] * pow1[le] - a[x - le][y] * pow2[le] + a[x - le][y - le] * pow1[le] * pow2[le];
int tmp = y;
y = m - (y - le);//位置要调整（细节
ull res2 = b[x][y] - b[x][y - le] * pow1[le] - b[x - le][y] * pow2[le] + b[x - le][y - le] * pow1[le] * pow2[le];
y = tmp, x = n - (x - le);//位置要调整（细节
ull res3 = c[x][y] - c[x][y - le] * pow1[le] - c[x - le][y] * pow2[le] + c[x - le][y - le] * pow1[le] * pow2[le];
return res1 == res2 && res2 == res3;
}
inline void solve() {
int tmp = min(n, m);
//这里要分两点讨论，边长为偶数的是枚举格点，而边长为奇数的则是枚举格子（细节
for(RI i = 0; i < n; i++)
for(RI j = 0; j < m; j++) {
int l = 1, r = tmp, res = 0;
while(l < r) {
if(check(i + mid, j + mid, mid + mid))
res = mid, l = mid + 1;
else
r = mid;
}
ans += res;
}
for(RI i = 0; i < n; i++)
for(RI j = 0; j < m; j++) {
int l = 1, r = tmp, res = 0;
while(l < r) {
if(check(i + mid, j + mid, mid + mid + 1))
res = mid, l = mid + 1;
else
r = mid;
}
ans += res;
}
ans += n * m; //1格的也算对称正方形，不要漏了（细节
printf("%d\n", ans);
} int main() {
Read();
init();
solve();
return 0;
}