P3492

题面

给两个

n \times m

的矩阵，可以交换两行，可以交换两列，求第一个矩阵可不可以用若干次操作变成第二个。

题解

不管怎么换，位于同行的总位于同行，位于同列的总位于同列，不可能拆开。

而且，这里因为元素各不相同，所以第一个矩阵中一个元素只能对应到第二个矩阵至多一个元素。

所以要判断是不是对于第一个矩阵任意一行，都在第二个矩阵中有包含相同元素的一行对应；对于第一个矩阵任意一列，都在第二个矩阵中有包含相同元素的一列对应。

如果满足上一段的结论，则绝对成立（考虑先换列，列换成对应的状态后换行即可）。

判每行，找到第一个矩阵中第

i

行第一个元素在第二个矩阵的所在行

x

，然后看第一个矩阵中

i

行的元素是不是都出现在第二个矩阵的

x

行。

判每列，找到第一个矩阵中第

j

列第一个元素在第二个矩阵的所在列

y

，然后看第一个矩阵中

j

列的元素是不是都出现在第二个矩阵的

y

列。

此题结。

一句闲话：这题之前我用了 vector 和 unordered_map 都被卡掉了，后面发现可以直接用数组（把低于

0

的元素加到

0

以上）。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
const int pls=1e6; 
int _;
int n,m;
int sx[N*2],sy[N*2];
int v1[1050][1050],v2[1050][1050];
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)) {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
inline void solve() {
	n=read(),m=read();
	for(int i=1;i<=n;i++) {
		for(int j=1,x;j<=m;j++) {
			v1[i][j]=x=read();
			sx[x+pls]=0,sy[x+pls]=0;
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=1,x;j<=m;j++) {
			v2[i][j]=x=read();
			sx[x+pls]=i,sy[x+pls]=j;
		}
	}
	for(int i=1;i<=n;i++) {
		int fl=sx[v1[i][1]+pls];
		for(int j=1;j<=m;j++) {
			int t=v1[i][j];
			if(!sx[t+pls]||sx[t+pls]!=fl) {puts("NIE");return;}
		}
	}
	for(int i=1;i<=m;i++) {
		int fl=sy[v1[1][i]+pls];
		for(int j=1;j<=n;j++) {
			int t=v1[j][i];
			if(!sy[t+pls]||sy[t+pls]!=fl) {puts("NIE");return;}
		}
	}
	puts("TAK");
	return;
}
int main() {
	scanf("%d",&_);
	while(_--) solve();
	return 0;
}

文章操作

题面

题解

代码

相关推荐

评论

P3492