题解：P17273 [eJOI 2026] Automata

Register_int · 2026-09-27 13:23:19 · 题解

场了记录一下。放 NOIP T2 还是有点太高看我了，做了一百万年。

一个观察就是 K>2 和 K=2 没有区别，只要你最左和最右的两个点能靠起来就够了，中间的不用管。接下来只考虑两个点的情况。

观察走的过程，我们将这些结构定义为“单向阀”：

特别地，假装序列的边界也存在单向阀。

那么我们考虑要让 l,r 走到一起要满足什么条件。若两个点之间没有任何单向阀，或者单向阀全部同向，那么只要让一边不断靠过去即可，必然有解。否则，单向阀一定形如 \cdots\to\to\to\gets\gets\gets\cdots，能靠到最中间就赢了。继续分类讨论：

• 若 l 和 r 到中间的第一段路同为递增或递减，那么必然可以先把两个点卡在最近的单向阀的位置，然后任意挪动，必然有解。
• 若 l 的左侧是 \to，那么 l 已经被卡住，可以再把 r 卡到中间去，然后移动 l，必然有解。
• 若 r 的右侧是 \gets，同理也有解。
• 否则，此时形如 \gets l\to\cdots\gets r\to。设 l 到左右两侧的距离为 ax,ay，r 到左右两侧的距离为 bx,by。那么我们要想办法让一侧不卡出去的同时把另一个点卡进来，相当于要求 ax>bx 或 ay<by 成立，否则无解。

以上就是所有情况，实现只需要找上一个或下一个 \to 或 \gets，直接二分做到 \mathcal{O}(n\log n)，预处理所有位置的前驱后继即可做到 \mathcal{O}(n)。