【URAL 1486】Equal Squares(二维哈希+二分)
Description
During a discussion of problems at the Petrozavodsk Training Camp, Vova and Sasha argued about who of them could in 300 minutes find a pair of equal squares of the maximal size in a matrix of size N × M containing lowercase English letters. Squares could overlap each other but could not coincide. He who had found a pair of greater size won. Petr walked by, looked at the matrix, said that the optimal pair of squares had sides K, and walked on. Vova and Sasha still cannot find this pair. Can you help them?
Input
The first line contains integers N and M separated with a space. 1 ≤ N, M ≤ 500. In the next N lines there is a matrix consisting of lowercase English letters, M symbols per line.
Output
In the first line, output the integer K which Petr said. In the next two lines, give coordinates of upper left corners of maximal equal squares. If there exist more than one pair of equal squares of size K, than you may output any of them. The upper left cell of the matrix has coordinates (1, 1), and the lower right cell has coordinates (N, M). If there are no equal squares in the matrix, then output 0.
Sample input
5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl
Sample output
3
1 1
3 3
题解
二分答案,然后利用二维哈希\(O(n^2)\)check,总的时间为\(O(n^2 logn)\)
参考代码
#include <map>
#include <queue>
#include <cstdio>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll unsigned long long
#define inf 1000000000
#define PI acos(-1)
#define bug puts("here")
#define REP(i,x,n) for(int i=x;i<=n;i++)
#define DEP(i,n,x) for(int i=n;i>=x;i--)
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void Out(int a){
if(a<0) putchar('-'),a=-a;
if(a>=10) Out(a/10);
putchar(a%10+'0');
}
const int N=505;
char a[N][N];
ll ha[N][N];
ll p1[N],p2[N];
map<ll,int>vis;
int ansx1,ansy1,ansx2,ansy2;
int n,m;
struct node{
int x,y;
}book[N*N];
bool check(int s){
vis.clear();
ll tmp;int tot=0;
REP(i,s,n) REP(j,s,m){
tmp=ha[i][j]-ha[i-s][j]*p2[s]-ha[i][j-s]*p1[s]+ha[i-s][j-s]
*p1[s]*p2[s];
if(vis[tmp]){
int id=vis[tmp];
ansx1=book[id].x;ansy1=book[id].y;
ansx2=i-s+1;ansy2=j-s+1;
return true;
}
++tot;
book[tot].x=i-s+1;book[tot].y=j-s+1;
vis[tmp]=tot;
}
return false;
}
int main(){
cin>>n>>m;
REP(i,1,n) cin>>(a[i]+1);
int seed1=123,seed2=1789;
REP(i,1,n) REP(j,1,m) ha[i][j]=ha[i][j-1]*seed1+a[i][j];
REP(i,1,n) REP(j,1,m) ha[i][j]=ha[i-1][j]*seed2+ha[i][j];
p1[0]=p2[0]=1;
REP(i,1,m) p1[i]=p1[i-1]*seed1;
REP(i,1,n) p2[i]=p2[i-1]*seed2;
int l=1,r=min(n,m),ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
l=mid+1;
ans=mid;
}else r=mid-1;
}
if(ans!=-1){
printf("%d\n",ans);
printf("%d %d\n%d %d\n",ansx1,ansy1,ansx2,ansy2);
}else puts("0");
return 0;
}
最新文章
- python基础(1) 变量类型
- 复旦大学2014--2015学年第二学期(14级)高等代数II期末考试第八大题解答
- Autolayout及VFL经验分享
- delphi 中字符串与16进制、10进制转换函数
- WinForm实现跨进程通信的方法
- input placeholder文字垂直居中(Mobile &; PC)
- mobilize扁平化的fullPage.js类工具使用心得
- 更新sdk
- MySQL安装--ubuntu
- iphone与安卓的兼容性问题汇总
- javascript 函数的多义性
- TOMCAT的框架结构
- git stash解决代码merge出错
- phantomjs 中文文档
- [原][杂谈]如果人类的末日:";天网";出现
- vue-实例生命周期钩子(不太明白)
- 使用通配符和泛型:完成父子类关系的List对象的类型匹配
- android矩阵详解
- (转载)Unity 关于动态监听时,点击Button,返回其在数组中的下标
- tomcat manager
热门文章
- c++ 头文件路径选择
- python之文件的读写
- 使用ansible对远程主机上的ssh公钥进行批量分发
- Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) 题解
- (5)《Head First HTML与CSS》学习笔记---布局与定位
- Math.net,.net上的科学计算利器
- String 截取字符串#中间的文本
- HTTP协议 处理流程
- Can&#39;t locate ExtUtils/MakeMaker.pm in @INC
- Hibernate中的inverse和cascade属性