P9492 「SFCOI-3」进行一个拆的解 题解

liruixiong0101 · 2023-08-04 21:22:37 · 题解

P0 题意：

给定一个长度为 n 的数组 a_1,a_2,\dots,a_n，请问是否有一个数 l（l\in[1,n)），[1,l] 为 [l+1,n] 子序列，或 [l+1,n] 为 [1,l] 的子序列，若有所有的 l 都合法输出 NO 否则输出 YES。

P1 思路：

1.暴力：

暴力思路很明显，枚举 l，再 O(n) 判断这个 l 是否合法即可，判断 l 是否合法可以用双指针实现。

2.正解：

我们来自己手算一下第一个样例，我们会发现当 l\ge \lfloor \frac{n}{2} \rfloor 时，每一个 l 都可行，为什么呢？

• 当 l=3 时，两个序列分别为 1 2 1 和 2 1，此时 2 1 为 1 2 1 的子序列。
• 当 l = 4 时，两个序列分别为 1 2 1 2 和 1，此时第一个序列增加了一个 2，而第二个序列减少了一个 2，1 也为 1 2 1 2 的子序列。

研究完样例，我们很容易发现一个性质：
若 b 序列为 a 序列的子序列，那么在 b 序列中去掉一个元素 c，在 a 序列中增加此元素 c， b 序列还为 a 序列的子序列。

我们从子序列的定义入手：

若一个序列 a 可以通过删除任意数量元素（可以为 0 个），从而让序列 a 变为另一个序列 b，那么称 b 为 a 的子序列。

很明显，我们在 b 序列中删除元素不会影响 b 为 a 的子序列这一条件，同样，我们在 a 序列中增加一个元素也不会影响此条件。这样我们得到了上述性质：若 b 序列为 a 序列的子序列，那么在 b 序列中去掉一个元素 c，在 a 序列中增加此元素 c， b 序列还为 a 序列的子序列。

同理，我们可以得出一下结论：

• 若 l=\lfloor\frac{n}{2}\rfloor 时，这个 l 成立，那么 l\ge\lfloor\frac{n}{2}\rfloor 所有的 l 都成立。
• 若 l=\lceil\frac{n}{2}\rceil 时，这个 l 成立，那么 l\le\lceil\frac{n}{2}\rceil 所有的 l 都成立。

所以我们只需判断 l=\lfloor\frac{n}{2}\rfloor 和 l=\lceil\frac{n}{2}\rceil 的 l 是否合法即可，判断 l 是否合法与暴力判断相同。

P3 代码：

代码很简单，这里只提供 AC 记录了。
https://www.luogu.com.cn/record/119061135