P11282 题解

lmh_qwq · 2024-11-16 18:49:57 · 题解

一些题外话：赛时 20min 把这题秒了，加上 1A 共耗时 33min。坏消息是报名太晚，痛失首杀。最后 Div1 rk7，一分钱没拿到。

题目中把操作方式写得很抽象，实际上它等价于：每次选择排列中连续的三个数，将它们删除，并在原位放上它们的最小值或者最大值。

对排列 p 中每一个数单独处理。假设我们目前在处理位置 x 上的数，则令数列 {a_i} 为：

那么显然原先的操作可以直接套用到现在的序列上，我们的目标是最后剩下的数是原序列中唯一的那个 1。此时，这个 1 只能和两个 0 或者两个 2 操作。

Part 1：x\equiv0\pmod 2

现在考虑一个只有 0 和 2 的长度为奇数的序列，对它操作可以得到什么结果。

注意到对三个 0 进行一次操作只能变成 0，对三个 2 进行一次操作只能变成 2，但是如果三个数中同时有 0 和 2，就可以变成任意一个。

这样我们发现，只要这个序列中有 0，就一定存在一种操作方法使得这个序列变成 0。2 同理。

如果 x\equiv 0\pmod 2，那么它两边的数列长度都为奇数。只要两边都能变成 0 或都能变成 2，那么就有解。

否则，只可能是一边全是 0，另一边全是 2。这样的话，出现对 0,1,2 进行操作就废了。然而，每次操作会减少 2 个数，而左边（不妨这样假设）0 的个数和右边 2 的个数都是奇数，因此无法在不进行 0,1,2 的操作且不把 1 搞没的前提下去掉所有的 0，因而无解。

维护前后缀最大最小值即可，时间复杂度 O(n)。

Part 2：x\equiv 1\pmod 2

下证明：长度大于 2 且长度为偶数的由 0 和 2 组成的数列可以通过操作变成两个相等的数。

假设数列第一个数为 0，由之前对奇数长度数列性质的推导，只要后面有 0，就可以把去掉第一个数的部分变成 0。否则，后面全部都是 2，但数列长度大于 2，那么此时对去掉最后一个数的部分操作使其变成 2，就会剩下两个相同的数。

所以，如果 x\ne 3 且 x\ne n-2，那么它两段的序列长度要么是 0，要么 >2，可以变成两个相同的数然后和中间的 1 操作把它留下来。

下只考虑 x=3 的情况。x=n-2 同理。

不妨假设 n\ge 7，此时 x 右边的序列长度 >2。n=3 和 n=5 的情况是类似的，最后会给出结论。

如果 (a_1,a_2,a_3)=(0,0,1) 或 (2,2,1)，那么把序列后半部分变成两个相同的数，显然有解。

否则，不妨设 (a_1,a_2,a_3)=(0,2,1)。显然我们不能对 a_1,a_2,a_3 进行操作，所以必定有一次操作是对 2,1,2 进行，此时 a_4=2。之后我们肯定还有一次对 0,1,0 进行的操作。

也就是说，我们必须从后面凑出一个 2 和一个 0。假设 p\le n+1 为最小的使得 \max_{i=4}^p{a_i}=2 的偶数（令 a_{n+1}=2），那么 a_4\sim a_p 的子序列长度为奇数，显然可以凑出一个 2。（这里 p=n+1 是个 corner case，不过不要紧，后面会把这种情况排除掉）

同时，由于 p 是最小的满足条件的偶数，所以把 a_4\sim a_{p-2} 合并凑不出 2，把 a_4\sim a_{p+2} 合并不优。现在，我们还需要在 a_{p+1}\sim a_n 中凑出一个 0。这个判断是简单的。

由此，我们解决了 n\ge 7 的情况。

当 n=3 或 n=5，x=3 时，有如下结论：