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

liu鲤鱼 · 2026-04-26 17:12:27 · 题解

【LGR-280-Div.2】洛谷 4 月月赛 III & Diligent-OI Round 3-P16354 「Diligent-OI R3 B」天际线。

卡了将近 1h，写篇题解纪念一下。

本题解为 O(nT) 做法。

篇幅略长。

思路

先考虑何时输出 -1。

1. 如果一栋楼，既要求“从北向南”被看到，又要求“两侧看时均不能被看见”，显然不合法；
2. 同理，既要求“从南向北”被看到，又要求“两侧看时均不能被看见”，显然也不合法；
3. 假如在最北端或最南端的楼，要求“两侧看时均不能被看见”，不合法；
4. 找到要求“从北向南”被看到的楼房中最靠南的一个，找到要求“从南向北”被看到的楼房中最靠北的一个，若前者比后者更靠北，不合法。

:::info[为什么这么说？]{open} 记“要求‘从北向南’被看到的楼房中最靠南的一个”为 h_i，“要求‘从南向北’被看到的楼房中最靠北的一个”为 h_j。

要求“从北向南”被看到，意味着在位置 i 的北面不能有比这栋楼高的楼，即 \forall k \in \{1, \dots, i-1\}, h_k < h_i；

要求“从南向北”被看到，意味着在位置 j 的南面不能有比这栋楼高的楼，即 \forall k \in \{j+1, \dots, n\}, h_k < h_j。

如果 j<i，那么按照定义，需要同时满足 h_i<h_j、h_i>h_j，这显然不可能 :::

那么，对于有答案的问题，怎么去处理呢？

乍一看没有思路，我们不妨先尝试忽略所有的条件，直接构造。此时要达到字典序最小，直接升序排列即可。

然后加入 01 串 a，显然此时原序列（即从 1 到 n）仍是最优且合法的。因为串 a 本身就是要求其中为 1 的位置必须升序排列。

然后加入 01 串 b，此时我们发现，之前的序列不对了。因为 b 串本身是要求其中为 1 的位置降序排列。

还记得刚刚我们找了一个“‘从南向北’被看到的楼房中最靠北的一个”吗？它就是 b 串中最靠前的 1 的位置。对于在它之前的位置，只有 a 要处理，因此仍按照之前的方法升序处理。

对于在它之后的位置，一种显然的思路是直接把剩下的数降序排列。但要注意：降序排列意味着字典序最差，对于在 b 串中为 1 的位置，没办法，只能降序；但对于为 0 的位置，完全可以升序处理！只需保证为 0 的高度都小于为 1 的高度即可。

所以此时的方法变成了：

找到 b 串中第一个 1 的位置记为 r，对于在 r 左侧的位置，令 h_i=i；右侧的位置，先将 b 中为 0 的位置仿照左侧，升序排列；再把剩下的位置从左到右、从 n 开始依次降低，即第一个为 1 的位置（r）为 n，下一个为 n-1，以此类推；

（当然，最后一部分也可以看做是从右到左，按刚刚最后一个数字 +1 开始依次升高，最后来到最大的位置，即 h_r=n。下面代码就是这种写法。）

代码大致如下：

ll num=1;
for(ll i=1;i<r;i++)//先处理左侧的，依次升高
    h[i]=num++;
for(ll i=r+1;i<=n;i++)//右侧为 0 的部分，依次升高
    if(b[i-1]=='0') h[i]=num++;
for(ll i=n;i>=r;i--)//剩下的，右向左升高（也可以左向右依次下降）
    if(b[i-1]=='1') h[i]=num++;

最后，考虑 c 串的情况。（由于合法判断的第三条，此处不考虑第一个位置与最后一个位置。）

由于 r 两侧处理不同，我们同样以 r 为分界。

对于 r 左侧的位置，首先它的右侧一定是看不见它的，因为它本身是升序排列的；假使它是升序部分最后一个，右边的 h_r 也是最大的 n。

所以，左侧部分只需看是不是一个位置的左边有比它大的即可。

按照字典序最小的原则，肯定是这个大于它的位置越靠近它越好。假设左边紧邻的位置为 x，有连续 y 个位置不能被看见，那么 h_x 的最小值就应该是 x+y。而 剩下的 y 个位置则依次填入 x 至 x+y-1。

例如一个左半部分原本为：

1 2 3 4 5 6

现在要求第 3、4、5 个位置不能被看见。刚刚说过右边不考虑，因此让紧邻的左边的位置比它们大。这里有连续的 3 个位置不能被看见，左边紧邻的位置为 2，那么 h_2=3+2=5，h_3=2，h_4=3，h_5=4。即：

1 5 2 3 4 6