• • 题目描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例：
      • 输出样例：
  • 分析性质
    • 分析
    • 代码
    • 时间复杂度
  • 参考文章

题目传送门

题目描述

一个 n×mn×m 的整数矩阵，已知其每一行从左到右拥有哪些元素，每一列从上到下拥有哪些元素。

但是，行和列的具体顺序并不确定。

请你根据已知的信息，将矩阵复原并输出。

输入格式

第一行包含整数 TT，表示共有 TT 组测试数据。

每组数据第一行包含两个整数 n,mn,m。

接下来 nn 行，每行包含 mm 个整数，表示其中一行从左到右的所有元素。

接下来 mm 行，每行包含 nn 个整数，表示其中一列从上到下的所有元素。

输出格式

每组数据输出一个 nn 行 mm 列的矩阵。

可以证明一定存在唯一解。

数据范围

1≤T≤1051≤T≤105,
1≤n,m≤5001≤n,m≤500,
一个测试点的所有测试数据的 n×mn×m 之和不超过 250000250000。
矩阵中包含 1～n×m1～n×m 中的每个数恰好一次。
矩阵的每一行和每一列的信息都保证恰好给出一次。

输入样例：

2
2 3
6 5 4
1 2 3
1 6
2 5
3 4
3 1
2
3
1
3 1 2

输出样例：

1 2 3 
6 5 4 
3 
1 
2 

分析性质

分析

首先给出了一个矩阵的每一行所有的数字，虽然行的顺序不固定，但是根据这个信息，每一个数在哪一列就可以确定了！！然后题目说了每个数都不一样，所以用一个数组col[x]表示x这个数的列号

然后题目又给了每一列所有的数字，和行类似，虽然列之间的顺序不确定，但是有这个信息就可以确定每一个数的行号

然后就可以将一个数填到对应的行列号中了

代码

#include
#include
using namespace std;
const int N = 510;
int a[N][N];
int ans[N][N];

int col[N*N]; // 每个数字的列号

int t;
int n, m;
int main()
{
	scanf("%d", &t);
	while(t --)
	{
		scanf("%d%d", &n, &m);
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
			{
				int x;
				scanf("%d", &x);
				col[x] = j; // 记录x这个数所在的列号 
			}
		
		for(int j = 0; j < m; j++)
			for(int i = 0; i < n; i++)
			{
				int x; 
				scanf("%d", &x);
				ans[i][col[x]] = x;
			 } 
			 
		for(int i = 0; i < n; i ++)
		{
			for(int j = 0; j < m; j++) printf("%d ", ans[i][j]);
			puts("");
		}
	}
	return 0;
	
	
 } 

时间复杂度

参考文章

https://www.acwing.com/solution/content/54773/