题解：AT_abc433_e [ABC433E] Max Matrix 2

_Weslie_ · 2025-11-25 09:39:38 · 题解

退役前最后一场 ABC 吧。

Solution AT_abc433_e

先把行和列拆开。

我们对于一个行的数组，给它排序。由于一行必然要填 m 个数，也就是说对于 a_i 如果没有 m 个小于等于 a_i 的数显然无解。设 a_i 排序之后位置是 p，则 \le a_i 的数的个数为 a_i-(p-1)m（前面 p-1 行，每行都要用 m 个）。

对于列其实也差不多，给它排序，如果没有 n 个小于等于 b_i 的数无解。

然后因为一个数不能同时出现在两行或者两列，所以 a_i 必须互异，否则无解。

然后你考虑开始填数。

先把限制最强的填了：如果 a_i=b_j=x，则直接把 x 填到 (i,j)。
然后填次强的：如果 a_i=x，找到一个 b_j>x 且 (i,j) 还没有被填的位置填上 x。对于列同理，找到一个 a_i>x 且还没有被填数的位置填上 x 即可。
然后还剩下一些位置没有被填。我们考虑：\min(a_i,b_j) 越小，可以填的数越少，限制越强。综上，我们把没有填的位置塞进一个 vector 里，然后按照 \min(a_i,b_j) 排序，然后从 1 开始，双指针遍历：
- 如果当前的数还没有被用，则把这个数填到这个位置里，然后换到下一个数。
- 如果当前的数已经被用了，直接换到下一个数。

不难发现这样是最能满足这些限制的方案。

但是你会 WA 5 个点。原因是，给你一组 hack：

你可能会输出

2 1
3 4

也可能输出

2 3
1 4

但是这两个都是不符合条件的。所以填完之后，我们再检查一遍，如果还是不满足，就无解了。 ::::success[Code]

#include<bits/stdc++.h>
using namespace std;
const int N=400005;
#define fi first
#define se second
vector<int>ans[N];
int p[N],q[N],a[N],b[N],vis[N];
int n,m;
vector<pair<int,pair<int,int> > >g;
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        p[i]=a[i];
        ans[i].clear();
        ans[i].resize(m+1);
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
        q[i]=b[i];
    }
    for(int i=1;i<=n*m;i++)vis[i]=0;
    sort(p+1,p+n+1);
    sort(q+1,q+m+1);
    for(int i=1;i<=n;i++){
        if(p[i]-(i-1)*m<m){
            cout<<"No\n";
            return;
        }
        if(p[i]==p[i-1]){
            cout<<"No\n";
            return;
        }
    }
    for(int i=1;i<=m;i++){
        if(q[i]-(i-1)*n<n){
            cout<<"No\n";
            return;
        }
        if(q[i]==q[i-1]){
            cout<<"No\n";
            return;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]==b[j]){
                ans[i][j]=a[i];
                vis[a[i]]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(vis[a[i]])continue;
        for(int j=1;j<=m;j++){
            if(ans[i][j]==0){
                if(b[j]>a[i]){
                    ans[i][j]=a[i];
                    vis[a[i]]=1;
                    break;
                }
            }
        }
    }
    for(int j=1;j<=m;j++){
        if(vis[b[j]])continue;
        for(int i=1;i<=n;i++){
            if(ans[i][j]==0){
                if(a[i]>b[j]){
                    ans[i][j]=b[j];
                    vis[b[j]]=1;
                    break;
                }
            }
        }
    }
    g.clear();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!ans[i][j]){
                g.push_back(make_pair(min(a[i],b[j]),make_pair(i,j)));
            }
        }
    }
    sort(g.begin(),g.end());
    int i=1;
    for(auto t:g){
        int x=t.se.fi,y=t.se.se;
        while(i<=n*m&&vis[i])i++;
        ans[x][y]=i;i++;
    }
    for(int i=1;i<=n;i++){
        int mx=0;
        for(int j=1;j<=m;j++)mx=max(mx,ans[i][j]);
        if(mx!=a[i]){
            cout<<"No\n";
            return;
        }
    }
    for(int j=1;j<=m;j++){
        int mx=0;
        for(int i=1;i<=n;i++){
            mx=max(mx,ans[i][j]);
        }
        if(mx!=b[j]){
            cout<<"No\n";
            return;
        }
    }
    cout<<"Yes\n";
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<ans[i][j]<<' ';
        }
        cout<<'\n';
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--)solve();
}

::::