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

InterRiver · 2025-06-16 23:40:22 · 题解

关于本题，有一个重要的结论：答案一定不超过 2，评测用例规模与约定中隐约暗示了这一点。

该结论的证明如下：

• 若 n < 3，结论显然正确。

• 若 n \ge 3，在 (1, n) 间连一条边，在 (n - 2, n) 间连一条边。于是游戏一定有解：

  • 基于上述两种操作，我们可以实现交换任意两个相邻的石块的操作。只需将它们循环位移到最后，然后交换即可。
  • 能交换任意两个相邻元素意味着可以对任意序列进行排序。

既然答案有且仅有 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。