BZOJ2351 [BeiJing2011]Matrix 解题报告【数据结构】【Hash】

本文主要是介绍BZOJ2351 [BeiJing2011]Matrix 解题报告【数据结构】【Hash】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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。
题解
这道题是YYR上课的时候引用的。这道题无非就是考的一个行列hash的裸体。其中除了基础的hash操作之外，如何加加减减使得我们的前缀hash值变成部分hash值也是一个有趣的操作。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int N=1000;
const int BASE1=10016957;
const int BASE2=10016959;
const int Mod=10100;
using namespace std;
struct abcd{unsigned num;int next;
}table[N*N+5];
int m,n,a,b,q;
unsigned int sum[N+5][N+5],power1[N+5],power2[N+5];
int hash_table[Mod],tot;
void Hash(unsigned int x)//插入新的hash值 
{int pos=x%Mod;table[++tot].num=x;table[tot].next=hash_table[pos];hash_table[pos]=tot;
}
bool Get_Hash(unsigned int x)//查询其在hash表中的存在 
{int pos=x%Mod;for(int i=hash_table[pos];i;i=table[i].next)if(table[i].num==x)return true;return false;
}
int main()
{scanf("%d%d%d%d",&m,&n,&a,&b);for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)scanf("%1d",&sum[i][j]);for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)sum[i][j]+=sum[i-1][j]*BASE1;//行hash for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)sum[i][j]+=sum[i][j-1]*BASE2;//列hash power1[0]=power2[0]=1;for(int i=1;i<=N;i++)power1[i]=power1[i-1]*BASE1,power2[i]=power2[i-1]*BASE2;//打表打出base的i次幂 for(int i=a;i<=m;i++)for(int j=b;j<=n;j++){unsigned int temp=sum[i][j]-sum[i-a][j]*power1[a]-sum[i][j-b]*power2[b]+sum[i-a][j-b]*power1[a]*power2[b];//对前缀hash值加加减减得到部分hash Hash(temp);}for(scanf("%d",&q);q;q--){for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)scanf("%1d",&sum[i][j]);for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)sum[i][j]+=sum[i-1][j]*BASE1;for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)sum[i][j]+=sum[i][j-1]*BASE2;unsigned int temp=sum[a][b];if(Get_Hash(temp))puts("1");else puts("0");}return 0;
}