AT_abc433_e 题解

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

哇哦，我们发现直接根据

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

的常数。

CPP

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

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

文章操作

相关推荐

评论

AT_abc433_e 题解