P10474 [ICPC 2011 Beijing R] Matrix 矩阵哈希
题目描述
给定一个MMM行NNN列的010101矩阵，以及QQQ个AAA行BBB列的010101矩阵，你需要求出这QQQ个矩阵哪些在原矩阵中出现过。
所谓010101矩阵，就是矩阵中所有元素不是000就是111。
输入格式
输入文件的第一行为M,N,A,BM,N,A,BM,N,A,B，参见题目描述。
接下来MMM行，每行NNN个字符，非000即111，描述原矩阵。
接下来一行为你要处理的询问数QQQ。
接下来QQQ个矩阵，一共Q×AQ\times AQ×A行，每行BBB个字符，描述QQQ个010101矩阵。
输出格式
你需要输出QQQ行，每行为000或者111，表示这个矩阵是否出现过，000表示没有出现过，111表示出现过。
输入输出样例 #1
输入 #1
3 3 2 2 111 000 111 3 11 00 11 11 00 11输出 #1
1 0 1说明/提示
对于100%100\%100%的实际测试数据，1≤M,N≤10001\leq M,N \leq 10001≤M,N≤1000，Q=1000Q = 1000Q=1000。
对于40%40\%40%的数据，A=1A = 1A=1。
对于80%80\%80%的数据，A≤10A \leq 10A≤10。
对于100%100\%100%的数据，A≤100A \leq 100A≤100，B≤500B \leq 500B≤500。
C++实现
#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongULL;constintP1=10003,P2=11117,mod=1000007,N=1005;intn,m,T,A,B;chars[N];ULL p1[N],p2[N],h[N][N],num[N*N];intcnt,last[mod],nxt[N*N];intfind(ULL x){intid=x%mod;for(inti=last[id];i;i=nxt[i])if(num[i]==x)returni;return0;}intinsert(ULL x){intid=x%mod;for(inti=last[id];i;i=nxt[i])if(num[i]==x)returni;num[++cnt]=x;nxt[cnt]=last[id];last[id]=cnt;returncnt;}intmain(){cin>>n>>m>>A>>B;p1[0]=p2[0]=1;for(inti=1;i<=n;i++)p1[i]=p1[i-1]*P1;for(inti=1;i<=m;i++)p2[i]=p2[i-1]*P2;for(inti=1;i<=n;i++){ULL c=0;scanf("%s",s+1);for(intj=1;j<=m;j++){c=c*P2+s[j];h[i][j]=h[i-1][j]*P1+c;}}for(inti=A;i<=n;i++)for(intj=B;j<=m;j++)insert(h[i][j]-h[i-A][j]*p1[A]-h[i][j-B]*p2[B]+h[i-A][j-B]*p1[A]*p2[B]);cin>>T;while(T--){ULL res=0;for(inti=1;i<=A;i++){scanf("%s",s+1);for(intj=1;j<=B;j++)res+=s[j]*p1[A-i]*p2[B-j];}if(find(res))cout<<1<<endl;elsecout<<0<<endl;}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
