The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-L. Leak

题目大意

题目描述

给定一个正整数 $n$ 以及两个长度为 $n$ 的排列 $r$ 和 $c$。
请构造一个 $n \times n$ 的矩阵，满足以下所有条件：

1. 矩阵中的所有元素均为 $[0, n]$ 范围内的整数。

2. 矩阵第 $i$ 行元素的 $\text{MEX}$ 值为 $r_i$。

3. 矩阵第 $i$ 列元素的 $\text{MEX}$ 值为 $c_i$。

注：数组的 $\text{MEX}$ 值是指数组中未出现的最小非负整数。题目保证必然存在符合上述条件的矩阵。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^3$），表示测试用例的数量。
对于每个测试用例：
第一行包含一个正整数 $n$（$1 \le n \le 2 \times 10^3$）。
第二行包含一个长度为 $n$ 的排列 $r_1, r_2, \dots, r_n$。
第三行包含一个长度为 $n$ 的排列 $c_1, c_2, \dots, c_n$。
保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^3$。

输出格式

对于每个测试用例，输出 $n$ 行，每行包含 $n$ 个整数，表示满足所有条件的矩阵。如果有多个符合条件的矩阵，输出其中任意一个即可。

样例数据

输入:
2
4
2 1 3 4
3 4 1 2
5
2 1 4 3 5
1 4 2 5 3

输出:
0 0 4 1
2 3 4 0
1 2 0 1
0 1 2 3
0 0 0 0 1
0 0 0 2 0
2 3 3 1 0
2 1 0 4 2
0 2 1 3 4

样例解释

以第一个测试用例为例，$n = 4$，$r = [2, 1, 3, 4]$，$c = [3, 4, 1, 2]$。
对于输出的矩阵：

• 第 $1$ 行元素为 $[0, 0, 4, 1]$，其中包含 $0, 1, 4$，未出现的最小非负整数为 $2$，等于 $r_1$。

• 第 $2$ 行元素为 $[2, 3, 4, 0]$，其中包含 $0, 2, 3, 4$，未出现的最小非负整数为 $1$，等于 $r_2$。

• 第 $3$ 行元素为 $[1, 2, 0, 1]$，其中包含 $0, 1, 2$，未出现的最小非负整数为 $3$，等于 $r_3$。

• 第 $4$ 行元素为 $[0, 1, 2, 3]$，其中包含 $0, 1, 2, 3$，未出现的最小非负整数为 $4$，等于 $r_4$。

同理观察列方向上的 $\text{MEX}$ 值：

• 第 $1$ 列元素为 $[0, 2, 1, 0]$，包含 $0, 1, 2$，其 $\text{MEX}$ 值为 $3$，等于 $c_1$。

• 第 $2$ 列元素为 $[0, 3, 2, 1]$，包含 $0, 1, 2, 3$，其 $\text{MEX}$ 值为 $4$，等于 $c_2$。

• 第 $3$ 列元素为 $[4, 4, 0, 2]$，包含 $0, 2, 4$，其 $\text{MEX}$ 值为 $1$，等于 $c_3$。

• 第 $4$ 列元素为 $[1, 0, 1, 3]$，包含 $0, 1, 3$，其 $\text{MEX}$ 值为 $2$，等于 $c_4$。

所有行和列的 $\text{MEX}$ 值均完全符合输入的排列要求，该矩阵合法。

思路讲解

不难注意到这样一个构造方法。

然后，其实我们自己也想到了，一个构造方法，可以通过行列交换，得到新的，任何符合要求的这个 mex 矩阵。

通过行交换，可以使得列的条件依然得到满足。通过列交换，可以使得行的条件依然得到满足。

因此，现应用行交换，再应用列交换，就可以把一个这个构造方法变成任何东西。

for (int i_R=1;i_R<=N;++i_R) {
    ll i=R[i_R];
    for (int j_C=1;j_C<=N;++j_C) {
        ll j=C[j_C];
        cout<<maze[i][j]<<" ";
    }
    cout<<"\n";
}

AC代码

AC
https://codeforces.com/gym/106380/submission/366322358

源代码

心路历程（WA，TLE，MLE……）