AT_abc433_e 题解

Moya_Rao · 2025-11-23 16:05:44 · 题解

赛时看错题这一块。以为可以重复。

哇哦，我们发现直接根据 X 和 Y 两个数组去确定元素位置好像很难诶，换个角度，枚举元素然后根据 X 和 Y 的信息去确定位置吧！

怎么个顺序枚举，从小到大，还是从大到小？明显是从大到小啦，大的数选择余地很少，小的数哪哪都能填啦。

首先你会发现 n \times m 它是有且仅有一个位置可以填的，那就是满足 X_i = n \times m 且 Y_j = n \times m 的 (i,j) 方格。如果没有 i 或者没有 j 或者有多个，都无解！

为之后表述方便，记满足 X_i = n \times m 的 i 为 Nx，满足 Y_j = n \times m 的 j 为 Ny。

通过这里我们可以发现一个更加一般化的条件，那就是当存在 X_i = num 且 Y_j = num 的时候，不用怀疑，num 别无去处，只能填在 (i,j) 这个格子里。原理简单故不多说。

这只是一条。我们倒序枚举 num 的时候如果满足上面这一条可以直接固定位置——但是，如果只存在一个 X_i = num 或者 Y_j = num 呢？这个时候我们该怎么做？

有一个很厉害的做法，那就是：如果 X_i = num，就把 num 填入 (i,Ny) 格子里；如果 Y_j = num，就把 num 填入 (Nx,j) 格子里。对，总之就是取了 n \times m 所在的行或列，因为在这行列里，只要不重叠，怎么填都不违规。

处理了满足一个的情况，显然也有一个不满足的情况吧。这个时候我们就得从剩余的格子里找“庇护所”了。所谓“庇护所”的话，就是指某个格子能够填的进去 num，那么这个格子就是 num 的“庇护所”。一个 num 可能有多个“庇护所”。

现在要做的就是维护这些“庇护所”的集合咯，我这边使用了一个 vector 来存储。

这个“庇护所”怎么维护呢？我们发现，当一个 num 填入 (i,j) 这个位置时，它会对 i 这一行和 j 这一列分别进行“庇护”。当一个格子 (x,y) 满足 x 这一行被某个数“庇护”了，并且 y 这一列也被某个数“庇护”了时，这个格子 (x,y) 就成为了一个“庇护所”。

你可能要问了，“庇护”和“庇护所”不都是根据受到“庇护”的那个数的大小而产生的吗，怎么这里只字没提那个数呢？因为你忘了，我们是从大到小枚举 num 的，如果某个格子能够“庇护”一个较大的数，那么较小的数一样也能被“庇护”。

说了这么多废话，还没说到重点上呢。到底如何维护“庇护”的情况以及“庇护所”对应的那个 vector 呢？

考虑再定义两个 vector，分别命名为 px 和 py，存储受到“庇护”的行和列的分别对应的集合。嗯，这个是很简单的，每当我们把一个数 num 填入格子 (i,j) 中时，就将 i 塞进 px，j 塞进 py。

接着是维护具体的“庇护所”。依然根据 num 填入格子 (i,j) 这个例子来看，我们发现了新的一行 i 是被庇护的，这个时候遍历 py 中所有列的编号如 y，只要 (i,y) 这个格子还没有被使用，它就是一个空置的现成的“庇护所”了，这时候就要将 (i,y) 格子放进存储“庇护所”的 vector 里了。同理，新列 j 也会对应找 x，判断 (x,j) 的情况而对应进行操作。

这些维护的步骤可以考虑写两个函数来处理。

于是这样我们就成功在均摊时间复杂度 O(n \times m) 的情况下维护好了被“庇护”的行列情况，以及目前所有空置的“庇护所”了。那么我们就可以回到一开始那个问题了——如果某个 num 既没有 X_i = num 也没有 Y_j = num 该填哪里呢？有“庇护所”情况后，这不就轻而易举了嘛，随便从“庇护所”集合里抓一个出来让 num 进去不就得了。但是如果目前没有一个空置的“庇护所”，那么就只好无解咯。

最后输出即可。

这就是该题的全部做法咯，不算太难，重点在于“庇护”情况以及“庇护所”的维护。总体时间复杂度是 O(n \times m) 的，可能带有个 2 的常数。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 2e5+5;
int T,n,m,a[N],b[N],Nx,Ny;
vector<int> s[N],px,py;
vector<pii> D;bool flag;
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
void InsX(int x){
    for(int y:py)
        if(!s[x][y])D.pb({x,y});
    px.pb(x);return;
}
void InsY(int y){
    for(int x:px)
        if(!s[x][y])D.pb({x,y});
    py.pb(y);return;
}
int main(){
    T=read();
    while(T--){
        n=read(),m=read(),flag=0;
        px.clear(),py.clear();
        for(int i=1;i<=n;i++)s[i].resize(m+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)s[i][j]=0;
        for(int i=1;i<=n*m;i++)a[i]=0,b[i]=0;
        for(int i=1;i<=n;i++){int x=read();a[x]=i;}
        for(int i=1;i<=m;i++){int x=read();b[x]=i;}
        Nx=a[n*m],Ny=b[n*m];
        if(!Nx||!Ny){cout<<"No\n";continue;}
        px.pb(Nx),py.pb(Ny),s[Nx][Ny]=n*m;
        for(int x=n*m-1;x>=1;x--)
            if(a[x]&&b[x]){
                s[a[x]][b[x]]=x;
                InsX(a[x]),InsY(b[x]);
            }else if(a[x]||b[x]){
                if(a[x])s[a[x]][Ny]=x,InsX(a[x]);
                else s[Nx][b[x]]=x,InsY(b[x]);
            }else if(D.empty()){flag=1;break;}
            else{
                auto [i,j]=D.back();
                s[i][j]=x;D.pop_back();
            }
        if(flag){cout<<"No\n";continue;}
        cout<<"Yes\n";
        for(int i=1;i<=n;cout<<"\n"&&i++)
            for(int j=1;j<=m;j++)cout<<s[i][j]<<" ";
    }
    return 0;
}

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！