给一个n行m列的矩阵, 求上下,左右均对称的正方形区域的数目. (n,m≤10^4, 矩阵中的数≤10^9) 不困难, 但那天思维堵塞......
首先, 上下,左右均对称, 也就是每行,每列均是回文串.
开始把它当成了DP, 囧......枚举正方形的中心, 暴力二分答案即可.
二分怎么验证呢? - 二维哈希 一维哈希, 我们把字符串s对应到一个多项式f(x), 把f(x0)作为s的哈希值; 为了O(1)回答一个子串的值, 我们预处理每个后缀的哈希值. 二维哈希, 就把字符串对应到二元多项式f(x,y), 把f(x0,y0)作为哈希值; 为了O(1)回答一个子矩形的值, 我们预处理每个后缀矩形的哈希值 (二维后缀和). 分别从四个角哈希. (unsigned int自然溢出就可以) - Manacher + ST表 这个方法比哈希靠谱多了......Manacher求出每个点在行,列上延伸的最长距离, 区间取min, 再对列,行的答案取min. 卡一卡空间......
时间复杂度均为
存在复杂度相同的其他做法. 上面 二分 + Manacher + ST表 的做法, 我们实际上求的是以每个点为中心, 向上,下,左,右延伸的最大的长:宽=2:1的矩形. 每一行每个点向左延伸的最远位置关于列有单调性, 换做 two-pointer 即可. 其他方向同理. 仍然用ST表求区间最小值. 见 [除草]BZOJ 1414 [ZJOI2009]对称的正方形 - zcwwzdjn - 博客园.
矩形的长和宽之间相互制约. 但如果长宽之比是定值, 就很和谐了.
{% raw %}
const int N = 1002;
typedef unsigned int uint;
const int d[][2] = {{1,1},{1,-1},{-1,-1},{-1,1}};
uint X[N] = {1, 2333}, Y[N] = {1, 23333}, h[4][N][N], s[N][N];
int n, m;
void init()
{
rep (i, 2, max(n, m)+1) X[i] = X[i-1] * X[1], Y[i] = Y[i-1] * Y[1];
rep (k, 0, 4)
for (int i = d[k][0] > 0 ? n : 1; i <= n && i > 0; i -= d[k][0])
for (int j = d[k][1] > 0 ? m : 1; j <= m && j > 0; j -= d[k][1])
{
int a = i+d[k][0], b = j+d[k][1];
h[k][i][j] = s[i][j] + X[1] * h[k][a][j] + Y[1] * h[k][i][b] - X[1] * Y[1] * h[k][a][b];
}
}
inline uint H(int k, int a, int b, int t)
{
int i = a - d[k][0]*t, j = b - d[k][1]*t;
return h[k][i][j] - X[t] * h[k][a][j] - Y[t] * h[k][i][b] + X[t] * Y[t] * h[k][a][b];
}
int binary_search_1(int i, int j)
{
int l = 1, r = min(min(min(i, j), n-i+1), m-j+1) + 1;
while (r-l > 1) // [l, r)
{
int m = (l+r)/2;
uint t = H(0, i+d[0][0], j+d[0][1], m);
bool ok = true;
rep (k, 1, 4) if (t != H(k, i+d[k][0], j+d[k][1], m)) { ok = false; break; }
if (ok) l = m;
else r = m;
}
return l;
}
int binary_search_2(int i, int j)
{
int l = 0, r = min(min(min(i-1, j-1), n+1-i), m+1-j) + 1;
while (r-l > 1) // [l, r)
{
int m = (l+r)/2;
uint t = H(0, i, j, m);
if (t == H(1, i, j-1, m) && t == H(2, i-1, j-1, m) && t == H(3, i-1, j, m)) l = m;
else r = m;
}
return l;
}
int main()
{
scanf("%d%d", &n, &m);
rep (i, 1, n+1) rep (j, 1, m+1) scanf("%u", &s[i][j]);
init();
int ans = 2*(n+m) - 4;
rep (i, 2, n) rep (j, 2, m) ans += binary_search_1(i, j);
rep (i, 2, n+1) rep (j, 2, m+1) ans += binary_search_2(i, j);
printf("%d\n", ans);
return 0;
}
{% endraw %}