自动搬运

查看原文

来自洛谷，原作者为

	liruixiong0101 当我们身陷无尽黑暗，不妨努力绽放光亮，搏一搏，让别人看到我们身上的微光，这是给予彼此的希望。

搬运于2025-08-24 22:48:52，当前版本为作者最后更新于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