← 返回题目列表

AtCoder · arc199_a

A. 翻转行或列 2

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

分数: 800 点

问题陈述

您将获得 N\times N 矩阵 A=(A_{i,j})\ (1\leq i,j\leq N) 和长度的整数序列 N: R=(R_1,R_2,\ldots,R_N), C=(C_1,C_2,\ldots,C_N)。的每个元素 A is 0 or 1,以及每个元素 R,C 至少 0 且小于 \frac{N}{4}.

您可以自由选择一对琴弦 X,Y 长度 N 组成 0 和 1。基于所选的字符串 X,Y,执行以下操作:

  • 首先,对于每个 i=1,2,\ldots,N,执行以下操作。让 X_i 是 i- 第一个字符 X:
    • If X_i is 0,什么也不做。
    • If X_i is 1,翻转所有元素 i-第行 A。也就是说,对于每个 j=1,2,\ldots,N,替换 A_{i,j} 与 1-A_{i,j}.
  • 接下来,对于每个 j=1,2,\ldots,N,执行以下操作。让 Y_j 是 j- 第一个字符 Y:
    • If Y_j is 0,什么也不做。
    • If Y_j is 1,翻转所有元素 j第 列 A。也就是说,对于每个 i=1,2,\ldots,N,替换 A_{i,j} 与 1-A_{i,j}.

判断是否可以选择 X,Y 巧妙地让矩阵 A 运算后满足以下条件,如果可能,输出这样的一对。

  • 对于每个 i=1,2,\ldots,N,中的元素之和 i-第行 A, \displaystyle \sum_{j=1}^N A_{i,j}是 R_i.
  • 对于每个 j=1,2,\ldots,N,中的元素之和 j第 列 A, \displaystyle \sum_{i=1}^N A_{i,j}是 C_j.

你被给予 T 测试用例,因此回答每个用例。

约束

  • 1\leq T\leq 10^5
  • 1\leq N\leq 1000
  • A_{i,j} \in\lbrace 0,1\rbrace
  • 0\leq R_i,C_j\lt \frac{N}{4}
  • T,N,R_i,C_j 是整数。
  • 总和 N^2 一个输入文件中的所有测试用例最多 10^6.

输入

输入由标准输入按以下格式给出:

T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T

每个测试用例均按以下格式给出:

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
R_1 R_2 \ldots R_N
C_1 C_2 \ldots C_N

输出

输出您的解决方案 \textrm{case}_1,\textrm{case}_2,\ldots,\textrm{case}_T 按以下格式顺序排列:

如果没有配对 X,Y 满足条件,输出 No.

如果存在这样一个对,则输出:

Yes
X
Y

如果有多个解决方案,则其中任何一个都将被视为正确。


示例输入 1

3
2
10
01
0 0
0 0
5
10101
11110
01111
10011
00110
1 1 1 1 1
1 1 1 1 1
10
0001011010
0101101000
0000101111
0010011100
0111000001
0011100110
1110001110
1100110000
0110111011
1101101101
1 1 0 2 0 0 2 2 2 2
2 2 0 1 0 2 1 2 1 1

示例输出 1

Yes
01
10
Yes
01101
10001
No

对于第一个测试用例, A=\begin{pmatrix}1&0 \\ 0&1\end{pmatrix}。考虑以下情况 分别为 X,Y 是 01 和 10。操作执行如下:

  • X_1 is 0,所以什么也不做。
  • X_2 is 1,因此翻转 2第 2 行 A,导致 A=\begin{pmatrix}1&0 \\ 1&0\end{pmatrix}.
  • Y_1 is 1,因此翻转 1st 列 A,导致 A=\begin{pmatrix}0&0 \\ 0&0\end{pmatrix}.
  • Y_2 is 0,所以什么也不做。

因此,矩阵 A 操作后是 A=\begin{pmatrix}0&0 \\ 0&0\end{pmatrix}。中元素的总和 1st 行,中元素的总和 2第 行,元素的总和 1st 列,以及 2第nd列全部 0,因此满足条件。

输出也是正确的:

Yes
10
01