题目描述

给定一个M行N列的01矩阵（只包含数字0或1的矩阵），再执行Q次询问，每次询问给出一个A行B列的01矩阵，求该矩阵是否在原矩阵中出现过。

输入格式
第一行四个整数M,N,A,B。

接下来一个M行N列的01矩阵，数字之间没有空格。

接下来一个整数Q。

接下来Q个A行B列的01矩阵，数字之间没有空格。

输出格式
对于每个询问，输出1表示出现过，0表示没有出现过。

数据范围
$A≤100，M,N≤1000，Q≤1000$

样例

输入样例：
3 3 2 2
111
000
111
3
11
00
11
11
00
11
输出样例：
1
0
1

二维前缀和+哈希

这道题目思路简短,就是开一个二位哈希前缀和,然后暴力枚举,然后check判断就是了,注意卡卡常数,不过BZOJ上不加O3也可以优化过.可见YXC老师的时间限制极高,有利于锻炼卡常

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned iny//一定要记住是无符号整数,感谢楼下的大佬指出问题.
#define fir(i,a,b) for(int i=a;i<=b;i++)
const int N=1100;
ull val[N*N],p1[N],p2[N],hash_a[N][N],Hash_2[N][N],has,ans;
int p=0,n,m,a,b;
const ull Pi=131,Pj=233;//P进制
inline void init()//初始化P进制权重
{
    p1[0]=1;
    p2[0]=1;
    fir(i,1,N)
    {
        p1[i]=p1[i-1]*233;
        p2[i]=p2[i-1]*131;
    }
}
inline void Hash_A()//计算哈希值
{
    fir(i,1,n)
    fir(j,1,m)
    hash_a[i][j]=hash_a[i-1][j]*Pi+hash_a[i][j];
    fir(i,1,n)
    fir(j,1,m)
    hash_a[i][j]=hash_a[i][j-1]*Pj+hash_a[i][j];
}
inline ull Hash_B()//计算哈希值
{
    fir(i,1,a)
    fir(j,1,b)
    Hash_2[i][j]=Hash_2[i-1][j]*Pi+Hash_2[i][j];
    fir(i,1,a)
    fir(j,1,b)
    Hash_2[i][j]=Hash_2[i][j-1]*Pj+Hash_2[i][j];
    return Hash_2[a][b];
}
int main()
{
//  freopen("stdout.out","w",stdout);
    init();
    scanf("%d%d%d%d\n",&n,&m,&a,&b);
    fir(i,1,n)
    fir(j,1,m)
    scanf("%1u",&hash_a[i][j]);
    Hash_A();
    fir(i,a,n)
    fir(j,b,m)
    {
        has=hash_a[i][j];
        has-=hash_a[i-a][j]*p2[a];
        has-=hash_a[i][j-b]*p1[b];
        has+=hash_a[i-a][j-b]*p2[a]*p1[b];//其实就是二维前缀和,只是乘以哈希权重而已.
        val[++p]=has;//记录这个哈希值
    }
    int q,flag=0;
    char ch;
    scanf("%d",&q);
    for(int v=1; v<=q; v++)
    {
        fir(i,1,a)
        fir(j,1,b)
        scanf("%1u",&Hash_2[i][j]);
        ans=Hash_B();
        fir(j,1,p-1)//找所有的哈希值,是否有一模一样的
        {
            if(val[j]==ans)
            {
                puts("1");
                flag=1;
                break;//找到了直接退出,不要浪费时间
            }
        }
        if(!flag)
            puts("0");
        flag=0;
    }
    return 0;
}