题解：P11463 N角进攻

TLE_Automat · 2024-12-24 15:18:12 · 题解

这里是官方题解。

可以将序列分为三个部分，左边 \lfloor \frac{n}{2} \rfloor 个，右边 \lfloor \frac{n}{2} \rfloor 个，最中间的 1 个。

容易观察到，进行恰好 n 次传球后，左边的部分会完全翻转到右边，而右边的部分也会完全翻转到左边，而最中间的元素不变，相当于对原序列进行了 \operatorname{reverse} 操作，所以进行 2n 次传球后序列会变为跟初始时一样，所以我们可以将先 k 对 2n 取模。

之后在 \Theta(n) 的时间复杂度内暴力模拟题目中的传球操作即可通过。

模拟的方式有很多，这里提供一种模拟方式：

首先开两个数组或者两个双端队列，再开一个变量记录最中间的值，分别模拟左边的部分和右边的部分。

• 如果当前操作为向左传球，则将中间元素插入到左边的队首，新的中间元素设置为左边的队尾并将其弹出。
• 如果当前操作为向右传球，则将中间元素插入到右边的队尾，新的中间元素设置为右边的队首并将其弹出。