NKOJ 2663 （ZJOI 2009）对称的正方形（Manacher）

发表于 |
字数统计: 830字 | 阅读时长 ≈ 4min

P2663【ZJOI 2009 Day2】对称的正方形

问题描述

Orez很喜欢搜集一些神秘的数据，并经常把它们排成一个矩阵进行研究。最近，Orez又得到了一些数据，并已经把它们排成了一个n行m列的矩阵。通过观察，Orez发现这些数据蕴涵了一个奇特的数，就是矩阵中上下对称且左右对称的正方形子矩阵的个数。
Orez自然很想知道这个数是多少，可是矩阵太大，无法去数。只能请你编个程序来计算出这个数。

输入格式

第一行为两个整数n和m。
接下来n行每行包含m个正整数，表示Orez得到的矩阵。

输出格式

仅包含一个整数answer，表示矩阵中有answer个上下左右对称的正方形子矩阵。

样例输入

5 5
4 2 4 4 4
3 1 4 4 3
3 5 3 3 3
3 1 5 3 3
4 2 1 2 4

样例输出

27

提示

对于30%的数据 n，m≤100
对于100%的数据 n，m≤1000 ，矩阵中的数的大小≤10^9

数据范围很小，考虑暴力做法。
直接将每一行每一列跑一次Manacher，记录下对应的最长回文子串长度，对于奇偶的处理同样是在相邻两个树之间添加字符。
然后枚举一个点作为正方形的中心点，向四个方向同时拓展即可。
貌似可以利用单调性优化一部分，但暴力还是跑得很快的。

代码：

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
#include<stdio.h>
#include<algorithm>
#define N 2222
using namespace std;
int n,m,G[N][N],HR[N][N],LR[N][N],Max,pos,Ans;
void Manacher(int k)
{
	Max=0;pos=0;
	for(int i=1;i<=m;i++)
	{
		if(i>Max)HR[k][i]=1;
		else HR[k][i]=min(Max-i+1,HR[k][2*pos-i]);
		while(i-HR[k][i]>0&&i+HR[k][i]<=m&&G[k][i-HR[k][i]]==G[k][i+HR[k][i]])HR[k][i]++;
		if(i+HR[k][i]-1>Max)Max=i+HR[k][i]-1,pos=i;
	}
}
void manacher(int k)
{
	Max=0;pos=0;
	for(int i=1;i<=n;i++)
	{
		if(i>Max)LR[k][i]=1;
		else LR[k][i]=min(Max-i+1,LR[k][2*pos-i]);
		while(i-LR[k][i]>0&&i+LR[k][i]<=n&&G[i-LR[k][i]][k]==G[i+LR[k][i]][k])LR[k][i]++;
		if(i+LR[k][i]-1>Max)Max=i+LR[k][i]-1,pos=i;
	}
}
int main()
{
	int i,j,k,u,d,l,r,Min;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)scanf("%d",&G[i<<1][j<<1]);
	n=n<<1|1;m=m<<1|1;
	for(i=1;i<=n;i++)if(i-1&1)Manacher(i);
	for(i=1;i<=m;i++)if(i-1&1)manacher(i);
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	if(i+j-1&1)
	{
		u=d=i;l=r=j;k=2;
		u--;d++;l--;r++;
		if(HR[i][j])Min=min(HR[i][j],LR[j][i]);
		else Min=n;
		while((Min>=k&&HR[u][j]>=k&&HR[d][j]>=k&&LR[l][i]>=k&&LR[r][i]>=k)||(k+i-1&1))
		{
			if(HR[u][j])Min=min(HR[u][j],Min);
			if(HR[d][j])Min=min(HR[d][j],Min);
			if(LR[l][i])Min=min(LR[l][i],Min);
			if(LR[r][i])Min=min(LR[r][i],Min);
			u--;d++;l--;r++;k++;
		}
		if(j&1)Ans+=k-2>>1;
		else Ans+=k-1>>1;
	}
	printf("%d",Ans);
}