周村区住房和城乡建设厅网站,专业做二手房的网站有哪些,加强网站安全建设,石家庄网站设计制作题目链接 文章目录题目描述题意#xff1a;题解代码#xff1a;时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K
64bit IO Format: %lld题目描述 给定一个M行N列的01矩阵#xff08;只包含数字0或1的矩阵题解代码时间限制C/C 1秒其他语言2秒
空间限制C/C 32768K其他语言65536K
64bit IO Format: %lld题目描述 给定一个M行N列的01矩阵只包含数字0或1的矩阵再执行Q次询问每次询问给出一个A行B列的01矩阵求该矩阵是否在原矩阵中出现过。 输入描述: 第一行四个整数M,N,A,B。 接下来一个M行N列的01矩阵数字之间没有空格。 接下来一个整数Q。 接下来Q个A行B列的01矩阵数字之间没有空格。 输出描述: 对于每个询问输出1表示出现过0表示没有。 示例1 输入
3 3 2 2
111
000
111
3
11
00
11
11
00
11输出
1
0
1备注: 对于40%的数据A 1。 对于80%的数据A≤10。 对于100%的数据A≤100M,N≤1000Q≤1000。
题意
给你个MN的二维矩阵然后给你个AB的二维矩阵问后者是否在前者出现过
题解
毫无疑问用hash 我们先想一个问题 一个长为L的字符串a问长度为lenlenL的字符串b在a中出现过吗 这个怎么做 我们可以将a中长度为len的部分求出hash并放进哈希表然后求出b的hash进行比较即可
其实本题就是将一维问题转化成二维 我们将n * m的矩形中所有大小为a * b的矩形哈希一下并放到哈希表中然后给出矩阵后直接O1查找就可以了 求矩阵的hash的步骤 先求出每一行前缀的hash然后固定矩阵的一边长度b求出长度为b的边的hash值然后从这一行向下延伸a行求出这a行对应的长度为b的hash值。当长度大于a后就将最上面一行删去始终保持为 a * b 的矩阵。
代码
#include bits/stdc.h
using namespace std;
const int maxn1005;
typedef unsigned long long ull;
ull hash1[maxn][maxn];
ull base[maxn*maxn];
int base113;
char c[maxn];
ull get(ull hash1[],int l,int r)
{return hash1[r]-hash1[l-1]*base[r-l1];
}
int q;
int n,m,a,b;
int main(){cinnmab;base[0]1;for(int i1;in*m;i) base[i]base[i-1]*base1;//素数倍数用于查询子串哈希值 for(int i1;in;i){scanf(%s,c1);for(int j1;jm;j) hash1[i][j]hash1[i][j-1]*base1c[j]-0;//求取每一行前缀哈希值 }unordered_setull s;for(int ib;im;i){ull x0;int li-b1,ri;for(int j1;jn;j){xx*base[b]get(hash1[j],l,r);// 加上当前行的hash值 if(ja) x-get(hash1[j-a],l,r)*base[a*b];// 如果超行了删去最上面一行 if(ja){s.insert(x);//用map来存哈希值方便后面的判断是否存在 }}}cinq;while(q--){ull x0;for(int i0;ia;i){scanf(%s,c);for(int j0;jb;j){xx*base1c[j]-0;//将所给的矩阵转化成hash }}if(s.count(x))//利用map性质查询是否有这个数 cout1endl;else cout0endl;}return 0;
}不过这样做好像超内存了。。。 可以手写map会好些
