Chrysanthemum's Blog

这是这套题最后完成的一题。然而做的我欲罢不能，骑虎难下啊。。。

题意：给你一个01矩阵，让你找出最大子正方形，使得他们是轴对称，4对称，8对称，90对称，180对称。轴对称就是关于四条对称轴任意一条对称，90对称就是顺时针旋转90与原矩阵相同，180对称就是旋转180与原矩阵相同，4对称就是既是轴对称又是180对称，8对称就是既是轴对称又是90对称。

题解：运用hash思想来解决这道题目。将原矩阵的每个点赋一个权值，（i，j）的权值为Aⁱ*B^j，把每个点乘以权值形成一个新矩阵，令这个矩阵为P，那么如何解决对称问题呢，举一个左右对称的例子，假如要判断最大的左右对称的子矩阵，我们可以把权值左右对称一下，然后得到另一个矩阵，令这个矩阵为Q，然后就是计算任意一个矩阵的hash值，我们只要用一下片段和，然后把整个矩形移到右下角（乘一个数即可），这就是一个子矩阵的hash值。假如要判断(x1,y1)->(x2,y2)的矩阵是否是左右对称，我们只要计算这个矩阵在P上的hash值与在Q上的hash值是否相同。以此类推其他对称情况。这样就O（1）实现矩阵对称性的判断，然而总复杂度还是n³的。但是我们可以发现只要确定中心，是有单调性的，只要二分即可。所以最我们在O（n²logn）的复杂度下日（哔~~~）掉了本题。

代码：

#include<cstdio>
using namespace std;
typedef unsigned int ull;
int n;
const int maxn=511,d1=666233,d2=2333;
ull h[7][maxn][maxn];
ull mi1[maxn],mi2[maxn];
char s[510];
/*
0代表原始1代表竖对称,2代表横对称,3代表主对角线对称,4代表副对角线对称 
5代表顺时针90度转,6代表180度转 
*/
void gethash()
{
    for (int k=0;k<=6;k++)
        for (int i=1;i<=n;i++)
        {
            ull P=mi1[n-i];
            for (int j=1;j<=n;j++)
            {
                h[k][i][j]=h[k][i][j]*P*mi2[n-j];
                h[k][i][j]+=h[k][i-1][j]+h[k][i][j-1]-h[k][i-1][j-1];
            }
        }
}
ull calc(int k,int x,int y,int len){return (h[k][x][y]-h[k][x-len][y]-h[k][x][y-len]+h[k][x-len][y-len])*mi1[x]*mi2[y];}
int judge(int i,int j,int len,int x)
{
    if (x==8)return judge(i,j,len,90)&judge(i,j,len,0);
    if (x==4)return judge(i,j,len,180)&judge(i,j,len,0);
    if (x==180&&calc(0,i,j,len)==calc(6,n-i+len,n-j+len,len))return 1;
    if (x==90&&calc(0,i,j,len)==calc(5,j,n-i+len,len))return 1;
    if (x==0&&
    (calc(0,i,j,len)==calc(1,i,n-j+len,len)||
    calc(0,i,j,len)==calc(2,n-i+len,j,len)||
    calc(0,i,j,len)==calc(3,j,i,len)||
    calc(0,i,j,len)==calc(4,n-i+len,n-j+len,len))) return 1;
    return 0;
}
int check(int len,int x)
{
    for (int i=len;i<=n;i++)
        for (int j=len;j<=n;j++) if (judge(i,j,len,x)) return 1;
    return 0;
}
int solve(int x)
{
    int l,r,mid;
    for (l=1,r=n/2;mid=l+r>>1,l<=r;){
        if (check(2*mid,x))l=mid+1;else r=mid-1;}
    l--;if (!check(2*l+1,x)) return 2*l;
    for (r=n/2;mid=l+r>>1,l<=r;)
        if (check(2*mid+1,x))l=mid+1;else r=mid-1;
    l--;return 2*l+1;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s);
        for (int j=1;j<=n;j++) h[0][i][j]=h[1][i][n-j+1]=h[2][n-i+1][j]=h[3][j][i]=h[4][n-j+1][n-i+1]=h[5][j][n-i+1]=h[6][n-i+1][n-j+1]=s[j-1]-'0';
    }
    mi1[0]=1;for (int i=1;i<=n;i++) mi1[i]=mi1[i-1]*d1;
    mi2[0]=1;for (int i=1;i<=n;i++) mi2[i]=mi2[i-1]*d2;
    gethash();
    printf("%d %d %d %d %d\n",solve(8),solve(90),solve(4),solve(180),solve(0));
    return 0;
}