首页 > 代码库 > 【字符矩阵哈希】bzoj2351 [BeiJing2011]Matrix
【字符矩阵哈希】bzoj2351 [BeiJing2011]Matrix
引用题解:http://blog.csdn.net/popoqqq/article/details/41084047
#include<cstdio>#include<cstring>using namespace std;typedef unsigned long long ull;int n,m,a,b,q;const ull seed1=17,seed2=19;#define MOD 1000001ull v[MOD],sum[1001][1001],ord[201],pow1[1001],pow2[1001];char s[1001][1001];int first[MOD],next[MOD],en;void Insert(const ull &V){ int U=(int)(V%MOD); v[en]=V; next[en]=first[U]; first[U]=en++;}int main(){ scanf("%d%d%d%d",&n,&m,&a,&b); memset(first,-1,sizeof(first)); ord[‘0‘]=1,ord[‘1‘]=2; for(int i=1;i<=n;++i) scanf("%s",s[i]+1); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) sum[i][j]=ord[s[i][j]]+sum[i-1][j]*seed1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) sum[i][j]+=sum[i][j-1]*seed2; pow1[0]=pow2[0]=1; for(int i=1;i<=n;i++) pow1[i]=pow1[i-1]*seed1; for(int i=1;i<=m;i++) pow2[i]=pow2[i-1]*seed2; for(int i=a;i<=m;i++) for(int j=b;j<=n;j++) Insert(sum[i][j] -sum[i-a][j]*pow1[a] -sum[i][j-b]*pow2[b] +sum[i-a][j-b]*pow1[a]*pow2[b]); scanf("%d",&q); for(;q;--q) { for(int i=1;i<=a;i++) scanf("%s",s[i]+1); for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) sum[i][j]=ord[s[i][j]]+sum[i-1][j]*seed1; for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) sum[i][j]+=sum[i][j-1]*seed2; int o=(int)(sum[a][b]%MOD); for(int i=first[o];i!=-1;i=next[i]) if(v[i]==sum[a][b]) {puts("1"); goto OUT;} puts("0"); OUT:; } return 0;}
【字符矩阵哈希】bzoj2351 [BeiJing2011]Matrix
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。