4753: Lydsy2351 Matrix
Time Limit: 10 Sec Memory Limit: 128 MB
- Submit: 97 Solved: 33
- [Submit https://begin.lydsy.com/JudgeOnline/submitpage.php?id=4753][Status https://begin.lydsy.com/JudgeOnline/problemstatus.php?id=4753 ][web Board https://begin.lydsy.com/JudgeOnline/bbs.php?pid=4753 ]
- Description
给定一个 M 行 N 列的 01 矩阵, 以及 Q 个 A 行 B 列的 01 矩阵, 你需要求出这 Q 个矩阵哪些在原矩阵中出现过.
所谓 01 矩阵, 就是矩阵中所有元素不是 0 就是 1.
Input
输入文件的第一行为 M,N,A,B, 参见题目描述.
接下来 M 行, 每行 N 个字符, 非 0 即 1, 描述原矩阵.
接下来一行为你要处理的询问数 Q.
接下来 Q 个矩阵, 一共 Q*A 行, 每行 B 个字符, 描述 Q 个 01 矩阵.
A 100
Output
你需要输出 Q 行, 每行为 0 或者 1, 表示这个矩阵是否出现过, 0 表示没有出现过, 1 表示出现过.
- Sample Input
- 3 3 2 2
- 111
- 000
- 111
- 3
- 11
- 00
- 11
- 11
- 00
- 11
- Sample Output
- 1
- 0
- 1
我只能说进阶指南的标程太坑,,,,,, 非但复杂看不懂还是错的,,,, 毒害身心,, 浪费了我两天下午的时间
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<iostream>
- using namespace std;
- const int maxn=1010;
- const int pc=131;
- const int ppc=13331;
- const int mod=10100;
- unsigned int a[maxn][maxn],p1[maxn],p2[maxn],sum[maxn][maxn];
- int fa,adj[mod];
- char b[maxn][maxn];
- struct my{
- unsigned int zhi;
- int next;
- }bian[maxn*maxn+5];
- void Hash(unsigned int u){
- int x=u%mod;
- bian[++fa].zhi=u;
- bian[fa].next=adj[x];
- adj[x]=fa;
- }
- bool ask(unsigned int u){
- int x=u%mod;
- for (int i=adj[x];i;i=bian[i].next){
- if(bian[i].zhi==u) return true;
- }
- return false;
- }
- int main(){
- int n,m,r,c,q;
- cin>>m>>n>>r>>c;
- for (int i=1;i<=m;i++) scanf("%s",b[i]+1);
- cin>>q;
- for (int i=1;i<=m;i++)
- for (int j=1;j<=n;j++)
- sum[i][j]=b[i][j]-'0';
- for (int i=1;i<=m;i++){
- for (int j=1;j<=n;j++){
- sum[i][j]+=sum[i-1][j]*pc;
- }
- }
- for (int i=1;i<=m;i++){
- for (int j=1;j<=n;j++){
- sum[i][j]+=sum[i][j-1]*ppc;
- }
- }
- p1[0]=p2[0]=1;
- for (int i=1;i<=r;i++) p1[i]=p1[i-1]*pc;
- for (int j=1;j<=c;j++) p2[j]=p2[j-1]*ppc;
- for (int i=r;i<=m;i++){
- for (int j=c;j<=n;j++){
unsigned int temp=sum[i][j]-sum[i-r][j]*p1[r]-sum[i][j-c]*p2[c]+sum[i-r][j-c]*p1[r]*p2[c];
- Hash(temp);
- }
- }
- while(q--){
- memset(sum,0,sizeof(sum));
- memset(b,0,sizeof(b));
- for (int i=1;i<=r;i++)
- scanf("%s",b[i]+1);
- for (int i=1;i<=r;i++){
- for (int j=1;j<=c;j++){
- sum[i][j]=b[i][j]-'0';
- }
- }
- for (int i=1;i<=r;i++)
- for (int j=1;j<=c;j++) sum[i][j]+=sum[i-1][j]*pc;
- for (int i=1;i<=r;i++)
- for (int j=1;j<=c;j++) sum[i][j]+=sum[i][j-1]*ppc;
- unsigned int temp=sum[r][c];
- if(ask(temp)) puts("1");
- else puts("0");
- }
- return 0;
- }
- bzoj2351(矩阵哈希)
来源: http://www.bubuko.com/infodetail-2587529.html