P14592 题解

题目思路

首先明确，MEX 只与数组中最小的未出现正整数有关，所以大于 MEX 的数字对 MEX 没有贡献。

所以我们尝试不用大于等于 MEX 的正整数构造矩阵，此时我们解题就要用到一个性质，那就是每行的 MEX 数组和每列的 MEX 数组都是一个排列。下面的思路会基于这个性质填充矩阵的每一个位置。

比如我们先考虑某一行，此时这一行对应的每一个位置，它所在的列的 MEX 一定也是一个排列。我们不妨设这一行的 MEX 为

x

，第

i

个位置对应列的 MEX 为

y_i

，分讨两种情况：

$x \le y_i$ ，这些位置一共有 $y_i$ 个， $y_i$ 对应的为 $1 \sim x$ ，而若要构造出这一行 MEX 为 $x$ ，必须要有 $0 \sim x - 1$ 的每一个值，只需要把矩阵的这些位置的填充为 $y_i - 1$ 即可。
$x > y_i$ ，这些位置对这一行的 MEX 没有用处，因为我们已经用 $x \le y_i$ 的位置构造出了这一行的 MEX，那么剩下的这些位置可以填充小于 $x$ 的值。

上述的填充方法显然可以用于矩阵的每一行、每一列，只要我们把考虑某一行变为考虑某一列即可。这样我们重新考虑上面分讨的第二种情况，只需要此时这个位置填充的值小于

\min(x , y_i)

即可；而第一种情况可以推广为填充

\min(x , y_i) - 1

。所以美观起见，第二种情况也可以这么填。

最后我们考虑全局，这个方法也是正确的。用题目里的信息表述的话，那么

\forall i , j \in [1 , n] , a_{i , j} = \min(r_i , c_j) - 1

。

然后就做完了。

题目代码

代码和上面讲解的唯一区别就是数组名换成了

a

和

b

，两者结合着看不会影响理解。

CPP

#include<iostream>
using namespace std;
int a[2005] , b[2005];
void solve()
{
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i];
    }
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> b[i];
    }
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            cout << min(a[i] , b[j]) - 1 << " \n" [j == n];
        }
    }
}
signed main()
{
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

题解：P14592 [LNCPC 2025] 裂痕

文章操作

P14592 题解

题目思路

题目代码

相关推荐

评论

题解：P14592 [LNCPC 2025] 裂痕