bzoj 2351 [BeiJing2011]Matrix——二维哈希

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2351

就是先把每行单独从左到右扫着乘一个 b1 哈希起来,然后再按列从上往下乘一个 b2 哈希起来。

如果要取模的话,行的哈希和列的哈希应该模一样的数。

当然不是读入询问再枚举所有位置看哈希值啦……应该先把合法位置的哈希值用一个 map 之类的存一下存在性,询问的时候直接查 map 就行了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define ull unsigned long long
using namespace std;
const int N=,b1=1e9+,b2=;
int n,m,a,b; ull bn1[N],bn2[N],hs[N][N];
map<ull,bool> mp;
int main()
{
scanf("%d%d%d%d",&n,&m,&a,&b);
bn1[]=;for(int i=;i<=n;i++)bn1[i]=bn1[i-]*b1;
bn2[]=;for(int i=;i<=m;i++)bn2[i]=bn2[i-]*b2;
for(int i=,d;i<=n;i++)
for(int j=;j<=m;j++)
{
scanf("%1d",&d); d++;//
hs[i][j]=hs[i][j-]*b2+d;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
hs[i][j]=hs[i-][j]*b1+hs[i][j];
for(int i=a;i<=n;i++)
for(int j=(i==a?b:);j<=m;j++)
{
ull tp=hs[i][j] - hs[i-a][j]*bn1[a]
- hs[i][j-b]*bn2[b] + hs[i-a][j-b]*bn1[a]*bn2[b];
mp[tp]=;
}
int Q; scanf("%d",&Q);
while(Q--)
{
ull tmp=;
for(int i=,d;i<=a;i++)
for(int j=;j<=b;j++)
{
scanf("%1d",&d); d++;
tmp+=d*bn1[a-i]*bn2[b-j];
}
puts(mp[tmp]?"":"");
}
return ;
}
上一篇:C#设计模式(1)-单例模式


下一篇:Alpha冲刺! Day6 - 砍柴