题目链接

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld

题目描述

给定一个M行N列的01矩阵(只包含数字0或1的矩阵),再执行Q次询问,每次询问给出一个A行B列的01矩阵,求该矩阵是否在原矩阵中出现过。
输入描述: 第一行四个整数M,N,A,B。 接下来一个M行N列的01矩阵,数字之间没有空格。 接下来一个整数Q。
接下来Q个A行B列的01矩阵,数字之间没有空格。 输出描述: 对于每个询问,输出1表示出现过,0表示没有。

示例1
输入

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

输出

1
0
1

备注:
对于40%的数据,A = 1。
对于80%的数据,A≤10。
对于100%的数据,A≤100,M,N≤1000,Q≤1000。

题意:

给你个MN的二维矩阵,然后给你个AB的二维矩阵,问后者是否在前者出现过

题解

毫无疑问用hash
我们先想一个问题:
一个长为L的字符串a,问长度为len(len<L)的字符串b在a中出现过吗?
这个怎么做?
我们可以将a中长度为len的部分求出hash并放进哈希表,然后求出b的hash,进行比较即可

其实本题就是将一维问题转化成二维
我们将n * m的矩形中所有大小为a * b的矩形哈希一下并放到哈希表中,然后给出矩阵后,直接O(1)查找就可以了
求矩阵的hash的步骤:
先求出每一行前缀的hash,然后固定矩阵的一边长度b,求出长度为b的边的hash值,然后从这一行向下延伸a行,求出这a行对应的长度为b的hash值。当长度大于a后,就将最上面一行删去,始终保持为 a * b 的矩阵。

代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
typedef unsigned long long ull;
ull hash1[maxn][maxn];
ull base[maxn*maxn];
int base1=13;
char c[maxn];
ull get(ull hash1[],int l,int r)
{
   
    return hash1[r]-hash1[l-1]*base[r-l+1];
}
int q;
int n,m,a,b;
int main(){
   
   
    cin>>n>>m>>a>>b;
    base[0]=1;
    for(int i=1;i<=n*m;i++) base[i]=base[i-1]*base1;//素数倍数,用于查询子串哈希值 
    
    for(int i=1;i<=n;i++)
	{
   
        scanf("%s",c+1);
        for(int j=1;j<=m;j++) hash1[i][j]=hash1[i][j-1]*base1+c[j]-'0';//求取每一行前缀哈希值 
    }
    unordered_set<ull> s;
    for(int i=b;i<=m;i++)
	{
   
        ull x=0;
        int l=i-b+1,r=i;
        for(int j=1;j<=n;j++)
		{
   
            x=x*base[b]+get(hash1[j],l,r);// 加上当前行的hash值 
            if(j>a) x-=get(hash1[j-a],l,r)*base[a*b];// 如果超行了,删去最上面一行 
            if(j>=a)
			{
   
                s.insert(x);//用map来存哈希值,方便后面的判断是否存在 
            }
        }
    }
 
    cin>>q;
    while(q--)
	{
   
        ull x=0;
        for(int i=0;i<a;i++)
		{
   
            scanf("%s",c);
            for(int j=0;j<b;j++)
			{
   
                x=x*base1+c[j]-'0';//将所给的矩阵转化成hash 
            }
        }
        if(s.count(x))//利用map性质查询是否有这个数 
		cout<<"1"<<endl;
        else cout<<"0"<<endl;
    }
    return 0;
}

不过这样做,好像超内存了。。。
可以手写map会好些