CF2043E 题解

__vector__ · 2024-12-27 12:12:28 · 题解

题意

给定大小为 n \times m 的矩阵 A,B，两个矩阵均由不大于 10^9 的非负整数组成。

单次操作可以有以下两种形式：

1. 选择两个数 i,x，满足 1 \le i \le n,x \ge 0。

   对于 1 \le \forall j \le m，将 A_{i,j} 替换为 A_{i,j} 按位与 x，即整行按位与。

2. 选择两个数 j,x，满足 1 \le j \le m,x\ge 0。

   对于 1 \le \forall i \le n，将 A_{i,j} 替换为 A_{i,j} 按位或 x，即整列按位或。

问能否在任意次操作之后将 A 变为 B。

做法

每一位都是独立的，考虑枚举每一位。

问题简化为了，两个 n \times m 的 01 矩阵 A,B，每次可以将 A 的一整行设置为 0，或将 A 的一整列设置为 1，求能否将 A 变为 B。

考虑对于 (i,j)，如果 A_{i,j} \neq B_{i,j}，该如何处理。

不难注意到，每一行，每一列最多执行一次操作。

如果对第 i 行执行了操作，且存在 j 满足 B_{i,j}=1，那么必然需要在此之后对 j 列执行一次操作。

同理，如果对第 j 列执行了操作，存在 i 满足 B_{i,j}=0，那么必然需要在此之后对第 i 列执行一次操作。

由此可以建立一个有向图，x \rightarrow y 代表 x 操作执行完成后必须执行 y 操作。

从每个必须执行的操作出发 dfs，如果找到环，那么必然无解。

如果最终没有找到环，显然是有解的。