首页 > 代码库 > BZOJ 1567 Blue Mary的战役地图(二维hash+二分)
BZOJ 1567 Blue Mary的战役地图(二维hash+二分)
题意: 求两个矩形最大公共子正方形。(n<=50)
范围这么小可以枚举子正方形的边长。那么可以对这个矩形进行二维hash,就可以在O(1)的时候求出任意子矩形的hash值。然后判断这些正方形的hash值有没有相同的
部分就行了。可以用二分来判断。
需要注意的是行和列乘的hash种子值需要不同的质数,否则可能出现冲突。
时间复杂度O(n^3logn).
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi acos(-1.0) # define eps 1e-9 # define MOD 1024523 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { 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; } void Out(int a) { if(a<0) {putchar(‘-‘); a=-a;} if(a>=10) Out(a/10); putchar(a%10+‘0‘); } const int N=55; //Code begin... int hash1[N][N], hash2[N][N], P[N*N], Q[N*N], n; VI a; VI::iterator it; bool check(int ans){ FOR(i,ans,n) FOR(j,ans,n) { int tmp=hash2[i][j]-hash2[i-ans][j]*Q[ans]-hash2[i][j-ans]*P[ans]+hash2[i-ans][j-ans]*P[ans]*Q[ans]; it=lower_bound(a.begin(),a.end(),tmp); if (it==a.end()||*it!=tmp) continue; return true; } return false; } int main () { scanf("%d",&n); P[0]=1; FOR(i,1,250) P[i]=P[i-1]*131; Q[0]=1; FOR(i,1,250) Q[i]=Q[i-1]*1789; FOR(i,1,n) FOR(j,1,n) scanf("%d",&hash1[i][j]), hash1[i][j]+=hash1[i][j-1]*P[1]; FOR(i,1,n) FOR(j,1,n) hash1[i][j]+=hash1[i-1][j]*Q[1]; FOR(i,1,n) FOR(j,1,n) scanf("%d",&hash2[i][j]), hash2[i][j]+=hash2[i][j-1]*P[1]; FOR(i,1,n) FOR(j,1,n) hash2[i][j]+=hash2[i-1][j]*Q[1]; int ans; for (ans=n; ans>=1; --ans) { a.clear(); FOR(i,ans,n) FOR(j,ans,n) a.pb(hash1[i][j]-hash1[i-ans][j]*Q[ans]-hash1[i][j-ans]*P[ans]+hash1[i-ans][j-ans]*P[ans]*Q[ans]); sort(a.begin(),a.end()); if (check(ans)) break; } printf("%d\n",ans); return 0; }
BZOJ 1567 Blue Mary的战役地图(二维hash+二分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。