题目链接
https://codeforces.com/problemset/problem/1980/E
题意
共输入\(T\)组测试用例,每组测试用例第一行输入两个整数\(n, m\),分别代表输入的数据的行数和列数,其中\(n * m \leq 2 * 10^5\)。
接下来输入两个\(n\)行\(m\)列的矩阵\(a, b\),对于每个矩阵中的元素\(x_{i,j}\)都是不同的,且满足:\(1 \leq x_{i,j} \leq n * m\)。
你有以下两种可以执行的操作:
- 选择两个不同的行进行交换
- 选择两个不同的列进行交换
你可以执行上述操作任意次,每次只能选择其中一个操作。问:能否通过上述操作将矩阵\(b\)变为矩阵\(a\),若能,输出“yes”,否则,输出“no”。
题解
本质是考察线性代数的相等矩阵的知识。
矩阵相等的条件:
- 两个矩阵为同型矩阵
- 矩阵的元素完全相同
对于条件1,由于矩阵\(a, b\)均为\(n\)行\(m\)列的矩阵,故明显成立
对于条件2,只能使用选择两个不同的行/列进行交换,去尝试使之成立
对于初等行/列变换中的行/列交换,有一个非常重要的性质,就是进行行(列)交换后,行(列)内元素的相对位置不会发生变化。
基于上述性质,假设此时发生一次行交换,此时行内的相对顺序是不变的,只是每一列元素的相对位置会发生改变,但是发生改变的仅仅是列内元素的相对位置,原本处于同一列的元素依然会处于同一列。
再假设此时发生一次列交换,此时列内的相对顺序是不变的,只是每一行元素的相对位置会发生改变,但是发生改变的仅仅只是行内元素的相对位置,原本处于同一行的元素依然会处于同一行。
基于上述结论,我们只需要判断出矩阵\(a, b\)的每一行、列各自组成的集合,能否在某个顺序下完全相同即可。若能,则输出“YES”,否则,输出“NO”。
在编码实现上,有个问题就是若直接开一个2e5 * 2e5的矩阵,复杂度必然是不可接受的。
观察题目,已知\(n * m \leq 2e5\),那么不妨直接进行矩阵压缩,将二维矩阵压缩为一维,下面讲解如何将二维矩阵压缩为一维数组:
下图是将\(n\)行\(m\)列的二维矩阵映射成长度为\(n * m\)的一维数组:
观察上图,易知原二维矩阵中,处于同一列的元素,在一维数组中是偏移了长度为\(m\)的长度。在二维矩阵中原本同处于第\(i(1 \leq i \leq n)\)行的元素,在一维数组中是从第\((i - 1) * m + 1\)到第\(i * m\)个元素。
因此,若想在一维数组中遍历二维矩阵的每一行,可以用如下代码:
for (int i = 0; i < n; ++ i) {//共n行
for (int j = 0; j < m; ++ j) {//共m列
//i * m + j
}
}
若想在一维数组中遍历二维矩阵的每一列,可以用如下代码:
for (int i = 0; i < m; ++ i) {//共m列
for (int j = 0; j < n; ++ j) {//共n行
//j * m + i
}
}
参考代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
constexpr int N = 2e5 + 7;
int T, n, m;
int a[N], b[N], row[N], col[N];
void solve() {
cin >> n >> m;
for (int i = 0; i < n * m; ++ i) {
cin >> a[i];
row[a[i]] = i / m;
col[a[i]] = i % m;
}
for (int i = 0; i < n * m; ++ i) cin >> b[i];
if (n == 1 || m == 1) {//行或列等于1时必相等
cout << "YES\n";
return ;
}
//求同行
for (int i = 0; i < n; ++ i) {
int r = row[b[i * m]];
for (int j = 1; j < m; ++ j) {
if (row[b[i * m + j]] != r) {
cout << "NO\n";
return ;
}
}
}
//求同列
for (int i = 0; i < m; ++ i) {
int c = col[b[i]];
for (int j = 1; j < n; ++ j) {
if (col[b[j * m + i]] != c) {
cout << "NO\n";
return ;
}
}
}
cout << "YES\n";
}
int main() {
IOS
cin >> T;
while (T --) {
solve();
}
return 0;
}
标签:Rows,leq,int,元素,矩阵,codeforces,++,一维,Columns
From: https://www.cnblogs.com/RomanLin/p/18289101