首页 > 代码库 > BZOJ2351: [BeiJing2011]Matrix
BZOJ2351: [BeiJing2011]Matrix
2351: [BeiJing2011]Matrix
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 589 Solved: 171
[Submit][Status]
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矩阵。
Output
你需要输出Q行，每行为0或者1，表示这个矩阵是否出现过，0表示没有出现过，1表示出现过。
Sample Input
3 3 2 2
111
000
111
3
11
00
11
11
00
11
111
000
111
3
11
00
11
11
00
11
Sample Output
1
0
1
0
1
HINT
对于100%的实际测试数据，M、N ≤ 1000，Q = 10
对于40%的数据，A = 1。
对于80%的数据，A ≤ 10。
对于100%的数据，A ≤ 100。
题解：
因为大小固定的矩阵最多只有100W个，那么我们可以把所有的矩阵hash出来，然后直接查询即可。
代码的实现参考了PoPoQQQ，很有技巧性。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 1500 26 27 #define maxm 1000000+5 28 29 #define eps 1e-10 30 31 #define ull unsigned long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 999983 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,m,tot,head[maxm],a,b; 61 ull sum[maxn][maxn],power[2][maxn]; 62 struct edge{ull go;int next;}e[maxm]; 63 const ull base[2]={13131,10007}; 64 inline void hash(ull x) 65 { 66 int y=x%mod; 67 e[++tot]=(edge){x,head[y]};head[y]=tot; 68 } 69 inline bool ask(ull x) 70 { 71 for(int i=head[x%mod];i;i=e[i].next)if(e[i].go==x)return 1; 72 return 0; 73 } 74 75 int main() 76 77 { 78 79 freopen("input.txt","r",stdin); 80 81 freopen("output.txt","w",stdout); 82 83 n=read();m=read();a=read();b=read(); 84 for1(i,n)for1(j,m){char ch=getchar();while(ch!=‘0‘&&ch!=‘1‘)ch=getchar();sum[i][j]=ch-‘0‘;} 85 for1(i,n)for1(j,m)sum[i][j]+=sum[i-1][j]*base[0]; 86 for1(i,n)for1(j,m)sum[i][j]+=sum[i][j-1]*base[1]; 87 power[0][0]=power[1][0]=1; 88 for1(i,maxn-1)for0(j,1)power[j][i]=power[j][i-1]*base[j]; 89 for2(i,a,n) 90 for2(j,b,m) 91 hash(sum[i][j]-sum[i-a][j]*power[0][a]-sum[i][j-b]*power[1][b]+sum[i-a][j-b]*power[0][a]*power[1][b]); 92 int q=read(); 93 while(q--) 94 { 95 for1(i,a)for1(j,b){char ch=getchar();while(ch!=‘0‘&&ch!=‘1‘)ch=getchar();sum[i][j]=ch-‘0‘;} 96 for1(i,a)for1(j,b)sum[i][j]+=sum[i-1][j]*base[0]; 97 for1(i,a)for1(j,n)sum[i][j]+=sum[i][j-1]*base[1]; 98 if(ask(sum[a][b]))printf("1\n");else printf("0\n"); 99 }100 101 return 0;102 103 }
BZOJ2351: [BeiJing2011]Matrix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。