还是提供一种和秦淮岸不一样的做法。
Hash开散列
定义一个数列$A$的Hash值为$$\sum_{i=1}^n a_i*131^{n-i}$$
写成代码就是
ll res=0;
for(ll i=1;i<=n;++i)
res=res*131+a[i];
更一般地,定义一个矩阵$M$的Hash值为$$\sum_{i=1}^n f_i*131^{n-i}$$
$f_i$表示第i行的Hash值。
然后预处理:对于题目中原矩阵所有大小为$A\times B$的子矩阵,求出其Hash值mod size(我取了2000003,这是一个素数)的值(这部分的时间复杂度稍后讲,你也可以自己思考怎么快速求),并把这个子矩阵左上角坐标(因为ab已知,左上角就能表示一个子矩阵)插入这个值对应的邻接表。
查询时,求出要求的矩阵的Hash值,并再其对应的邻接表中查找即可。
剩下一个问题:如何快速计算所有大小为$A\times B$的子矩阵的Hash值?暴力求解的复杂度是$O(nmab)$,无法通过。
方法1:预处理f[i][j]表示第i行中,1~j的Hash值。由Hash函数的可减性,可以把求子矩阵每一行的Hash值的时间复杂度从$O(b)$降到$O(1)$,所以总时间复杂度是$O(nma)$,可以通过。
方法2:预处理原矩阵Hash值的二维前缀和,从而将求子矩阵Hash值的时间复杂度直接从$O(ab)$降为$O(1)$,但我不是很理解其正确性。
方法3:在方法1的基础上,如果左上角为$(i,n)$的子矩阵Hash值已知,那么左上角为$(i+1,j)$的子矩阵可以由它直接$O(1)$推得,故总时间复杂度$O(nm)$
但其实方法3不太好写,我就只写了方法1 试图为自己的菜找借口
期望中时间复杂度:O(nma+qab)
贴一下代码吧:
//Wan Hong 2.2
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
ll f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
bool umax(ll& a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
bool umin(ll& a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
/**********/
#define MAXN 1011
const ll sz=2000003;//开散列大小,Hash函数值对此取模
ll n,m,a,b;
bool p[MAXN][MAXN],s[MAXN][MAXN];//原矩阵,询问的矩阵
ll pw[MAXN],f[MAXN][MAXN];//131的次幂,f[i][j]表示第i行中,1~j的Hash值
pll xy[sz+4];//xy[i]:Hash开散列
ll get(ll x,ll l,ll r)//第x行[l,r]的Hash值
{
return (f[x][r]-f[x][l-1]*pw[r-l+1]%sz+sz)%sz;
}
ll last[sz+4],nxt[sz+4],cnt=0;//last:Hash值为i的表头
void insert(ll h,ll x,ll y)//插入Hash值为h,左上角是(i,j)的子矩阵
{
xy[++cnt]=pll(x,y);
nxt[cnt]=last[h];last[h]=cnt;
}
bool eql(ll x,ll y)//判断左上角是(i,j)的子矩阵和询问的矩阵是否相等
{
for(ll i=1;i<=a;++i)
for(ll j=1;j<=b;++j)
if(p[x+i-1][y+j-1]!=s[i][j])return 0;
return 1;
}
ll query(ll h)//询问
{
ll u=last[h];
while(u)
{
if(eql(xy[u].first,xy[u].second))return 1;
u=nxt[u];
}
return 0;
}
int main()
{
n=read(),m=read(),a=read(),b=read();
pw[0]=1;
for(ll i=1;i<=m;++i)pw[i]=pw[i-1]*131%sz;
for(ll i=1;i<=n;++i)
for(ll j=1;j<=m;++j)
{
char c=getchar();
while(c!='0'&&c!='1')c=getchar();
c-='0';
f[i][j]=(f[i][j-1]*131+c)%sz;
p[i][j]=c;
}
for(ll i=1;i<=n-a+1;++i)//处理子矩阵Hash值
for(ll j=1;j<=m-b+1;++j)
{
ll res=0;
for(ll k=i;k<i+a;++k)
res=(res*131+get(k,j,j+b-1))%sz;
insert(res,i,j);
}
ll q=read();
for(ll i=1;i<=q;++i)
{
ll res=0;
for(ll i=1;i<=a;++i)//处理询问矩阵Hash值
{
ll t=0;
for(ll j=1;j<=b;++j)
{
char c=getchar();
while(c!='0'&&c!='1')c=getchar();
c-='0';
s[i][j]=c;
t=(t*131+c)%sz;
}
res=(res*131+t)%sz;
}
printf("%lld\n",query(res));//询问
}
return 0;
}
居然没人点赞
蛮不错的
就是看不懂
确实
代码太复杂了,刻薄的我看不懂