分数: 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}.
- If X_i is
- 接下来,对于每个 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}.
- If Y_j is
判断是否可以选择 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