F. Unusual Matrix - 题解

比赛与标签

比赛: Codeforces Round 697 (Div. 3) 标签: 2-sat, brute force, constructive algorithms, *1900 难度: *1900

题目大意是什么喵？

简单来说，我们有两个 N x N 大小的 01 矩阵，分别叫做 a 和 b 呐。我们可以对矩阵 a 进行两种操作，而且次数不限：

1. 竖直异或: 挑一列 j，把这一整列的所有元素都和 1 做异或操作（也就是 0 变 1，1 变 0）。
2. 水平异或: 挑一行 i，把这一整行的所有元素都和 1 做异或操作。

我们的任务就是判断，通过这些操作，能不能把矩阵 a 变得和矩阵 b 一模一样。如果可以，就输出 "YES"，不然就输出 "NO"，的说。

解题思路大揭秘！

嘿嘿，这个问题看起来有点复杂，但只要我们把它转换成数学语言，就会变得非常清晰哦，喵~！

1. 用变量来表示操作

让我们来定义一些小小的变量来代表我们的操作吧！

• 设 r_i 是一个 0 或 1 的变量。如果 r_i = 1，就表示我们对第 i 行进行了一次“水平异或”；如果 r_i = 0，就表示我们没动这一行。
• 同样地，设 c_j 也是一个 0 或 1 的变量。如果 c_j = 1，表示我们对第 j 列进行了一次“竖直异或”；如果 c_j = 0，就表示没动这一列。

为啥是 0 或 1 呢？因为异或两次等于没操作嘛 (x ⊕ 1 ⊕ 1 = x)，所以对同一行或同一列操作偶数次都没用，奇数次等于操作一次。所以我们只需要关心“操作”还是“不操作”就够了。

2. 列出魔法方程式

现在，考虑矩阵 a 中的任意一个元素 a[i][j]。在经过我们的一系列操作后，它的新值 a'[i][j] 会是多少呢？ 它会受到第 i 行操作和第 j 列操作的影响。所以，新值就是： a'[i][j] = a[i][j] ⊕ r_i ⊕ c_j

我们的目标是让 a 变成 b，也就是说，对于所有的 i 和 j，都要满足： a'[i][j] = b[i][j]

把上面的式子代入，我们就得到了一个关键的等式： a[i][j] ⊕ r_i ⊕ c_j = b[i][j]

为了让这个式子更漂亮一点，我们把 a[i][j] 移到右边去（两边同时异或 a[i][j]）： r_i ⊕ c_j = a[i][j] ⊕ b[i][j]

这个等式就是我们解题的核心啦！它告诉我们，第 i 行和第 j 列的操作选择，必须等于 a[i][j] 和 b[i][j] 的差异。

3. 发现隐藏的约束条件

让我们来定义一个新的差异矩阵 d，其中 d[i][j] = a[i][j] ⊕ b[i][j]。我们的条件就变成了： r_i ⊕ c_j = d[i][j]

这个条件必须对所有 i 和 j 都成立。现在，让我们来玩一个“找不同”的游戏，喵~ 随便选两行，比如说第 i 行和第 k 行，再随便选一列 j。根据我们的魔法方程式：

• 对于 (i, j) 位置：r_i ⊕ c_j = d[i][j]
• 对于 (k, j) 位置：r_k ⊕ c_j = d[k][j]

把这两个等式再异或一下会发生什么？ (r_i ⊕ c_j) ⊕ (r_k ⊕ c_j) = d[i][j] ⊕ d[k][j]

左边的 c_j 和 c_j 异或就消失啦！得到： r_i ⊕ r_k = d[i][j] ⊕ d[k][j]

4. 最终的判断方法！

看这个最终的式子！r_i ⊕ r_k 的值只和我们选择的行 i 和行 k 有关，对于任何一列 j，它的值都是固定的！ 这意味着，右边的 d[i][j] ⊕ d[k][j] 对于所有的 j (1 <= j <= n)，也必须是同一个常量！

这是什么意思呢？ d[i][j] ⊕ d[k][j] 是个常量，意味着 d 矩阵的第 i 行和第 k 行的“异或差异”是一致的。换句话说，d 矩阵的第 i 行，要么和第 k 行完全相同（此时差异全为0），要么就是第 k 行的完全反转（此时差异全为1）。

所以，我们的算法就出来啦：

1. 计算出差异矩阵 d（虽然我们不需要真的存下来）。
2. 以第 0 行为基准。
3. 对于其他每一行 i（从 1 到 n-1），检查它和第 0 行的关系。它们要么完全相同，要么完全相反。
4. 怎么检查呢？对于一行 i，我们先看它和第 0 行在第 0 列的差异：d[i][0] ⊕ d[0][0]。
5. 然后，我们检查这一行 i 在其他所有列 j 上与第 0 行的差异 d[i][j] ⊕ d[0][j] 是否都和第一个差异相同。
6. 如果所有行都满足这个条件，那么就一定存在一种操作方案，输出 "YES"。
7. 只要有一行不满足，那就说明无论如何也变不成 b 矩阵，输出 "NO"。

