题面：
传送门
题目描述：
给出两个n x m的矩阵A，B。矩阵A可以把正方子矩阵进行“转置操作”，问：可不可以对矩阵A进行多次这样的操作，使矩阵A变为矩阵B？
题目分析：
这道题是一道水题，但是我一时脑子瓦特了，看了题解也有点懵，看了代码才突然想明白的，所以特地来写一下博客。
首先，我们可以发现：
矩阵里面的一个元素可以通过多次转置转移到其他地方，其他的对应元素也会相应发生变化。所以，这个变换过程会很复杂。如果直接去暴力模拟的话，矩阵里面有500*500个元素，遍历一遍就要1e5的时间了，暴力是肯定不行的。这时，我们仍分析变化的东西会变得更为复杂，所以关键是找不变的东西，那怎么找呢？可以看一下样例：由于样例1，2太简单了，我们就不去分析它们。我们看看样例3：
这里我们很容易发现：变化之后的数字要么就是原来的位置，要么就是关于主对角线对称的位置。那是不是巧合呢？的确是巧合，我们可以找出这样的反例：当矩阵A不变，矩阵B为这样时：
1 4 5
2 7 6
3 8 9
其实这个矩阵B就是上右方的那个矩阵B的2*2子矩阵转置一下，但这个转置后的矩阵B显然不符合刚刚我们推出的规律。
所以我们要继续思考：
既然是要在变化中找不变的规律，我们肯定要找变化的元素，然后看它们的属性，找出不变量，拿上述矩阵的数字7作为例子看看：
在矩阵A中，他的位置是第3行，第1列。而在新的矩阵B中，7的位置在第2行，第2列。我们发现了：3+1 == 2+2
这似乎就是我们要找的答案了：转置后，元素的行列之和不变。那为什么会这样呢？我们进一步的想：在转置的过程中，我们是通过主对角线来进行转置的，示意图（红色的块转置后变成绿色的块）：
再进一步，是这样进行转置的：
我们沿着反对角线，从红色的方块走到绿色的方块：
先从红色的方块走到黄色的方块：行-1，列+1
同理，走到绿色的方块时：行-3，列+3，刚刚好行列增量抵消掉了。
即：所有元素都可以沿着的反对角线走，从而使自己的行列之和不变。
所以，要判断矩阵A是否能变成矩阵B，只需要判断：行列之和相同时，两个矩阵包含的元素相同就可以了（这里有多种写法，能达到这个目的就可以了）。
AC代码（vector版本）：
1 #include <stdio.h>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5 int n, m, A, B;
6 vector<int> a[1005], b[1005];
7
8 int main(){
9 scanf("%d%d", &n, &m);
10 for(int i = 0; i < n; i++){
11 for(int j = 0; j < m; j++){
12 scanf("%d", &A);
13 a[i+j].push_back(A); //将行列之和相同的元素加入到同一组
14 }
15 }
16 for(int i = 0; i < n; i++){
17 for(int j = 0; j < m; j++){
18 scanf("%d", &B);
19 b[i+j].push_back(B);
20 }
21 }
22
23 for(int i = 0; i < n+m; i++){
24 //排序，方便下面判断
25 sort(a[i].begin(), a[i].end());
26 sort(b[i].begin(), b[i].end());
27
28 if(a[i] != b[i]){ //判断：行列之和相同时，两个矩阵包含的元素是否相同
29 printf("NO\n");
30 return 0;
31 }
32 }
33 printf("YES\n");
34 return 0;
35 }
Codeforces Round #546 C. Nastya Is Transposing Matrices
原文：https://www.cnblogs.com/happy-MEdge/p/10821586.html
