E题题解
题干
问题描述
你得到一个大小为 n x m 的矩阵 a，其中包含从 1 到 n * m 的整数排列。
一个长度为 n 的整数排列是一个数组，其中包含从 1 到 n 的所有整数各一次。例如，数组 [1]、[2, 1, 3]、[5, 4, 3, 2, 1] 是排列，而数组 [1, 1]、[100]、[1, 2, 4, 5] 不是排列。
如果一个矩阵的所有元素都被写出后，得到的数组是一个排列，那么这个矩阵就包含一个排列。例如，矩阵 [[1, 2], [3, 4]]、[[1]]、[[1, 5, 3], [2, 6, 4]] 包含排列，而矩阵 [[2]]、[[1, 1], [2, 2]]、[[1, 2], [100, 200]] 不包含排列。
你可以在一次操作中执行以下两个操作之一：
- 选择列
c和d（1 ≤ c, d ≤ m, c ≠ d）并交换这些列； - 选择行
c和d（1 ≤ c, d ≤ n, c ≠ d）并交换这些行。
你可以执行任意数量的操作。
你得到原始矩阵 a 和目标矩阵 b。你的任务是确定是否可以通过给定的运算将矩阵 a 变换为矩阵 b。
输入
第一行包含一个整数 t（1 ≤ t ≤ 10^4）——测试用例的数量。每个测试用例包含以下内容：
- 第一行包含两个整数
n和m（1 ≤ n, m ≤ n m ≤ 2 10^5）——矩阵的大小。 - 接下来的
n行每行包含m个整数a_ij（1 ≤ a_ij ≤ n * m）。保证矩阵a是一个排列。 - 接下来的
n行每行包含m个整数b_ij（1 ≤ b_ij ≤ n * m）。保证矩阵b是一个排列。
保证所有测试用例的值 n * m 之和不超过 2 * 10^5。
输出
对于每个测试用例，如果可以通过给定的运算将矩阵 a 变换为矩阵 b，则输出 "YES"，否则输出 "NO"。你可以以任何大小写（小写或大写）输出每个字母。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 都将被接受为肯定答案。
示例
输入
7
1 1
1
1
2 2
1 2
3 4
4 3
2 1
2 2
1 2
3 4
4 3
1 2
3 4
1 5 9 6
12 10 4 8
7 11 3 2
1 5 9 6
12 10 4 8
7 11 3 2
3 3
1 5 9
6 4 2
3 8 7
9 5 1
2 4 6
7 8 3
2 3
1 2 6
5 4 3
6 1 2
3 4 5
1 5
5 1 2 3 4
4 2 5 1 3输出
YES
YES
NO
YES
YES
NO
YESAC代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define mod
#define N 100010
void solve()
{
int n , m;
map<int,pair<int,int> > ma;
cin>>n>>m;
vector<set<int> > row(n+5);
vector<set<int> > col(m+5);
for(int i = 1 ; i <= n; i++)
{
for(int j = 1 ; j <= m ; j++)
{
int x;
cin>>x;
ma[x] = {i,j}; //每个值的行列均储存 为了后续插入使用
}
}
bool ans = true;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
int x;
cin>>x;
row[i].insert(ma[x].first); // 当前行 即i行的是由 A矩阵 ma[x].first 转移得来
if(row[i].size() > 1) // 如果条件成立则说明 第I行 由A矩阵不同的两行得到 错误
ans = false;
col[j].insert(ma[x].second);
if(col[j].size() > 1)
ans = false;
}
}
if(ans)
cout<<"YES\n";
else
cout<<"NO\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _= 1;
cin>>_;
while(_--)
{
solve();
}
return 0 ;
}思路
无论经过什么样的行交换和列交换
同一行（列）中的数字的值始终相同 只是排列顺序不同
（在同一行中的数始终在同一行）
因此
若条件成立则需要满足 B矩阵中同一行的所有数都由 A矩阵中的同一行得来
如果不是同一行得来那么B矩阵不能由A矩阵变化得到