题解：P16354 「Diligent-OI R3 B」天际线

· · 题解

挺有意思的一道题。

字典序最小，我们不妨从初始序列为 1\sim n 开始交换。

初始情况下肯定 a 的要求是满足的，那接下来我们要依次处理 b 和 c 的限制。我们来思考一下 b 要怎么处理。发现如果 b_i=1，其右边的所有数都不能大于它。于是一个大胆的想法就浮现出来了，我们拿当前右边最大的值来填这个位置，然后剩下的向右补全最大的那个数的空位。这里要判个无解，条件是最大的那个数的 a 为 1，原因自行思考。这样处理出来的序列一定是字典序最小的。

然后是 c。我们先把 c_1=1\lor c_n=1 的无解以及其与 a 和 b 矛盾的无解判掉。对于 c_i=1，其右边必定存在比其大的数。为什么？如果没有的话早就被当做无解判掉了（如果没有的话意味着 b_i=1，与 c_i=1 矛盾）。那我们要左边的数有一个大于它。我们先判断左边有没有数大于它，如果没有，最简单的操作：将 i 和 i-1 交换位置，依旧能保证字典序最小。

:::success[code]


#include <bits/stdc++.h>
using namespace std;
int T,n,ans[100005],minn,maxx,sum;
bool flag,f;
string a,b,c;
int main(){
    cin>>T;
    while(T--){
        cin>>n>>a>>b>>c;
        a=' '+a,b=' '+b,c=' '+c,flag=f=0;
        for(int i = 1;i<=n;i++)
            if(c[i]=='1'&&(a[i]=='1'||b[i]=='1'))
                flag=1;
        for(int i = 1;i<=n;i++){
            if(a[i]=='1'&&f) flag=1;
            if(b[i]=='1') f=1;
        }
        if(c[1]=='1'||c[n]=='1') flag=1;
        if(flag){cout<<"-1\n";continue;}
        minn=1,maxx=n;
        for(int i = 1;i<=n;i++)
            if(b[i]=='1') ans[i]=maxx--,sum++;
            else ans[i]=minn++;
        for(int i = n;i>=1;i--)
            if(b[i]=='1') sum--;
            else if(c[i]=='1'&&!sum)
                swap(ans[i],ans[i-1]);
        if(flag){cout<<"-1\n";continue;}
        for(int i = 1;i<=n;i++) cout<<ans[i]<<' ';
        cout<<'\n';
    }
    return 0;
}
/*
1 3 2 4 5
0010
0100

*/