建筑装饰 3 / Building 3

Chasing_Meteors · 2025-12-04 09:55:59 · 题解

题目给定了序列 B，让我们添加一个数到 B 的任意位置，得到的 A 存在一个元素互不相同的序列 h 使得 A_i 的元素意义是以 i 为结尾的最长上升子序列的长度。

首先 A_i 一定满足 A_i \le (\max_{j<i} A_j)+1，我们猜测满足这个条件就一定合法。

:::info[Proof]{open} 合法的条件是，我们将偏序关系建图后，不存在环。

我们发现，这个偏序就是所有 j < j 且 A_j \ge A_i 的 j 的值都要大于 A_i，而需要存在一个 j<i 满足 A_j = A_i - 1，存在不好处理，加强限制后就是都要满足，你会发现这样连的边都是某个前缀 A_i\ge k 的所有 i 连向 A_i=k-1 的所有 j，这个关系显然是没有环的。 :::

然后去数满足条件的 A 即可，分类讨论原先是否合法，以及是否存在方案使得 B 合法。