「Diligent-OI R3 B」天际线

_H17_ · 2026-04-26 21:44:59 · 题解

题目分析

首先如果 \max(a_i,b_i)=1,c_i=1 不合法。其次容易发现以 n 为分界线把楼划分成两半，前一半没有 b_i=1，后一半没有 a_i=1。

不妨记录 lsta 表示最后一个 a_i=1 的 i，类似的也有 fstb。如果 lsta>fstb 就没有合法构造。

然后考虑字典序的贪心。你发现按道理来说在 fstb 之前（不包括）的位置都应该直接从 1 往后顺着排，但是有一些 c 的限制。假设 c_i=1 那就表示之前有一个要超过它，由于贪心这个值一定是 i。那就变成了 ans_{pre_i}=i（pre_i 表示满足 c_j=0,j<i 的最大 j，如果不存在则无解）。剩下的空位直接从小到大填没用过的数就行，双指针维护可以线性。

然后 fstb 之后的位置限制变化了，变成如果 c_i=0 那么这个数是后缀最值，也就是需要把剩下最大的数选上，否则就选最小的。

有一个 corner case 就是 c_n=0，这是不合法的。

时间复杂度 O(Tn)。

代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e5+2;
int T,n,a[N],b[N],c[N],pre[N],ans[N],vis[N],lsta,fstb;
string sa,sb,sc;
void task(){
    memset(ans,0,sizeof(ans)),
    memset(vis,0,sizeof(vis));
    cin>>n>>sa>>sb>>sc;
    sa=" "+sa,sb=" "+sb,sc=" "+sc;
    for(int i=1;i<=n;i++)
        a[i]=(sa[i]-'0'),b[i]=(sb[i]-'0'),c[i]=(sc[i]-'0');
    lsta=0,fstb=n+1;
    for(int i=1,prenc=0;i<=n;i++){
        if(c[i]&&(a[i]||b[i]))
            return println("-1");
        if(a[i])
            lsta=i;
        if(b[i]&&fstb>n)
            fstb=i;
        if(!c[i])
            prenc=i;
        pre[i]=prenc;
    }
    if(lsta>fstb||c[n])
        return println("-1");
    for(int i=1;i<fstb;i++)
        if(c[i]){
            if(!pre[i])
                return println("-1");
            ans[pre[i]]=i;
        }
    for(int i=1;i<fstb;i++)
        if(ans[i])
            vis[ans[i]]=1;
    for(int i=1,j=1;i<fstb;i++){
        while(vis[j])
            j++;
        if(!ans[i])
            ans[i]=j,vis[j]=1;
    }
    for(int i=fstb,j1=1,j2=n;i<=n;i++){
        while(vis[j1])
            j1++;
        while(vis[j2])
            j2--;
        if(b[i])
            ans[i]=j2,vis[j2]=1;
        else
            ans[i]=j1,vis[j1]=1;
    }
    for(int i=1;i<=n;i++)
        print("{} ",ans[i]);
    return println("");
}
string program(){
    cin.tie(nullptr)->ios::sync_with_stdio(0);
    for(cin>>T;T;T--)
        task();
    return"H17";
}
string H17=program();
int main(){
    return 0;
}