← 返回题目列表

Codeforces · 1982/D

D. 山之美

中文机器翻译题面 查看原题

Nikita 热爱山脉,终于决定去参观 Berlyand 山脉!这个山脉是如此美丽,尼基塔决定在地图上捕捉它。该地图是一个由 $$$n$$$ 行和 $$$m$$$ 列组成的表格,每个单元格包含一个表示山的高度的非负整数。

他还注意到山脉有两种类型:

- 带有雪帽。
- 没有雪帽。

Nikita 是一个非常务实的人。他希望有雪冠的山脉的高度总和等于没有雪冠的山脉的高度总和。他已与别尔扬德市市长波利卡尔普·波利卡尔波维奇 (Polikarp Polikarpovich) 达成协议,允许他改造当地的景观。

Nikita 可以对大小为 $$$k \times k$$$ 的子矩阵执行如下变换:他可以将整数常量 $$$c$$$ 添加到该区域内的山脉高度,但山脉的类型保持不变。 Nikita 可以为每个变换独立选择常数 $$$c$$$。请注意,$$$c$$$ 可以为负数。

在进行转换之前,Nikita 要求您弄清楚是否有可能实现总和相等,或者是否不可能。即使山脉变成峡谷并且高度为负,付出什么代价也没关系。

如果地图上只显示一种类型的山,则另一种类型山的高度总和被视为零。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含三个整数 $$$n, m, k$$$ ($$$1 \le n, m \le 500, 1 \le k \le min(n, m)$$$)。

每个测试用例接下来的 $$$n$$$ 行包含 $$$m$$$ 整数 $$$a_{i j}$$$ ($$$0 \le a_{i j} \le 10^{9}$$$) — 山脉的初始高度。

每个测试用例的下一个 $$$n$$$ 长度为 $$$m$$$ 的二进制字符串确定山的类型,'$$$0$$$' - 有雪帽,'$$$1$$$' - 没有雪帽。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$250\,000$$$。

输出

对于每个测试用例,如果可以使山的高度总和相等,则输出不带引号的“YES”,否则输出不带引号的“NO”。您可以在任何情况下输出每个字母(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

8
3 3 2
7 11 3
4 2 3
0 1 15
100
010
000
4 4 3
123 413 24 233
123 42 0 216
22 1 1 53
427 763 22 6
0101
1111
1010
0101
3 3 2
2 1 1
1 1 2
1 5 4
010
101
010
3 3 2
2 1 1
1 1 2
1 5 3
010
101
010
3 4 3
46 49 50 1
19 30 23 12
30 25 1 46
1000
0100
0010
5 4 4
39 30 0 17
22 42 30 13
10 44 46 35
12 19 9 39
21 0 45 40
1000
1111
0011
0111
1100
2 2 2
3 4
6 7
00
00
2 2 2
0 0
2 0
01
00

输出 #1

YES
NO
YES
NO
YES
NO
YES
YES

注意

第一个测试用例中的山数组如下所示:

最初,有雪盖的山脉的高度总和为 $$$11 + 3 + 4 + 3 + 0 + 1 + 15 = 37$$$,没有雪盖的山峰高度总和为 $$$7 + 2 = 9$$$。

为了使这些总和相等,我们可以执行两个转换:

第一次转变:

请注意,常数 $$$c$$$ 可以为负数。

第一次改造后,山阵是这样的:

第二次转变:

结果,山阵看起来像这样:

有雪盖的山脉的高度总和是 $$$17 + 9 + 9 - 16 - 20 - 19 + 15 = -5$$$,没有雪盖的山的高度总和是 $$$7 - 12 = -5$$$,因此答案是 YES。