这个方法是不是很巧妙呀？我们通过分析约束，找到了一个非常简单的判断方法，喵~

代码实现喵~

#include <iostream>
#include <vector>
#include <string>

void solve() {
    int n;
    std::cin >> n;
    std::vector<std::string> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    // 假设 r_i 为1表示翻转第i行，为0表示不翻转。
    // 假设 c_j 为1表示翻转第j列，为0表示不翻转。
    // 最终 (i, j) 位置的值为 a[i][j] ^ r_i ^ c_j。
    // 我们希望它等于 b[i][j]，所以 a[i][j] ^ r_i ^ c_j = b[i][j]。
    // 整理一下得到：r_i ^ c_j = a[i][j] ^ b[i][j]。
    // 设 d[i][j] = a[i][j] ^ b[i][j]，那么条件就是 r_i ^ c_j = d[i][j]。

    // 从这个条件出发，对于任意两行 i 和 k，以及任意一列 j：
    // r_i ^ c_j = d[i][j]
    // r_k ^ c_j = d[k][j]
    // 将这两个等式异或，c_j 就消掉了：
    // (r_i ^ c_j) ^ (r_k ^ c_j) = d[i][j] ^ d[k][j]
    // 得到 r_i ^ r_k = d[i][j] ^ d[k][j]。

    // 左边的 r_i ^ r_k 是一个只和行 i, k 有关的常量。
    // 所以右边的 d[i][j] ^ d[k][j] 对于所有列 j 也必须是同一个常量。
    // 这意味着，对于任意两行 i 和 k，d 矩阵的第 i 行要么和第 k 行完全相同，要么是它的按位取反。

    // 我们可以通过检查每一行与第一行（第0行）的关系来验证这个性质。
    bool possible = true;
    for (int i = 1; i < n; ++i) {
        // 我们检查第 i 行和第 0 行的异或差异是否对所有列都一致。
        // `d[i][j] ^ d[0][j]` 对于所有 j 都应该是同一个值。
        
        // 首先，用第一列(j=0)计算出这个预期的差异模式。
        // d[i][0] = (a[i][0] - '0') ^ (b[i][0] - '0')
        // d[0][0] = (a[0][0] - '0') ^ (b[0][0] - '0')
        int diff_pattern = ((a[i][0] - '0') ^ (b[i][0] - '0')) ^ ((a[0][0] - '0') ^ (b[0][0] - '0'));
        
        // 然后，验证这个差异模式在其他所有列中是否成立。
        for (int j = 1; j < n; ++j) {
            int current_diff = ((a[i][j] - '0') ^ (b[i][j] - '0')) ^ ((a[0][j] - '0') ^ (b[0][j] - '0'));
            if (current_diff != diff_pattern) {
                possible = false;
                break;
            }
        }
        if (!possible) {
            break;
        }
    }

    if (possible) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    // 加速输入输出，让程序跑得更快喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(N^2) 的说。对于每个测试用例，我们需要读取两个 N x N 的矩阵，这需要 O(N^2) 的时间。之后，我们有一个外层循环 i 从 1 到 n-1，一个内层循环 j 从 1 到 n-1。所以检查过程也是 O(N^2) 的。总的来说就是 O(N^2) 啦！
• 空间复杂度: O(N^2) 的说。我们需要用 std::vector<std::string> 来存储两个 N x N 的矩阵，这占用了 O(N^2) 的空间。没有使用其他大的辅助空间，所以这就是主要的空间开销。

知识点与总结喵~

这道题真是一次有趣的逻辑推理之旅呢！让本喵来总结一下吧：

1. 模型转换: 解决这类问题的关键一步，是把具体的操作（翻转行/列）转换成代数表达式（r_i, c_j 和异或方程）。这能帮助我们看清问题的本质。
2. 约束推导: 从建立的方程 r_i ⊕ c_j = d[i][j] 出发，通过巧妙地组合和消除变量（比如消去c_j），我们推导出了一个非常强的约束条件。这个过程是解题的灵魂所在！
3. 抓住不变量: 我们发现 r_i ⊕ r_k 是一个不变量（对于所有列 j），这使得我们能锁定 d 矩阵行与行之间的关系。在算法问题中，寻找不变量常常是通往正确解法的捷径哦。
4. 化繁为简: 最初可能觉得需要搜索或者用什么复杂的数据结构，但最后我们发现，只需要一个简单的 O(N^2) 检查就足够了。这告诉我们，遇到问题不要马上想着用复杂的工具，先深入分析问题本身的性质，说不定有更简单的路可走！

希望这篇题解能帮助到大家！只要多思考，多练习，再难的题目也能被我们攻克的说！加油喵~！