Div 2 C. Nastya Is Transposing Matrices（矩阵&思维）
题目来源：http://codeforces.com/problemset/problem/1136/C
C. Nastya Is Transposing Matrices
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Nastya came to her informatics lesson, and her teacher who is, by the way, a little bit famous here gave her the following task.
Two matrices AA and BB are given, each of them has size n×mn×m. Nastya can perform the following operation to matrix AA unlimited number of times:
- take any square square submatrix of AA and transpose it (i.e. the element of the submatrix which was in the ii-th row and jj-th column of the submatrix will be in the jj-th row and ii-th column after transposing, and the transposed submatrix itself will keep its place in the matrix AA).
Nastya's task is to check whether it is possible to transform the matrix AA to the matrix BB.
As it may require a lot of operations, you are asked to answer this question for Nastya.
A square submatrix of matrix MM is a matrix which consist of all elements which comes from one of the rows with indeces x,x+1,…,x+k−1x,x+1,…,x+k−1 of matrix MM and comes from one of the columns with indeces y,y+1,…,y+k−1y,y+1,…,y+k−1 of matrix MM. kk is the size of square submatrix. In other words, square submatrix is the set of elements of source matrix which form a solid square (i.e. without holes).
Input
The first line contains two integers nn and mm separated by space (1≤n,m≤5001≤n,m≤500) — the numbers of rows and columns in AA and BBrespectively.
Each of the next nn lines contains mm integers, the jj-th number in the ii-th of these lines denotes the jj-th element of the ii-th row of the matrix AA (1≤Aij≤1091≤Aij≤109).
Each of the next nn lines contains mm integers, the jj-th number in the ii-th of these lines denotes the jj-th element of the ii-th row of the matrix BB (1≤Bij≤1091≤Bij≤109).
Output
Print "YES" (without quotes) if it is possible to transform AA to BB and "NO" (without quotes) otherwise.
You can print each letter in any case (upper or lower).
Examples
input
Copy
2 2
1 1
6 1
1 6
1 1
output
Copy
YES input
Copy
2 2
4 4
4 5
5 4
4 4
output
Copy
NO input
Copy
3 3
1 2 3
4 5 6
7 8 9
1 4 7
2 5 6
3 8 9
output
Copy
YES
思路：要求对A矩阵（可以是子矩阵）进行转置使得A变成B，由于转置是行列互换，主对角线不变，只要将副对角线排一下序，比较一下就ok了，笔者是用vector写的，感觉用容器代码还要短，给出大佬代码。
参考代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
#define N 505
int A[N][N],B[N][N];
int n,m;
bool Judge(int x,int y)
{
vector<int> xx,yy;
int i=x;
int j=y;
for(; i>=1&&j<=m; i--,j++)
{
xx.push_back(A[i][j]);
yy.push_back(B[i][j]);
}
sort(xx.begin(), xx.end());
sort(yy.begin(), yy.end());
if(xx != yy) return 0;
return 1;
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
cin>>A[i][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
cin>>B[i][j];
for(int i=1; i<=n; i++)
{
if( !Judge(i, 1) )
{
puts("NO");
return 0;
}
}
for(int i=1; i<=m; i++)
{
if( !Judge(n, i) )
{
puts("NO");
return 0;
}
}
puts("YES");
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);
const int N = 501;
int n, m, x, f;
multiset <int> sa[N+N],sb[N+N];
int main()
{
IOS; cin >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> x, sa[i+j].insert(x);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> x, sb[i+j].insert(x);
for(int i = 0; i < n + m; i++)
f |= sa[i] != sb[i];
cout << (f ? "NO" : "YES") << endl;
}
#include <bits/stdc++.h>
using namespace std;
const int maxn=510;
int a[maxn][maxn];
int b[maxn][maxn];
map<int,int>times[maxn*2];
int main()
{
int n,m;scanf("%d%d",&n,&m);
int f=1;
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
scanf("%d",&a[i][j]);
times[i+j+1][a[i][j]]++;
}
}
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
scanf("%d",&b[i][j]);
if(times[i+j+1][b[i][j]]<=0)f=0;
times[i+j+1][b[i][j]]--;
}
}
if(f)puts("YES");
else puts("NO");
}
查看19道真题和解析