时间限制:1秒 空间限制:131072K
给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。
第一行两个整数n, m代表矩阵的长和宽;
接下来n行,每行m个字符(小写字母),表示矩阵;
输出一个整数表示满足条件的最大正方形的边长。
示例1
5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl
3
对于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代码:
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 }