题解：P12848 [蓝桥杯 2025 国 A] 游戏

关于本题，有一个重要的结论：答案一定不超过

2

，评测用例规模与约定中隐约暗示了这一点。

该结论的证明如下：

若 $n < 3$ ，结论显然正确。
若 $n \ge 3$ ，在 $(1, n)$ 间连一条边，在 $(n - 2, n)$ 间连一条边。于是游戏一定有解：
- $(1, n)$ 的边可以用于将整个序列循环移位：全体序列向右移动一次，然后将位置 $n$ 的石块移动到位置 $1$ 。
- $(n - 2, n)$ 的边可以用于将 $n - 2$ 位置和 $n - 1$ 位置的石块互换位置，实际上就是一个长度为 $2$ 的循环移位。
- 基于上述两种操作，我们可以实现交换任意两个相邻的石块的操作。只需将它们循环位移到最后，然后交换即可。
- 能交换任意两个相邻元素意味着可以对任意序列进行排序。

既然答案有且仅有

0, 1, 2

，我们可以分类讨论：

答案为

0

当且仅当序列已经有序，因为不加边就不能改变序列。

否则，答案为

1

当且仅当存在一个区间，对其进行循环位移后全体序列有序。

充分性：令该区间为 $[x, y]$ ，我们可以连接 $(x, y + 1)$ ，将 $[y + 1, n - 1]$ 区间的石块右移一次，然后对目标区间做循环移位。
必要性：对于我们连接的一条边 $(x, y)$ ， $[1, x - 1]$ 和 $[y, n - 1]$ 位置的石块不可能改变在序列中的位置，且 $[x, y - 1]$ 区间内只能够循环移位。
如何找到这个可能的区间呢？区间外一定有 $a_i = i$ ，区间内一定有 $a_i \ne i$ ，只要找到第一个和最后一个位置不正确的石块，检查该区间是否可以通过循环移位变得有序即可。

否则答案为

2

。

文章操作