喵喵的矩阵魔法 ✨ | E. Permutation of Rows and Columns 题解

哈咯，各位爱算法的小伙伴们，你们好呀！我是你们的猫娘小助手 Mya~ 今天要给大家带来的是一道关于矩阵变换的有趣题目，感觉就像在玩一个大型的拼图游戏呢，喵~ 让我们一起来看看怎么用魔法（和算法）把它解决掉吧！

题目大意

这道题是说，我们有两个大小都是 n x m 的矩阵 a 和 b。这两个矩阵里的数字很特别哦，它们包含了从 1 到 n * m 的所有整数，而且每个数字都只出现一次，就像一个被打乱的大号排列一样。

我们可以对矩阵 a 进行两种操作，而且次数不限：

交换任意两行：比如把第 1 行和第 3 行的所有元素整个换个位置。
交换任意两列：比如把第 2 列和第 5 列的所有元素整个换个位置。

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

解题思路

一看到这种可以“任意”交换行和列的题目，猫娘的直觉就告诉我，我们应该去寻找一些在这些花里胡哨的操作下保持不变的性质，也就是“不变量”。

让我们来分析一下这两种操作会对矩阵产生什么影响吧~

1. 操作的影响

交换列：当我们交换两列时，每一行内部的元素顺序会被打乱。比如，一行是 [1, 2, 6]，交换前两列后就变成了 [2, 1, 6]。但是，请注意！虽然顺序变了，但这一行所包含的元素集合（或者更准确地说是多重集）是不会变的。[1, 2, 6] 和 [2, 1, 6] 都含有 {一个1, 一个2, 一个6}。这个性质对所有行都成立。
交换行：当我们交换两行时，只是把两行整体换了个位置。比如，矩阵有两行 [1, 2] 和 [3, 4]，交换后就变成了 [3, 4] 和 [1, 2]。这改变了行的顺序，但行的集合本身没有变。

2. 发现不变量！

结合起来看，无论我们怎么交换列，每一行内部的元素多重集是固定的。而交换行，只是在对这些“行多重集”进行重新排序。所以，一个非常重要的不变量就出现啦：

不变量一：矩阵 a 所有行的多重集所构成的多重集，和矩阵 b 所有行的多重集所构成的多重集，必须是相同的。

听起来有点绕口，对不对？喵~ 举个例子：如果矩阵 a 是：

1 2
3 4

它的行多重集分别是 {1, 2} 和 {3, 4}。那么由这两个行多重集构成的“多重集的集合”就是 {{1, 2}, {3, 4}}。如果矩阵 b 是：4 31 2它的行多重集分别是 {4, 3} 和 {1, 2}。因为 {4, 3} 和 {3, 4} 是同一个多重集，所以 b 的“多重集的集合”也是 {{1, 2}, {3, 4}}。它们是匹配的！同理，猫爪一挥，我们就能想到一个完全对称的性质：不变量二：矩阵 a 所有列的多重集所构成的多重集，和矩阵 b 所有列的多重集所构成的多重集，也必须是相同的。#### 3. 充分且必要

这两个条件是必要的，那它们是不是充分的呢？也就是说，只要这两个条件都满足，就一定能从 a 变换到 b 吗？

答案是肯定的，喵！因为行和列的操作是独立的，如果行多重集和列多重集都能对上，就意味着 b 只是 a 的一个行和列的置换版本。而题目给的操作正好允许我们进行任意的行置换和列置换。

所以，我们的解题策略就非常清晰啦：

检查 a 和 b 的行多重集集合是否相同。
检查 a 和 b 的列多重集集合是否相同。
如果两个都相同，答案就是 "YES"，否则就是 "NO"。

怎么比较两个“多重集的集合”是否相同呢？一个简单又聪明的办法是：

把每个行/列看作一个多重集，为了方便比较，我们把它们内部的元素排个序，得到一个有序的向量。这就成了这个多重集的唯一表示（也叫范式）。
把所有行/列的这种“有序向量”收集起来，再对这个向量列表进行排序。
最后，比较 a 和 b 经过这样处理后得到的最终列表是否完全一样就可以啦！

代码解说

