自动搬运

查看原文

来自洛谷，原作者为

	lam_dyr 少年曾许凌云志，誓做天下第一流

搬运于2025-08-24 23:08:15，当前版本为作者最后更新于2025-01-10 16:08:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

刚看到本题，二分图？？我不会啊。但仔细读了一遍题，这不是水题吗。

题意

给定两个 $01$ 矩阵 $A$ 和 $B$，判断是否可以通过以下两种操作将 $A$ 转换为 $B$：

• 行翻转：选择 $A$ 的一行，将 $0$ 变为 $1$，$1$ 变为 $0$。
• 列翻转：选择 $A$ 的一列，将 $0$ 变为 $1$，$1$ 变为 $0$。

思路

由于异或运算的特性：

• 相同的值异或结果为 $0$。
• 不同的值异或结果为 $1$。

考虑将矩阵 $B$ 的元素与矩阵 $A$ 的对应元素进行异或运算 A[i][j] ^= B[i][j]，操作后问题转化为判断是否可以通过行列翻转将矩阵 $A$ 的所有元素变为 $0$。

如果 A[i][j] 异或后为 $0$，则表示原 $A$ 和 $B$ 对应位置相同，否则表示不同。

进一步简化，假设第一行不进行翻转操作，那么，其他行和列的翻转操作就确定了。

如果第一行需要翻转，那么其他行和列的翻转操作也会相应改变。

因此，我们只需要考虑第一行是否翻转两种情况，而不需要枚举所有行的翻转情况。

注意到以下性质：

• 如果可以通过行列翻转将 $A$ 转换为 $B$，那么对于矩阵 $A$ 中任意一行，它要么与第一行完全相同，要么与第一行完全相反。
• 换句话说，每一行要么和第一行所有元素都相同，要么所有元素都相反（$0$ 变 $1$，$1$ 变 $0$）。

经过上述分析，我们不需要真正去模拟，就能得到最终的判定结果。

Code

#include <iostream>
using namespace std;
int a[1005][1005];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int n, m; // n: 行数, m: 列数
    cin >> n >> m;
    // a: 存储矩阵 A
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) 
            cin >> a[i][j];
    }
    // 读取矩阵 B，并与矩阵 A 进行异或操作
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int b; // b: 临时变量，存储矩阵 B 的元素
            cin >> b;
            a[i][j] ^= b;
        }
    }
    // 检查每一行是否与第一行满足条件
    for (int i = 1; i < n; ++i) {
        int k = 0; // k: 记录当前行与第一行相同元素的个数
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == a[0][j]) 
                k++;
        }
        // 如果当前行既不与第一行完全相同，也不与第一行完全相反，则输出 "Budexing"
        if (k != 0 && k != m) {
            cout << "Budexing";
            return 0;
        }
    }
    // 如果所有行都满足条件，则输出 "Koyi"
    cout << "Koyi";
    return 0;
}