专栏文章

题解：AT_abc433_e [ABC433E] Max Matrix 2

__Weslie_
AT_abc433_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min1284c
此快照首次捕获于
2025/12/01 18:49
3 个月前
此快照最后确认于
2025/12/01 18:49
3 个月前
查看原文
退役前最后一场 ABC 吧。

Solution AT_abc433_e

先把行和列拆开。
我们对于一个行的数组，给它排序。由于一行必然要填 mm 个数，也就是说对于 aia_i 如果没有 mm 个小于等于 aia_i 的数显然无解。设 aia_i 排序之后位置是 pp，则 ≤ai\le a_i 的数的个数为 ai−(p−1)ma_i-(p-1)m（前面 p−1p-1 行，每行都要用 mm 个）。
对于列其实也差不多，给它排序，如果没有 nn 个小于等于 bib_i 的数无解。
然后因为一个数不能同时出现在两行或者两列，所以 aia_i 必须互异，否则无解。
然后你考虑开始填数。
  • 先把限制最强的填了：如果 ai=bj=xa_i=b_j=x，则直接把 xx 填到 (i,j)(i,j)。
  • 然后填次强的：如果 ai=xa_i=x，找到一个 bj>xb_j>x 且 (i,j)(i,j) 还没有被填的位置填上 xx。对于列同理，找到一个 ai>xa_i>x 且还没有被填数的位置填上 xx 即可。
  • 然后还剩下一些位置没有被填。我们考虑：min⁡(ai,bj)\min(a_i,b_j) 越小，可以填的数越少，限制越强。综上，我们把没有填的位置塞进一个 vector 里，然后按照 min⁡(ai,bj)\min(a_i,b_j) 排序，然后从 11 开始，双指针遍历：
    • 如果当前的数还没有被用，则把这个数填到这个位置里，然后换到下一个数。
    • 如果当前的数已经被用了，直接换到下一个数。
不难发现这样是最能满足这些限制的方案。
但是你会 WA 55 个点。原因是，给你一组 hack：
CPP
1
2 2
2 4
2 4
你可能会输出
CPP
2 1
3 4
也可能输出
CPP
2 3
1 4
但是这两个都是不符合条件的。所以填完之后，我们再检查一遍，如果还是不满足，就无解了。
CodeCPP
#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();
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...