自动搬运

查看原文

来自洛谷，原作者为

	zy AFO

搬运于2025-08-24 21:49:31，当前版本为作者最后更新于2021-05-04 15:20:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题目大意：

判断一个 $nm$ 的矩阵能否通过整行整列更改成目标矩阵。

我们很显然能知道的是：

对于一行数而言：

• 如果通过整行更改只改变了位置，并不会有什么其它改变；

• 而整列更改则会改变这一行数的顺序，并不会引起其他变化。

总之，不论怎么变换，一行数到底是由哪几个数组成，是不会变化的！

一列数同理。

所以我们只需要 $Judge$ 目标矩阵的每一行,每一列是不是在原矩阵中出现过即可。

考虑每一列，每一行的数字组成映射成为一个数字。

显然可以构造：

$K= \sum_{i=1}^{n(m)}+\prod_{i=1}^{n(m)}$

来映射这一行或这一列的数字组成。

然后用 $map$ 来存储。

时间复杂度 $O_{Tmn}$.

小细节：

不要忘记开 $long$ $long$ ，亲测 $40$。

不要忘记清空 （数据应该没有卡这一部分。

目标数组没有出现所有在原矩阵的值也不可以。

分行列(其实题目中说明了元素两两不同，这个其实没有必要)

$//Updating$

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define int long long 
#define N 10010
#define MOD 10000007
using namespace std;
int re() {
	int p=0,f=1; char i=getchar();
	while(i<'0'||i>'9')	{if(i=='-')  f=-1;i=getchar();}
	while(i>='0'&&i<='9')	p=p*10+i-'0',i=getchar();
	return f*p;
}
int T,n,m,cnt;
int a[N][N],f[N];
map<int , bool > v_x,v_y,u_x,u_y;
bool Judge() 
{
	u_x.clear();
	u_y.clear();
	for(int i=1;i<=n;i++)
	{
		int mul=1,sum=0;
		for(int j=1;j<=m;j++)	{
			mul*=a[i][j];
			mul%=MOD;
			sum+=a[i][j];
		}
		u_x[sum+mul]=1;
		if(!v_x[mul+sum])	return false;
	}
	for(int j=1;j<=m;j++)
	{
		int mul=1,sum=0;
		for(int i=1;i<=n;i++)
		{
			mul*=a[i][j];
			mul%=MOD;
			sum+=a[i][j];
		}
		u_y[sum+mul]=1;
		if(!v_y[mul+sum])	return false;
	}
	for(int i=1;i<=cnt;i++)
		if(!u_x[f[i]]&&!u_y[f[i]])	return false;
	return true;
}
signed main()
{
	T=re();
	while(T--)
	{
		memset(f,0,sizeof(f));
		v_x.clear(); v_y.clear();
		cnt=0;
		n=re(); m=re();
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)	a[i][j]=re();
		for(int i=1;i<=n;i++)
		{
			int mul=1,sum=0;
			for(int j=1;j<=m;j++)	{
				mul*=a[i][j];
				mul%=MOD;
				sum+=a[i][j];
			}
			f[++cnt]=mul+sum;
			v_x[mul+sum]=1;
		}
		for(int j=1;j<=m;j++)
		{
			int mul=1,sum=0;
			for(int i=1;i<=n;i++)
			{
				mul*=a[i][j];
				mul%=MOD;
				sum+=a[i][j];
			}
			f[++cnt]=mul+sum;
			v_y[mul+sum]=1;
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)	a[i][j]=re();
		if(Judge())	printf("TAK\n");
		else printf("NIE\n");
	}
}

如果有不妥之处，请不要吝啬您的评论.

双倍经验

$qwq$