1106联考题解

T1

This problem is from previous Codeforces rounds. link

This problem is original. Credits to @Legendary_Noxus for crafting this problem. Hope everyone enjoy.

对于

n\le 8

的情况，我们可以使用 BFS 暴力求出答案，状态数为

8!

。可以通过搜索证明答案

\le 6

。

对于

n>8

的情况，我们维护包含

M=\lfloor\dfrac{1+n}{2}\rfloor

的值域连续段。设连续段的元素分别为

L,L+1,L+2,\ldots,R-1,R (L\le M\le R)

。

具体地，我们先找到

M

的位置，并使用

1

次操作将其移动到序列最前方。

接下来，我们重复以下操作：

如果当前包含 $M$ 的连续段在序列的开头，我们找到 $L-1$ 的位置，令其为 $p$ 。操作 $l=R-L+1,r=n-p$ 将会把当前连续段放在 $L-1$ 的右边，使新的连续段成为 $L-1,L,L+1,\ldots,R-1,R$ 。并且，操作完成后，新的连续段在序列末尾。
如果当前包含 $M$ 的连续段在序列的末尾，我们找到 $R+1$ 的位置，令其为 $p$ 。操作 $l=p-1,r=R-L+1$ 将会把当前连续段放在 $R+1$ 的左边，使新的连续段成为 $L,L+1,L+2,\ldots,R-1,R,R+1$ 。并且，操作完成后，新的连续段在序列开头。

我们重复该操作，直到连续段大小为

n-7

。此时我们可以把连续段看成一个整体，然后将原序列看成一个长度为

8

的序列，并使用 BFS 进行最后的求解。

显然，当

M=\lfloor\dfrac{1+n}{2}\rfloor

时，

1<L\le M\le R<n

在操作结束前恒成立，因此以上步骤是良定义的。

最开始可能会使用

1

次操作。连续段大小每操作一步都会增加

1

，在连续段大小为

n-7

时会使用

n-8

次操作。最后长度为

8

的序列至多需要

6

次操作。总操作数至多为

1+n-8+6=n-1

。

This problem is from previous Codeforces rounds. link

This problem is from previous Codeforces rounds. link