P9185 [USACO23OPEN] Rotate and Shift B 题解

HyB_Capricornus · 2023-04-05 22:28:51 · 题解

还没有人发题解，我来一发。

Sol

设原序列为 B。

令操作 C 为将 B_{A_1} 挪至 B_{A_2}，将 B_{A_2} 挪至 B_{A_3}，\ldots，将 B_{A_n} 挪至 B_{A_1}。

令操作 -x 为将序列逆时针转 x 次，即 B_1 \to B_2，B_2 \to B_3，\ldots，B_n \to B_1。

令操作 +x 为将序列顺时针转 x 次。

重点来了：

我们可以把将 A 向后挪再进行 C 操作想成先将 B 逆时针转 1 次，然后进行 C 操作，然后再顺时针转回去

当然每次转的次数不同，例如进行两次将 A 向后挪再进行 C 操作，我们就需要逆时针转 2 次，然后进行 C 操作，然后再顺时针转回去

则操作为：

C,-1,C,+1,-2,C,+2,-3,C,+3,\ldots,-(n-1),C,n-1

其中 + 与 - 可以抵消，抵消后结果为：

C,-1,C,-1,C,-1,\ldots,C,-1,C,n-1

C,-1,C,-1,C,-1,\ldots,C,-1,C,-1,n

我们称 C,-1 为 D 操作

我们创建数组 jmp[i][j]，其中 jmp[i][j]=d 表示进行 2^j 次 D 操作把 b_i 挪到了 d 位置。

通过倍增，原始暴力的复杂度 O(nT) 成功优化到 O(n\log_{2}{T})，复杂度显然可以通过本题。

最后不要忘了顺时针转 n 次，这道题目就做出来了。