「ZJOI2009」对称的正方形 - 单调队列+二维Manacher / 二分+Hash | Bill Yang's Blog

「ZJOI2009」对称的正方形 - 单调队列+二维Manacher / 二分+Hash

题目大意

    求一个矩阵中回文正方形的个数。
    回文正方形即指沿着中轴左右对称、上下对称。


题目分析

这道题可以用单调队列+二维Manacher来搞。
然而显然代码量高,调试复杂,我们不妨使用第二种解法。
没错我就是要用非确定性算法!

我们设置一下从左上角开始的Hash函数:

不难发现这个Hash函数是二维的前缀和形式,可以提取出一个子矩阵的Hash值。
再计算一下右上角开始的Hash与左下角开始的Hash,即可比较是否两个方向对称了。

为了不特判偶数情况,我们每隔一行一列插入一个空行,将偶数情况转化为奇数情况。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const int maxn=2005,base1=123,base2=10007;

int n,m,a[maxn][maxn],ans=0;
unsigned int LU[maxn][maxn],RU[maxn][maxn],LD[maxn][maxn],Pow1[maxn],Pow2[maxn];

bool Check(int x1,int y1,int x2,int y2) {
int h1=LU[x2][y2]-LU[x2][y1-1]*Pow2[y2-y1+1]-LU[x1-1][y2]*Pow1[x2-x1+1]+LU[x1-1][y1-1]*Pow2[y2-y1+1]*Pow1[x2-x1+1];
int h2=RU[x2][y1]-RU[x2][y2+1]*Pow2[y2-y1+1]-RU[x1-1][y1]*Pow1[x2-x1+1]+RU[x1-1][y2+1]*Pow2[y2-y1+1]*Pow1[x2-x1+1];
if(h1!=h2)return false;
int h3=LD[x1][y2]-LD[x1][y1-1]*Pow2[y2-y1+1]-LD[x2+1][y2]*Pow1[x2-x1+1]+LD[x2+1][y1-1]*Pow2[y2-y1+1]*Pow1[x2-x1+1];
return h2==h3;
}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
a[(i<<1)-1][(j<<1)-1]=Get_Int();
n=(n<<1)-1,m=(m<<1)-1;
Pow1[0]=Pow2[0]=1;
for(int i=1; i<=n; i++)Pow1[i]=Pow1[i-1]*base1;
for(int i=1; i<=m; i++)Pow2[i]=Pow2[i-1]*base2;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)LU[i][j]=LU[i][j-1]*base2+a[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)LU[i][j]+=LU[i-1][j]*base1;
for(int i=1; i<=n; i++)
for(int j=m; j>=1; j--)RU[i][j]=RU[i][j+1]*base2+a[i][j];
for(int i=1; i<=n; i++)
for(int j=m; j>=1; j--)RU[i][j]+=RU[i-1][j]*base1;
for(int i=n; i>=1; i--)
for(int j=1; j<=m; j++)LD[i][j]=LD[i][j-1]*base2+a[i][j];
for(int i=n; i>=1; i--)
for(int j=1; j<=m; j++)LD[i][j]+=LD[i+1][j]*base1;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(!((i+j)&1)) {
int Left=1,Right=min({i,j,n-i+1,m-j+1});
while(Left<=Right) {
int mid=(Left+Right)>>1;
if(Check(i-mid+1,j-mid+1,i+mid-1,j+mid-1))Left=mid+1;
else Right=mid-1;
}
ans+=(Right+(i&1))>>1;
}
printf("%d\n",ans);
return 0;
}
姥爷们赏瓶冰阔落吧~
0%