首页 > 代码库 > BZOJ 1567 JSOI2008 Blue Mary的战役地图 Hash+二分
BZOJ 1567 JSOI2008 Blue Mary的战役地图 Hash+二分
题目大意:给定两个矩阵,求最大公共子正方形边长
首先二分答案 然后Check的时候先把A矩阵的所有边长为x的子正方形存在哈希表里 然后枚举B矩阵的每个子正方形查找
注意二维哈希的时候横竖用的两个BASE不能一样 否则当两个矩阵关于对角线对称的时候会判断为相等
尼玛我的哈希表居然比map慢……不活了
#include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 60 #define SIZE 1001001 #define BASE1 999911657 #define BASE2 999911659 using namespace std; typedef unsigned int u; int n,T; u a[M][M],b[M][M],power1[M],power2[M]; map<u,int>table; bool Judge(int x) { int i,j; ++T; for(i=x;i<=n;i++) for(j=x;j<=n;j++) { u hash=a[i][j] -a[i-x][j]*power1[x] -a[i][j-x]*power2[x] +a[i-x][j-x]*power1[x]*power2[x]; table[hash]=T; } for(i=x;i<=n;i++) for(j=x;j<=n;j++) { u hash=b[i][j] -b[i-x][j]*power1[x] -b[i][j-x]*power2[x] +b[i-x][j-x]*power1[x]*power2[x]; if( table[hash]==T ) return true; } return false; } int Bisection() { int l=0,r=n; while(l+1<r) { int mid=l+r>>1; if( Judge(mid) ) l=mid; else r=mid; } if( Judge(r) ) return r; return l; } int main() { int i,j; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%u",&a[i][j]); for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]+=a[i-1][j]*BASE1; for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]+=a[i][j-1]*BASE2; for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%u",&b[i][j]); for(i=1;i<=n;i++) for(j=1;j<=n;j++) b[i][j]+=b[i-1][j]*BASE1; for(i=1;i<=n;i++) for(j=1;j<=n;j++) b[i][j]+=b[i][j-1]*BASE2; power1[0]=power2[0]=1; for(i=1;i<=n;i++) power1[i]=power1[i-1]*BASE1, power2[i]=power2[i-1]*BASE2; cout<<Bisection()<<endl; }
BZOJ 1567 JSOI2008 Blue Mary的战役地图 Hash+二分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。