P2601 [ZJOI2009]对称的正方形 题解
conprour
2021-09-15 22:10:28
# 分析
根据对称的定义，显然满足单调性。再看看范围，容易想到二分答案。
如何判断一个正方形是对称正方形？可以用二维 Hash 解决。
以下分为二分和二维 Hash 两个部分展开。
## 二分部分
首先确定，二分成立需要单调性，所以一定是从中心点二分，但是当正方形为奇数的时候中心点在中央的格子，那么偶数呢？
实际上，边长为偶数的时候正方形的重心在一个格点（就是一个点，不是格子）。
概括一下：
* 对于长度为奇数的正方形，以格子（一个 $1 \times 1$ 的正方形）为中心二分最远符合条件的长度。
* 对于长度为偶数的正方形，以格点（就是一个点）为中心二分最远符合条件的长度
那么二分的 ``check`` 函数就可以用二维 Hash 来 $O(1)$ 判断。
## 二维 Hash 部分
简单讲解一下板子需要注意的地方。
二维 Hash 的作用就是判断矩阵是否相同。
具体实现上就是横向和纵向分别算两次 Hash 值（$base1$ , $base2$ 取不同的值，模数 $mod$ 取一个值)。
对于 Hash 值的查询，类似二维前缀和，下面贴的代码中 $mi1$ , $base1$ 对应纵坐标 $y$ ， $mi2$ , $base2$ 对应横坐标 $x$，记住这个对应关系基本就不会写错。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const int INF = 0x3f3f3f3f,N = 1e3+10,base1 = 233,base2 = 133;
const ll mod = 1e9+9;
ull mi1[N<<1],mi2[N<<1],sum[N<<1][N<<1];
int len,a[N<<1][N<<1],n,m;
int ans;
void init()
{
mi1[0]=mi2[0]=1;
//这里所有的n,m不要忘记×2
for(int i=1;i<=m<<1;i++) mi1[i]=(mi1[i-1]*base1);
for(int i=1;i<=n<<1;i++) mi2[i]=(mi2[i-1]*base2);
for(int i=1;i<=n<<1;i++)
for(int j=1;j<=m<<1;j++)
sum[i][j]=sum[i][j-1]*base1+a[i][j];
for(int i=1;i<=n<<1;i++)
for(int j=1;j<=m<<1;j++)
sum[i][j]+=sum[i-1][j]*base2;//注意这里是+=
}
inline ll Hash(int xa,int ya,int xb,int yb)
{
return sum[xb][yb]-sum[xa-1][yb]*mi2[xb-xa+1]-
sum[xb][ya-1]*mi1[yb-ya+1]+
sum[xa-1][ya-1]*mi1[yb-ya+1]*mi2[xb-xa+1];
}
inline bool check(int xa,int ya,int xb,int yb)
{
return Hash(xa,ya,xb,yb)==Hash((n<<1)-xb+1,ya,(n<<1)-xa+1,yb)&&
Hash(xa,ya,xb,yb)==Hash(xa,(m<<1)-yb+1,xb,(m<<1)-ya+1);//+1要想好
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
a[i+n][j]=a[n-i+1][j];
a[i][j+m]=a[i][m-j+1];
}
init();//忘记调用init()还调了半天
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
//对于长度为奇数的正方形，以格子（一个1*1的正方形）为中心二分最远符合条件的长度
int l=0,r=max(n,m);
while(l<r)
{
int mid=(l+r+1)>>1;
if(i-mid>=1&&j-mid>=1&&i+mid<=n&&j+mid<=m&&check(i-mid,j-mid,i+mid,j+mid)) l=mid;
else r=mid-1;
}
ans+=l+1;
//对于长度为偶数的正方形，以格点（就是一个点）为中心二分最远符合条件的长度
l=0,r=max(n,m);
while(l<r)
{
int mid=(l+r+1)>>1;
if(i-mid+1>=1&&j-mid+1>=1&&i+mid<=n&&j+mid<=m&&check(i-mid+1,j-mid+1,i+mid,j+mid)) l=mid;
else r=mid-1;
}
ans+=l;
}
printf("%d\n",ans);
return 0;
}
```