「BZOJ1567」[JSOI2008] Blue Mary的战役地图
Description
Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。 由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。 具体来说，Blue Mary已经将战役地图编码为n*n的矩阵，矩阵的每个格子里面是一个32位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。
Input
第一行包含一个正整数n。 以下n行，每行包含n个正整数，表示第一张战役地图的代表矩阵。 再以下n行，每行包含n个正整数，表示第二张战役地图的代表矩阵。
Output
仅包含一行。这一行仅有一个正整数，表示这两个矩阵的相似程度。
Sample Input
3
1 2 3
4 5 6
7 8 9
5 6 7
8 9 1
2 3 4
1 2 3
4 5 6
7 8 9
5 6 7
8 9 1
2 3 4
Sample Output
2
HINT
样例解释：
子矩阵：
5 6
8 9
为两个地图的最大公共矩阵
约定：
n<=50
题解
二分子矩阵的边长。。。
把第一个矩阵的所有子矩阵放进hash，实际上我是用自然溢出+排序T T
第二个矩阵的所有子矩阵分别在hash中查找（排序后二分）
注意在行/列上计算key时乘的数应不同。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #include<cmath> #include<map> #include<queue> #define inf 2000000000 #define ll unsigned long long 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; } int n,ans,cnt; ll T[55],f[2][55][55]; int a[2][55][55]; ll H[5005]; int cal(int t,int x,int y,int l) { ll val=1; for(int i=x;i<=x+l-1;i++) val=(val*3659+f[t][i][y+l-1]-f[t][i][y-1]*T[l]); return val; } bool check(int x) { cnt=0; for(int i=1;i<=n-x+1;i++) for(int j=1;j<=n-x+1;j++) H[++cnt]=cal(0,i,j,x); sort(H+1,H+cnt+1); for(int i=1;i<=n-x+1;i++) for(int j=1;j<=n-x+1;j++) { ll t=cal(1,i,j,x); if(*lower_bound(H+1,H+cnt+1,t)==t) return 1; } return 0; } int main() { T[0]=1;for(int i=1;i<=50;i++)T[i]=T[i-1]*1789; n=read(); for(int K=0;K<=1;K++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[K][i][j]=read(); for(int K=0;K<=1;K++) for(int i=1;i<=n;i++) { f[K][i][0]=1; for(int j=1;j<=n;j++) f[K][i][j]=f[K][i][j-1]*1789+a[K][i][j]; } int l=1,r=n; while(l<=r) { int mid=(l+r)>>1; if(check(mid))ans=mid,l=mid+1; else r=mid-1; } printf("%d",ans); return 0; } |
计数器 9854515
OI 课件=>
OI 课件=>
黄学长，您cal函数返回值好像应该是ll，不是int