目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

1980E - Permutation of Rows and Columns

---

二、解题报告

1、思路分析

我们发现：

交换行：不会破坏任何一列集合

交换列：不会破坏任何一行集合

被交换的行列本身的集合也不会破坏

那么我们发现 a 能变成 b 当且仅当 a 中 任意元素 x 所在行列的集合 和 b 中元素所在行列的集合相同

我们记录 a、b中元素的行号列号rowa[] cola[] rowb[] colb[]，然后 建立 str[], stc[]

str[rowa[x]] 为 所有 rowb[x] 的集合

str[cola[x]] 为 所有 colb[x] 的集合

显然，如果合法，那么 每个 str[i] stc[i] 的 size  都不大于1

直接模拟即可

2、复杂度

时间复杂度： O(NM logn(N + M))空间复杂度：O(NM)

3、代码详解

 ​

#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;constexpr int N = 1E6;void solve() {int n, m;std::cin >> n >> m;std::vector<std::vector<int>> a(n, std::vector<int>(m)), b(a);std::vector<int> rowa(n * m), cola(n * m), rowb(n * m), colb(n * m);for (int i = 0; i < n; ++ i) {for (int j = 0; j < m; ++ j) {std::cin >> a[i][j];-- a[i][j];std::tie(rowa[a[i][j]], cola[a[i][j]]) = std::pair(i, j);}}for (int i = 0; i < n; ++ i) {for (int j = 0; j < m; ++ j) {std::cin >> b[i][j];-- b[i][j];std::tie(rowb[b[i][j]], colb[b[i][j]]) = std::pair(i, j);}}std::vector<std::set<int>> str(std::max(n, m)), stc(std::max(n, m));for (int i = 0; i < n * m; ++ i) {int ra = rowa[i], rb = rowb[i];int ca = cola[i], cb = colb[i];str[ra].insert(rb);stc[ca].insert(cb);if (str[ra].size() > 1 || stc[ca].size() > 1) {std::cout << "NO\n";return;}}std::cout << "YES\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint cur = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;std::cin >> t;while (t--) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - cur << '\n';
#endifreturn 0;
}