题解：CF1136C Nastya Is Transposing Matrices

前置知识

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

思路讲解

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

接下来拿出纸和笔，假设现在有一个

3 \times 3

的方形矩阵，数字是

1

到

9

，按照题意转置，即反转

i

和

j

下标，得到新的方形矩阵，如图所示：

我们发现转置后，每条副对角线（图中橙色线段）上的数字顺序反转，得出这一结论后就可以解决本题了：我们要判断矩阵

A

是否能变换为矩阵

B

，只需要判断每条副对角线长度和元素是否一样，一样即可行，不一样即不可行。

如何获取每条副对角线元素？我们列出同一副对角线所有元素的下标，发现

i

与

j

的和相同，因此放入同一数组即可；最后，对于

n \times m

的矩阵，可得到

n + m

条副对角线，依次判断长度和元素是否相同就好了。

代码展示

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

CPP

#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; // 完结撒花！ 
}

题解：CF1136C Nastya Is Transposing Matrices

文章操作

前置知识

思路讲解

代码展示

相关推荐

评论

题解：CF1136C Nastya Is Transposing Matrices