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

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

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

5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl

3

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

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 inline ll read()
  5 {
  6     ll x=0,f=1;
  7     char ch=getchar();
  8     while(ch<'0'||ch>'9')
  9     {
 10         if(ch=='-')
 11             f=-1;
 12         ch=getchar();
 13     }
 14     while(ch>='0'&&ch<='9')
 15     {
 16         x=x*10+ch-'0';
 17         ch=getchar();
 18     }
 19     return x*f;
 20 }
 21 inline void write(ll x)
 22 {
 23     if(x<0)
 24     {
 25         putchar('-');
 26         x=-x;
 27     }
 28     if(x>9)
 29         write(x/10);
 30     putchar(x%10+'0');
 31 }
 32 char dp[521][521];
 33 ll n,m;
 34 ll p1[520],p2[520];
 35 ll p[555][555];
 36 ll h[250010];
 37 inline bool checked(ll x)
 38 {
 39     //
 40     for(ll i=1;i<=n;i++)
 41     {
 42         ll ans=0;
 43         for(ll j=1;j<x;j++)
 44         {
 45             ans=ans*(ll)('a')+dp[i][j];
 46             p[i][j]=0;
 47         }
 48         for(ll j=x;j<=m;j++)
 49         {
 50             ans=ans*(ll)('a')-p1[x]*dp[i][j-x]+dp[i][j];
 51             p[i][j]=ans;
 52         }
 53     }
 54     //
 55     ll GG=0;
 56     for(ll i=x;i<=m;i++)
 57     {
 58         ll PP=0;
 59         for(ll j=1;j<x;j++)
 60         {
 61             PP=PP*(ll)('a'+(ll)(('A'+1)/2+1))+p[j][i];
 62         }
 63         for(ll j=x;j<=n;j++)
 64         {
 65             PP=PP*(ll)('a'+(ll)(('A'+1)/2+1))-p2[x]*p[j-x][i]+p[j][i];
 66             h[GG]=PP;
 67             GG++;
 68         }
 69     }
 70     sort(h,h+GG);
 71     for(ll i=1;i<GG;i++)
 72     {
 73         if(h[i-1]==h[i])
 74             return true;
 75     }
 76     return false;
 77 }
 78 int main()
 79 {
 80     n=read();
 81     m=read();
 82     memset(p,0,sizeof(p));
 83     for(ll i=1;i<=n;i++)
 84     {
 85         scanf("%s",dp[i]+1);
 86         for(ll j=1;j<=m;j++)
 87         {
 88             dp[i][j]=dp[i][j]-('a'-1);
 89         }
 90     }
 91     ll l=1;
 92     ll r=min(n,m);
 93     memset(p1,0,sizeof(p1));
 94     memset(p2,0,sizeof(p2));
 95     p1[0]=1;
 96     p2[0]=1;
 97     for(ll i=1;i<=r;i++)
 98     {
 99         p1[i]=p1[i-1]*(ll)('a');
100         p2[i]=p2[i-1]*(ll)('a'+(ll)(('A'+1)/2+1));
101     }
102     ll mid;
103     ll k;
104     while(l<=r)
105     {
106         mid=(l+r)/2;
107         if(checked(mid))
108         {
109             l=(k=mid)+1;
110         }
111         else
112             r=mid-1;
113     }
114     write(k);
115     return 0;
116 }