网站logo做黑页,求个网站这么难吗2022年贴吧,wordpress悬浮框,400网站建设推广题干#xff1a;
给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。
输入描述:
第一行两个整数n, m代表矩阵的长和宽#xff1b;
接下来n行#xff0c;每行m个字符#xff08;小写字母#xff09…题干
给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。
输入描述:
第一行两个整数n, m代表矩阵的长和宽
接下来n行每行m个字符小写字母表示矩阵
输出描述:
输出一个整数表示满足条件的最大正方形的边长。 示例1
输入
复制
5 10
ljkfghdfas
isdfjksiye
pgljkijlgp
eyisdafdsi
lnpglkfkjl
输出
复制
3
备注:
对于30%的数据n,m≤100
对于100%的数据n,m≤500
解题报告 二分一下矩阵的边长然后用字符串哈希判断两个矩阵是否相同就可以网络上找到一个map的解法但是感觉时间复杂度太不稳定好的时候700ms差的时候超时于是还是以后用多项式哈希吧。。这两个刚学哈希代码还是不特别美观、、
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 505;
using namespace std;
const ll D131,D2131;
int n,m;
char a[MAX][MAX];
ull pow1[MAX],pow2[MAX],h[MAX][MAX],tmp,tmp2,Hash[MAX*MAX];
bool ok(int x) {memset(h,0,sizeof h);int tot0;for(int i 1; in; i) {ull tmp 0;for(int j 1; jx; j) h[i][j] h[i][j-1] * D1 a[i][j];for(int j x; jm; j) h[i][j] h[i][j-1] * D1 a[i][j] - pow1[x] * a[i][j-x];
// for(int j 1; jx; j) tmp tmp * D1 a[i][j];
// for(int j x; jm; j) h[i][j] tmp * D1 a[i][j] - pow1[x] * a[i][j-x] , tmp h[i][j];}for(int j x; jm; j) {ull tmp 0;for(int i 1; ix; i) tmp tmp*D2 h[i][j];for(int i x; in; i) Hash[tot] tmp*D2 h[i][j] - pow2[x] * h[i-x][j] , tmp Hash[tot];}sort(Hash1,Hashtot1);for(int i 1; itot; i) {if(Hash[i] Hash[i1]) return 1;}return 0 ;
}
int main()
{
// ull qq1,ww2;
// cout qq-ww;scanf(%d%d,n,m);for(int i1; in; i) {scanf(%s,a[i]1);for(int j1; jm; j) {a[i][j]-(a-1);}}int l1,rmin(n,m);int mid (lr)1;int ans;pow1[0]pow2[0]1;for(int i1; in; i) pow1[i]pow1[i-1]*D1;for(int i1; im; i) pow2[i]pow2[i-1]*D2;while(lr) {mid(lr)1;if(ok(mid)) lmid1,ansmid;else rmid-1; }printf(%d,ans);return 0;
}
AC代码2map版这个时不时会跑个超时、。。
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
using namespace std;
typedef unsigned long long ull;
typedef pairint,intP;
#define maxn 505
int n,m;
char s[maxn][maxn];
ull h[maxn][maxn],b[maxn*maxn],base10007,hhh[maxn][maxn];
inline int ID(int i,int j) {return (i-1)*mj;
}
inline bool check(int mid) {mapull,intM;for(int x1; xn-mid1; x)for(int y1; ym-mid1; y) {int xxxmid-1,yyymid-1;ull val(h[xx][yy]-h[xx][y-1]-h[x-1][yy]h[x-1][y-1])*b[(n-x)*mm-y];if(M.find(val)!M.end())return 1;M[val]1;}return 0;
}
int main() {scanf(%d%d,n,m);for(int i1; in; i)scanf(%s,s[i]1);b[0]1;for(int i1; in; i)for(int j1; jm; j) {h[i][j]h[i][j-1]b[ID(i,j-1)]*(s[i][j]-a);b[ID(i,j)]b[ID(i,j-1)]*base;}
// for(int j1; jm; j)
// for(int i1; in; i)
// h[i][j]h[i-1][j];int l0,rmin(n,m),mid,ans0;while(lr) {mid(lr)/2;if(check(mid))ansmid,lmid1;else rmid-1;}printf(%d\n,ans);return 0;
}
总结据syt表示哈希题目多半带个log这次做题果然是需要比较所以需要先排序这样。
