Wannafly模拟赛 A.矩阵(二分答案+hash)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

矩阵

时间限制：1秒空间限制：131072K

题目描述

给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。

输入描述:

第一行两个整数n, m代表矩阵的长和宽；
接下来n行，每行m个字符（小写字母），表示矩阵；

输出描述:

输出一个整数表示满足条件的最大正方形的边长。

示例1

输入

5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl

输出

备注:

对于30%的数据，n,m≤100；
对于100%的数据，n,m≤500；

题目链接：https://www.nowcoder.com/acm/contest/submit/f8363c912a4c48a28b80f47e7102b6b8?ACMContestId=2&tagId=4

思路：二分答案mid，然后检验是否存在两个相同的mid*mid的正方形

检验方法：

首先对于每个位置，求出它开始长度为mid的横行的hash值

然后对于hash值再求一次竖列的hash值

将第二次求出的hash值排序，如果存在两个相同的hash值则可行

下面给出AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')
f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
inline void write(ll x)
{
if(x<)
{
putchar('-');
x=-x;
}
if(x>)
write(x/);
putchar(x%+'');
}
char dp[][];
ll n,m;
ll p1[],p2[];
ll p[][];
ll h[];
inline bool checked(ll x)
{
//
for(ll i=;i<=n;i++)
{
ll ans=;
for(ll j=;j<x;j++)
{
ans=ans*(ll)('a')+dp[i][j];
p[i][j]=;
}
for(ll j=x;j<=m;j++)
{
ans=ans*(ll)('a')-p1[x]*dp[i][j-x]+dp[i][j];
p[i][j]=ans;
}
}
//
ll GG=;
for(ll i=x;i<=m;i++)
{
ll PP=;
for(ll j=;j<x;j++)
{
PP=PP*(ll)('a'+(ll)(('A'+)/+))+p[j][i];
}
for(ll j=x;j<=n;j++)
{
PP=PP*(ll)('a'+(ll)(('A'+)/+))-p2[x]*p[j-x][i]+p[j][i];
h[GG]=PP;
GG++;
}
}
sort(h,h+GG);
for(ll i=;i<GG;i++)
{
if(h[i-]==h[i])
return true;
}
return false;
}
int main()
{
n=read();
m=read();
memset(p,,sizeof(p));
for(ll i=;i<=n;i++)
{
scanf("%s",dp[i]+);
for(ll j=;j<=m;j++)
{
dp[i][j]=dp[i][j]-('a'-);
}
}
ll l=;
ll r=min(n,m);
memset(p1,,sizeof(p1));
memset(p2,,sizeof(p2));
p1[]=;
p2[]=;
for(ll i=;i<=r;i++)
{
p1[i]=p1[i-]*(ll)('a');
p2[i]=p2[i-]*(ll)('a'+(ll)(('A'+)/+));
}
ll mid;
ll k;
while(l<=r)
{
mid=(l+r)/;
if(checked(mid))
{
l=(k=mid)+;
}
else
r=mid-;
}
write(k);
return ;
}