题解：P14592 [LNCPC 2025] 裂痕

· · 题解

P14592 题解

题目思路

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

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

比如我们先考虑某一行，此时这一行对应的每一个位置，它所在的列的 MEX 一定也是一个排列。我们不妨设这一行的 MEX 为 x，第 i 个位置对应列的 MEX 为 y_i，分讨两种情况：

上述的填充方法显然可以用于矩阵的每一行、每一列，只要我们把考虑某一行变为考虑某一列即可。这样我们重新考虑上面分讨的第二种情况，只需要此时这个位置填充的值小于 \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，两者结合着看不会影响理解。

#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;
}