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

N0_1 · 2026-04-26 20:32:58 · 题解

本文下标（索引）从 1 开始编号。

令构造出来的序列为 A。

因为是一个排列，对于 A_{p} = n：

• 对于所有的 i < p，一定有 b_{i} = 0。
• 对于所有的 i > p，一定有 a_{i} = 0。

令 a 中最后一次出现 1 的位置为 L，b 中第一次出现 1 的位置为 R，显然 L \le p \le R。

因为要保证字典序最小，则 p = R。

无解的情况：

• 对于所有的 i \in [L, R]，不存在 c_{i} = 0。

• 存在 i 满足 a_{i} = 1 或 b_{i} = 1，且 c_{i}=1。

此时就可以根据 A_{p} = n 把序列 A 划分成左右两部分。

把 a,b,c 的限制转换成一条有向边：对于一条 u 去 v 的边，表示 A_{u} < A_{v}。

对于左侧：

• 若 a_{i} = 1，则对于所有的 j < i，有一条 j 指向 i 的边。这一部分可以通过 “大小关系的传递性” 建图，防止 MLE 和 TLE。

• 对于 c_{i} = 1 的部分，因为要求字典序最小，显然要让 i 指向最接近 i 的点 j 且 c_{j}=0。

右侧同理。

最后使用优先队列实现的拓扑排序即可解决该题。

#include<bits/stdc++.h>

#define debug(x, ch) cerr << #x << ": " << x << ch

using namespace std;

typedef long long LL;

const int N = 1e5 + 5, inf = 0x3f3f3f3f;

int n;
string a, b, c;

vector<int> g[N];
int inDep[N];

void subtask3() {   
    a = "!" + a; b = "!" + b;  c = "!" + c;

    if (c[1] == '1' || c[n] == '1') return cout << "-1\n", void();
    for (int i = 1; i <= n; i++) {
        if ((a[i] == '1' || b[i] == '1') && c[i] == '1') {
            return cout << "-1\n", void();
        }
    } 

    int L = 1, R = n;
    for (int i = 1; i <= n; i++) if (a[i] == '1') L = i;
    for (int i = n; i >= 1; i--) if (b[i] == '1') R = i;

    if (L > R) return cout << "-1\n", void();

    int P = -1;
    for (int i = R; i >= L; i--) {
        if (c[i] == '0') {
            P = i;
            break;
        }
    }

    if (P == -1) return cout << "-1\n", void();

    auto add = [&](int u, int v) {
        g[u].push_back(v);
        inDep[v] ++; 
    };

    int last = 1, zero = 1;
    for (int i = 1; i < P; i++) {
        if (c[i] == '0') zero = i;

        if (a[i] == '1') {
            for (int j = last; j < i; j++) add(j, i);
            last = i;
        }
        if (c[i] == '1') add(i, zero);
    }

    last = n;
    zero = n; 
    for (int i = n; i > P; i--) {
        if (c[i] == '0') zero = i;

        if (b[i] == '1') {
            for (int j = last; j > i; j--) add(j, i);
            last = i;
        }

        if (c[i] == '1') add(i, zero);
    }

    for (int i = 1; i <= n; i++) {
        if (i != P) add(i, P);
    }

    priority_queue<int, vector<int>, greater<int> > pq;

    for (int i = 1; i <= n; i++) if (inDep[i] == 0) pq.push(i);

    vector<int> ans(n + 1, 0);
    int k = 0;
    while (pq.size()) {
        int u = pq.top();
        pq.pop();
        ans[u] = ++k;
        for (int v: g[u]) {
            if (--inDep[v] == 0) pq.push(v);
        }
    }

    if (k == n) for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
    else cout << "-1\n"; 
}

void solve() {
    cin >> n >> a >> b >> c;

    subtask3();

    for (int i = 1; i <= n; i++) {
        g[i].clear();
        inDep[i] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while (T --) {
        solve();
    } 

    return 0;
}