问题2988--照片(photos)

2988: 照片(photos)

时间限制: 2 Sec  内存限制: 512 MB
提交: 1  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

小R有一些黑白照片。一张照片可以表示成h*w个像素点,其中h是照片的高度,w是照片的宽度,我们将h*w称为该照片的尺寸。在每个像素点上有两种像素值,分别是0(表示黑色)和1(表示白色),也就是说,一张照片可以被表示成h*w的01矩阵。
两张尺寸相同的照片是可以相互比较的。定义两张尺寸相同的照片的相似度S(A,B)=∑_(i,j)▒〖[A(i,j)=B(i,j)]〗,即对应位置上像素值相同的数量。
现在小R想要比较两张不同尺寸的照片,他首先将这两张照片放大。放大一张尺寸为h*w照片时,必须将它的高度放大到原来的整数倍(假设为a倍),将它的宽度也放大到原来的整数倍(假设为b倍),则放大后的照片的尺寸为ah*bw(a≥1,b≥1),且若原来照片的像素为A(i,j),放大后的照片为B(i,j),满足B(i,j)=A( i/a,j/b)(除法均取下整),即原图片中的每一个像素点都对应到新图片上的一个a*b的矩形上。
小R对比尺寸分别为h1*w1和h2*w2的图片时,会将他们都放大到lcm(h1,h2)*lcm(w1,w2)(lcm表示最小公倍数),然后比较放大后的图片。你需要输出它们的相似度。

输入

第一行一个正整数T,表示数据组数。接下来是T组数据。
每组数据的第一行包含两个正整数h1,w1,表示第一张照片的高度和宽度。
第二行包含一个长度为h1*w1的01串,字符串的第(i-1)*w1+j个字符表示第一张图片中位置在(i,j)的像素值。
第三行包含两个正整数h2,w2,表示第二张照片的高度和宽度。
第四行包含一个长度为h2*w2的01串,字符串的第(i-1)*w2+j个字符表示第二张图片中位置在(i,j)的像素值。

输出

对于每组数据,输出一行答案,表示放大后的两张图片的相似度。

样例输入 Copy

2
1 2
01
2 1
01
2 2
0111
3 3
000000001

样例输出 Copy

2
13

提示

对于20%的数据,h1,w1,h2,w2≤20
对于50%的数据,h1,w1,h2,w2≤1000
对于另外30%的数据,h1=h2
对于100%的数据,T≤10,h1*w1≤〖10〗^6,h2*w2≤〖10〗^6

来源/分类