Codeforces 1136C - Nastya Is Transposing Matrices

时间:2021-06-26 15:52:36

题目链接:https://codeforces.com/problemset/problem/1136/C

题意:

给出 $n \times m$ 的矩阵 $A,B$,你可以对其中任意某个 $k \times k$ 的子矩阵进行转置操作。

问你是否能将 $A$ 变成 $B$。

题解:

不管我们如何进行转置,不难发现整个矩阵的任意一条反对角线上的元素构成的集合,都是不会变的。

而我们可以进一步得出结论,对于 $A,B$ 两个矩阵,只要满足任意一条反对角线上的它们的元素构成的集合相同,就能从 $A$ 变成 $B$。

这也很好证明,因为只要我每次都选取 $2 \times 2$ 的子矩阵进行转置,必然能将任意一条反对角线上的任意两个相邻的元素交换位置,而只要能随意交换相邻元素,任意一个序列就可以变成任意的另一个序列。

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int K=;
int n,m;
vector<int> a[*K],b[*K];
int main()
{
ios::sync_with_stdio();
cin.tie(), cout.tie(); cin>>n>>m;
for(int i=,x;i<=n;i++) for(int j=;j<=m;j++) cin>>x, a[i+j].push_back(x);
for(int i=,x;i<=n;i++) for(int j=;j<=m;j++) cin>>x, b[i+j].push_back(x); bool ok=;
for(int k=;k<=n+m;k++)
{
sort(a[k].begin(),a[k].end());
sort(b[k].begin(),b[k].end());
for(int i=;i<a[k].size();i++) if(a[k][i]!=b[k][i]) ok=;
}
cout<<(ok?"YES":"NO")<<'\n';
}