题目描述

Description

给定一个M行N列的01矩阵，以及Q个A行B列的01矩阵，你需要求出这Q个矩阵哪些在原矩阵中出现过。
所谓01矩阵，就是矩阵中所有元素不是0就是1。

Input

输入文件的第一行为M、N、A、B，参见题目描述。
接下来M行，每行N个字符，非0即1，描述原矩阵。
接下来一行为你要处理的询问数Q。
接下来Q个矩阵，一共Q*A行，每行B个字符，描述Q个01矩阵。

Output

你需要输出Q行，每行为0或者1，表示这个矩阵是否出现过，0表示没有出现过，1表示出现过。

Sample Input

3 3 2 2
111
000
111
3
11
00
11
11
00
11

Sample Output

1
0
1

HINT

对于100%的实际测试数据，M、N ≤ 1000，Q = 1000
对于40%的数据，A = 1。
对于80%的数据，A ≤ 10。
对于100%的数据，A ≤ 100。

题目分析

二维hash
先对每列用base1 hash 然后再对每行用base2 hash
相当于每个(i,j)保存了左上角为(1,1)，右下角为(i,j)的矩阵hash值
二维hash的方法有很多，但这么做的好处是能O(1)时间拿出一个矩阵的hash值

2351 必须unsigned long long + 双base+map 否则会wa
2462 不能用Map 否则会T 单base 双base 都能过

code: 2351

#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,A,B,q;
char sa[10010];
typedef unsigned long long ull;
ull base=233333,bas=2333,mp[1010][1010];
//bool operator < (your x,your y){return x.x==y.x?x.y<y.y:x.x<y.x;}
map<ull,bool>s;
ull po[1010],pop[1010],hsh[1010][1010];
void init()
{
    po[0]=1,pop[0]=1;
    for(int i=1;i<=1000;i++) 
        po[i]=po[i-1]*base,pop[i]=pop[i-1]*bas;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            hsh[i][j]=hsh[i-1][j]*base+mp[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            hsh[i][j]=hsh[i][j-1]*bas+hsh[i][j];
    for(int i=A;i<=n;i++)
        for(int j=B;j<=m;j++)
        {
            ull tmp=hsh[i][j];
            tmp-=hsh[i-A][j]*po[A];
            tmp-=hsh[i][j-B]*pop[B];
            tmp+=hsh[i-A][j-B]*po[A]*pop[B];
            s[tmp]=1;
        }
}
int main()
{   
    scanf("%d%d%d%d",&n,&m,&A,&B);
    for(int i=1;i<=n;i++)
    {   
        scanf("%s",sa+1);
        for(int j=1;j<=m;j++) mp[i][j]=sa[j]-'0';
    }
    init();   
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        for(int j=1;j<=A;j++)
        {
            scanf("%s",sa+1);
            for(int k=1;k<=B;k++) mp[j][k]=sa[k]-'0';
        }
        for(int j=1;j<=A;j++)
            for(int k=1;k<=B;k++)
                mp[j][k]=mp[j-1][k]*base+mp[j][k];
        for(int k=1;k<=B;k++)
            mp[A][k]=mp[A][k-1]*bas+mp[A][k];
        if(s[mp[A][B]]) printf("1\n");
        else printf("0\n");
    }
    return 0;
}


code: 2462

#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,A,B,q;
char sa[10010];
typedef unsigned long long ull;
ull base=233333,mp[1010][1010];
//bool operator < (your x,your y){return x.x==y.x?x.y<y.y:x.x<y.x;}
//map<ull,bool>s;
ull po[1010],hsh[1010][1010];
ull mod=99999997;
bool s[99999997+10];
void init()
{
    po[0]=1;
    for(int i=1;i<=1000;i++) po[i]=po[i-1]*base;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            hsh[i][j]=hsh[i-1][j]*base+mp[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            hsh[i][j]=hsh[i][j-1]*base+hsh[i][j];
    for(int i=A;i<=n;i++)
        for(int j=B;j<=m;j++)
        {
            ull tmp=hsh[i][j];
            tmp-=hsh[i-A][j]*po[A];
            tmp-=hsh[i][j-B]*po[B];
            tmp+=hsh[i-A][j-B]*po[A]*po[B];
            s[tmp%mod]=1;
        }
}
int main()
{   
    scanf("%d%d%d%d",&n,&m,&A,&B);
    for(int i=1;i<=n;i++)
    {   
        scanf("%s",sa+1);
        for(int j=1;j<=m;j++) mp[i][j]=sa[j]-'0';
    }
    init();   
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        for(int j=1;j<=A;j++)
        {
            scanf("%s",sa+1);
            for(int k=1;k<=B;k++) mp[j][k]=sa[k]-'0';
        }
        for(int j=1;j<=A;j++)
            for(int k=1;k<=B;k++)
                mp[j][k]=mp[j-1][k]*base+mp[j][k];
        for(int k=1;k<=B;k++)
            mp[A][k]=mp[A][k-1]*base+mp[A][k];
        if(s[mp[A][B]%mod]) printf("1\n");
        else printf("0\n");
    }
    return 0;
}