【bzoj1414&3705】[ZJOI2009]对称的正方形

2015.06.12 09:03 Fri | 23次阅读 | 旧日oi | 固定链接 | 源码

Description

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

题解

这道题的感觉有点像二维回文串,我们可以这样来搞,先用manacher求出每个以每个位置为中心的左右最长回文半径,上下最长回文半径,注意这里要添加一些0来处理偶数部分。
然后我们发现,若以一个点为中心的正方形直径是f,那么必满足在这个点左右各f/2个点中,上下的最长回文半径都>=f,上下的点也是如此,而点(i,j)和(i,j+1)对应的正方形各个端点都是有单调性的,所以我们可以做4遍单调队列来处理,预先处理出一个关于此行(列)的RMQ,然后单调队列删点的时候验证一下就行。
或许最后可以不用rmq,树状数组应该也能搞,但是比较麻烦,既要离散化,还要考虑负数。
自己的代码能力还是弱,所有的地方都想出来了,但是最后写的时候还是很费劲,还是看了下标程……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int s[2005][2005],h[2005][2005],g[15][2005];
int a[2005][2005],f[2005][2005],lg[2005];
int n,m,ans,tim;
int ask(int x,int y)
{
    int t=lg[y-x+1];
    return min(g[t][x],g[t][y-(1<<t)+1]);
}
int main()
{
    for(int i=2;i<=2000;i++) lg[i]=lg[i>>1]+1;
    cin>>n>>m;n=2*n-1;m=2*m-1;
    int i,j,k,p,mx,id,last;
    for(i=1;i<=n;i+=2) 
    for(j=1;j<=m;j+=2) 
    scanf("%d",&a[i][j]);
    for(p=1;p<=n;p++)
    for(mx=0,id=0,i=1;i<=m;i++)
    {
        if(mx>i) h[p][i]=min(h[p][2*id-i],mx-i);
        else h[p][i]=1;
        for(;i-h[p][i]>0&&i+h[p][i]<=m&&a[p][i+h[p][i]]==a[p][i-h[p][i]];h[p][i]++);
        if(h[p][i]+i>mx) mx=h[p][i]+i,id=i; 
    }
    for(p=1;p<=m;p++)
    for(mx=0,id=0,i=1;i<=n;i++)
    {
        if(mx>i) s[i][p]=min(s[2*id-i][p],mx-i);
        else s[i][p]=1;
        for(;i-s[i][p]>0&&i+s[i][p]<=n&&a[i+s[i][p]][p]==a[i-s[i][p]][p];s[i][p]++);
        if(s[i][p]+i>mx) mx=s[i][p]+i,id=i; 
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++) g[0][j]=s[i][j]-1;
        for(k=1;(1<<k)<=m;k++)
        for(j=1;j<=m;j++) 
        {
            g[k][j]=g[k-1][j];
            if (j+(1<<(k-1))<=m+1) g[k][j]=min(g[k][j],g[k-1][j+(1<<(k-1))]);
        }
        for(j=1,last=1;j<=m;j++) 
        {
            while(ask(last,j)<j-last) last++;
            f[i][j]=min(s[i][j],j-last);
        }
        for(j=m,last=m;j;j--)
        {
            while(ask(j,last)<last-j) last--;
            f[i][j]=min(s[i][j],last-j);
        }
    }
    for(j=1;j<=m;j++)
    {
        for(i=1;i<=n;i++) g[0][i]=h[i][j]-1;
        for(k=1;(1<<k)<=n;k++)
        for(i=1;i<=n;i++)
        {
            g[k][i]=g[k-1][i];
            if (i+(1<<(k-1))<=n+1) 
            g[k][i]=min(g[k][i],g[k-1][i+(1<<(k-1))]);
        }
        for(i=1,last=1;i<=n;i++)
        {
            while(ask(last,i)<i-last) last++;
            f[i][j]=min(f[i][j],i-last);
        }
        for(i=n,last=n;i;i--)
        {
            while(ask(i,last)<last-i) last--;
            f[i][j]=min(f[i][j],last-i);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        if(a[i][j]) ans+=(f[i][j]>>1)+1;
        else if(i%2==0&&j%2==0) ans+=(f[i][j]+1)>>1;
    }
    printf("%d\n",ans);
    return 0;
}```