[JSOI2008]Blue Mary的战役地图（二分+哈希）

时间：2025-01-05 21:34:08

Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。

由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。

具体来说，Blue Mary已经将战役地图编码为n*n的矩阵，矩阵的每个格子里面是一个32位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。

Solution

这题的数据范围是允许我们n^4log(n)做的，大概就是二分一个答案，暴力枚举两个矩形的左上角。

但我们必须做到O(1)查询，所以需要预处理。

我们先设g[i][j][k]表示从第i行第j列，从这个格子往后K个格子的哈希值。

在用一个f[i][j][k]表示以i，j开头的边长为k的正方形的哈希值。

实现的话看代码就好了。

Code

#include<iostream>

#include<cstdio>

#define N 52

using namespace std;

typedef unsigned long long ll;

int n,ans;

ll HA[N][N][N],HB[N][N][N],ha[N][N][N],hb[N][N][N],a[N][N],b[N][N];

const ll base=;

ll power(ll x,ll y){

    ll ans=;

    while(y){

        if(y&)ans*=x;

        x*=x;

        y>>=;

    }

    return ans;

}

inline bool check(int pos){

    for(int i=;i<=n-pos+;++i)

      for(int j=;j<=n-pos+;++j)

        for(int k=;k<=n-pos+;++k)

          for(int l=;l<=n-pos+;++l)

            if(HA[i][j][pos]==HB[k][l][pos])return true;

    return false;

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;++i)for(int j=;j<=n;++j)scanf("%ull",&a[i][j]);

    for(int i=;i<=n;++i)for(int j=;j<=n;++j)scanf("%ull",&b[i][j]);

    for(int k=;k<=n;++k)

      for(int i=;i<=n;++i)

        for(int j=;j<=n-k+;++j){

            ha[i][j][k]=a[i][j];hb[i][j][k]=b[i][j];

            for(int l=j+;l<j+k;++l)

              ha[i][j][k]=ha[i][j][k]*base+a[i][l],

              hb[i][j][k]=hb[i][j][k]*base+b[i][l];

        }

    for(int k=;k<=n;++k){

      ll bas=power(base,k);

      for(int i=;i<=n-k+;++i)

        for(int j=;j<=n-k+;++j){

            HA[i][j][k]=ha[i][j][k];HB[i][j][k]=hb[i][j][k];

            for(int l=i+;l<i+k;++l)

              HA[i][j][k]=HA[i][j][k]*bas+ha[l][j][k],

              HB[i][j][k]=HB[i][j][k]*bas+hb[l][j][k];

        }

    }

    int l=,r=n;

    while(l<=r){

        int mid=(l+r)>>;

        if(check(mid)){

            ans=mid;

            l=mid+;

        }

        else r=mid-;

    }

    cout<<ans;

    return ;

}

相关文章