下面是解题代码的 C++ 实现，猫娘来给你一步步讲解哦~

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> a(n, std::vector<int>(m));
    std::vector<std::vector<int>> b(n, std::vector<int>(m));
    
    // 读入矩阵 a 和 b
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> b[i][j];
        }
    }

    // --- 检查条件一：行多重集集合是否相等 ---
    {
        // a_row_sigs 用来存放 a 的所有“行签名”
        std::vector<std::vector<int>> a_row_sigs;
        a_row_sigs.reserve(n); // 预留空间，小优化喵
        for (int i = 0; i < n; ++i) {
            std::vector<int> row = a[i];
            std::sort(row.begin(), row.end()); // 把行内元素排序，得到行的“签名”
            a_row_sigs.push_back(std::move(row));
        }
        std::sort(a_row_sigs.begin(), a_row_sigs.end()); // 对所有行签名进行排序

        // 对矩阵 b 做同样的操作
        std::vector<std::vector<int>> b_row_sigs;
        b_row_sigs.reserve(n);
        for (int i = 0; i < n; ++i) {
            std::vector<int> row = b[i];
            std::sort(row.begin(), row.end());
            b_row_sigs.push_back(std::move(row));
        }
        std::sort(b_row_sigs.begin(), b_row_sigs.end());

        // 如果最终得到的签名列表不一致，说明无法变换
        if (a_row_sigs != b_row_sigs) {
            std::cout << "NO\n";
            return;
        }
    }

    // --- 检查条件二：列多重集集合是否相等 ---
    {
        // a_col_sigs 用来存放 a 的所有“列签名”
        std::vector<std::vector<int>> a_col_sigs;
        a_col_sigs.reserve(m);
        for (int j = 0; j < m; ++j) {
            std::vector<int> col;
            col.reserve(n);
            // 先把一整列的元素取出来
            for (int i = 0; i < n; ++i) {
                col.push_back(a[i][j]);
            }
            std::sort(col.begin(), col.end()); // 排序，得到列的“签名”
            a_col_sigs.push_back(std::move(col));
        }
        std::sort(a_col_sigs.begin(), a_col_sigs.end()); // 对所有列签名进行排序

        // 对矩阵 b 做同样的操作
        std::vector<std::vector<int>> b_col_sigs;
        b_col_sigs.reserve(m);
        for (int j = 0; j < m; ++j) {
            std::vector<int> col;
            col.reserve(n);
            for (int i = 0; i < n; ++i) {
                col.push_back(b[i][j]);
            }
            std::sort(col.begin(), col.end());
            b_col_sigs.push_back(std::move(col));
        }
        std::sort(b_col_sigs.begin(), b_col_sigs.end());

        // 如果列签名列表不一致，也无法变换
        if (a_col_sigs != b_col_sigs) {
            std::cout << "NO\n";
            return;
        }
    }

    // 如果两个条件都通过了，那就说明可以变换成功！
    std::cout << "YES\n";
}

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

知识点小课堂

这道题背后其实藏着一些很有用的概念呢，让猫娘来给你科普一下吧！

多重集 (Multiset) 和普通的集合（Set）不同，多重集是允许元素重复出现的。比如 {1, 1, 2, 3} 就是一个多重集。在这道题里，我们把每一行或每一列看作一个多重集，因为我们只关心它有哪些元素以及各有多少个，不关心它们的排列顺序。
不变量 (Invariant) 不变量是在一系列变换中保持不变的属性。在算法竞赛中，寻找不变量是一种非常强大的解题思想。当你遇到看起来很复杂、操作很多的问题时，不妨静下心来想一想：“什么东西是永远不会变的？” 找到了不变量，问题往往就迎刃而解啦！
范式/标准型 (Canonical Form) 当我们想比较两个结构是否“本质相同”（比如忽略顺序）时，一个常用的方法是把它们都转换成一个唯一的、标准的形式，这个形式就叫范式。在本题中，我们通过“先对行/列内部排序，再对所有行/列排序”的方式，为矩阵的行/列集合找到了一个范式。这样，复杂的“多重集集合比较”就变成了简单的“有序列表比较”。

好啦，今天的题解就到这里啦！希望猫娘的讲解能帮助你更好地理解这道题目。只要抓住了“不变量”这个小鱼干，再复杂的问题也会变得清晰起来的。大家要继续加油哦，我们下次再见，喵~ (ฅ'ω'ฅ)

喵喵的矩阵魔法 ✨ | E. Permutation of Rows and Columns 题解 ​

题目大意 ​

解题思路 ​

1. 操作的影响 ​

2. 发现不变量！ ​

代码解说 ​

知识点小课堂 ​