时间限制：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会好些
京公网安备 11010502036488号