题解：CF1136C Nastya Is Transposing Matrices

· · 题解

前置知识

你需要具备推理能力、画图能力，本题建议评黄。

思路讲解

题意已经很清晰，这里不再额外补充，没看懂多看几次。

接下来拿出纸和笔，假设现在有一个 3 \times 3 的方形矩阵，数字是 1 到 9，按照题意转置，即反转 i 和 j 下标，得到新的方形矩阵，如图所示：

我们发现转置后，每条副对角线（图中橙色线段）上的数字顺序反转，得出这一结论后就可以解决本题了：我们要判断矩阵 A 是否能变换为矩阵 B，只需要判断每条副对角线长度和元素是否一样，一样即可行，不一样即不可行。

如何获取每条副对角线元素？我们列出同一副对角线所有元素的下标，发现 i 与 j 的和相同，因此放入同一数组即可；最后，对于 n \times m 的矩阵，可得到 n + m 条副对角线，依次判断长度和元素是否相同就好了。

代码展示

为便于理解，参考代码较分散，实际编写时可简化，代码如下：

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f
#define ll long long
#define ld long double
#define endl '\n'

#define int long long

// 快速读入与快速输出，可选
inline int read() {int x = 0, w = 1;char ch = 0;while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') {  x = x * 10 + (ch - '0');ch = getchar();}return x * w;}
void write(int x) {static int sta[35];int top = 0;do {sta[top++] = x % 10, x /= 10;} while (x);while (top) putchar(sta[--top] + 48); }

int n,m; // 矩阵大小 
int a[507][507]; // 矩阵 A 
int b[507][507]; // 矩阵 B 
vector<int> x[1007]; // 矩阵 A 的副对角线 
vector<int> y[1007]; // 矩阵 B 的副对角线 

signed main(){
    n=read(),m=read(); // 读入大小 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read(); // 读入矩阵 A 
        }
    } 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            b[i][j]=read(); // 读入矩阵 B 
        }
    } 

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            x[i+j].push_back(a[i][j]); // 将矩阵 A 元素放入副对角线数组 
        }
    } 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            y[i+j].push_back(b[i][j]); // 将矩阵 B 元素放入副对角线数组
        }
    } 

    for(int i=1;i<=n+m;i++){ // 一共 n+m 条副对角线，枚举 
        sort(x[i].begin(),x[i].end()); // 元素排序，方便后续比较 
        sort(y[i].begin(),y[i].end());
        if(x[i].size() != y[i].size()){ // 长度不一样 
            cout<<"NO"; // 无法变换得到，退出 
            return 0;
        }
        for(int j=0;j<x[i].size();j++){ // 枚举两个矩阵里的这条副对角线 
            if(x[i][j]!=y[i][j]){ // 元素不一样
                cout<<"NO"; // 无法变换得到，退出 
                return 0;
            }
        }
    } 

    cout<<"YES"; // 可变换得到 

    return 0; // 完结撒花！ 
}