列表 题解

浩瀚星空里
只剩你的背影
银河已凝结成冰
记忆滑过泪滴
想象能回到过去
终会存在我心底
虽然逃避
她消失在梦里
日出的幻境
再次感觉到你
风送来你的呼吸
月色倒映着惊喜
原来你从未离去
默默守护在这里
无声无息
如影随形
我不再迷茫
思念是唯一的行囊
漫天的星光
有一颗是你的愿望
前方的路不再孤单漫长
天空下你我不再守望
轻声歌唱
在我身旁
日出的幻景
再次感觉到你
风送来你的呼吸
月色倒映着惊喜
原来你从未离去
默默守护在这里
无声无息
如影随形
我不再迷茫
思念是唯一的行囊
漫天的星光
有一颗是你的愿望
前方的路不再孤单漫长
天空下你我不再守望
轻声歌唱
在我身旁
我不再迷茫
思念是唯一的行囊
漫天的星光
有一颗是你的愿望
前方的路不再孤单漫长
天空下你我不再守望
轻声歌唱
在我身旁

其实昨天顶真就让写了，但一直没时间，今天补上来得及吗 QwQ？

但好像就算写了也基本没人看的懂。

首先先考虑题面在干啥，相当于是先选最中间的，如果删掉左边一个，就选一个右边，如果删掉右边一个就选上左边。

显然答案具有单调性，考虑二分区间长度，枚举左端点 \(L\)，将在答案区间的点在原序列标记成 \(1\)，否则是 \(0\)。

于是问题转化为如何判断是否能取到所有 \(1\)。

考虑双指针 \(l,r\) ，初始时 \(l=n\) 和 \(r=n+2\) 处，表示下一次可能选的值，显然每次是尽可能删掉近的 \(0\)，且不能删 \(1\)，考虑若 \(l,r\) 中有一个是 \(0\)，则一定是删掉 \(0\) 使得 \(l,r\) 同时向左右跳一个，若是都是 \(1\)，就是删掉左边或右边最近的一个，使另一边跳一个，容易发现删掉左边和右边是一样的，最后跳到头证明都能取，否则一定有一组 \(1\) 卡住了不能都取。

模拟即可达到 \(O(n)\) 的复杂度。

考虑优化，发现在枚举 \(L\) 时每次只会增删一个值，考虑动态维护判断。

首先发现在都是 \(1\) 时指针的跳动不对称，考虑改变操作，变为将最近的 \(0\) 变成 \(1\)，两边同时跳一个，容易发现其剩余对于序列没有变化。

于是将两边一起考虑，当值是 \((0,0),(0,1),(1,0)\) 时直接跳，当值是 \((1,1)\) 时要将后面一个 \(0\) 变成 \(1\)。

发现只有 \((1,1)\) 可能会卡住，考虑 \((0,1)\) 改掉一个 \(0\) 会变成 \((1,1)\)，并不会有贡献，\((1,0)\) 同理，只有 \((0,0)\) 可以消掉一个。

设 \((1,1)\) 的贡献为 \(1\)，\((0,0)\) 的贡献是 \(0\)，因为大于 \((1,1)\) 个数的 \((0,0)\) 不会有贡献，于是问题变成了从前往后依次加，动态对 \(0\) 取 \(max\)。

这是一个经典问题，考虑 冲刺CSP联训模拟2——星空遗迹 的做法，将对 \(0\) 取 \(\max\) 拆掉，问题变成最后是依次加的历史最小值，可以线段树上二分，也可以维护前缀和后区间加区间 \(\min\)。