[UESTCPC 2024] 汉诺塔排序问题

Luogu

IDLGP10327

Time2000ms

Memory512MB

DifficultyP7

2024O2优化高校校赛

Natsuzora 在玩一个特殊规则的汉诺塔。汉诺塔有 $A$、$B$、$C$ 共三根柱子，每根柱子上可以堆叠放置圆盘。圆盘可以在不同柱子之间移动，但必须遵守以下规则： - 一次只有一个圆盘被移动； - 每次移动只能将一个柱子最顶端的圆盘移动到另一个柱子的最顶端； - 在柱子 $B$ 和 $C$ 上，不允许任何圆盘放置在另外一个比它本身小的圆盘上； - **在柱子 $A$ 上，允许将较大的圆盘放置在较小的圆盘上。** 最开始时，Natsuzora 将 $n$ 个大小互不相同的圆盘乱序地摞在 $A$ 柱子上并将柱子 $B$ 和 $C$ 留空。在满足上述条件的情况下，Natsuzora 想要知道，若要将 $A$ 柱上的圆盘全部移动到 $B$ 柱上，他至少需要进行多少次移动。 ## Input 第一行包含一个整数 $T$ $(1\leq T\leq 10^4)$，表示数据组数。每组数据的第一行包含一个整数 $n$ $(1\leq n\leq 10^5)$，表示初始状态下柱子 $A$ 上的圆盘数量。每组数据的第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$ $(1\leq p_i\leq n)$，其中 $p_i$ 表示柱子 $A$ **从下往上**第 $i$ 个圆盘的直径。数据保证 $p_1,p_2,\ldots,p_n$ 是一个长度为 $n$ 的排列，即 $1$ 到 $n$ 中的每个整数都在序列中出现恰好一次。对于所有数据，保证 $\sum n\leq 2\times 10^5$。 ## Output 对于每组数据，输出一行一个整数，表示需要的最少移动次数。 [samples] ## Note 在第一个样例中，一种可行的次数最少的移动方案如下（$X\rightarrow Y$ 表示将柱子 $X$ 最顶上的圆盘移动到柱子 $Y$ 的顶部）： 1. $A\rightarrow C$ 2. $A\rightarrow B$ 3. $A\rightarrow C$ 4. $B\rightarrow C$ 5. $A\rightarrow B$ 6. $C\rightarrow A$ 7. $C\rightarrow A$ 8. $C\rightarrow B$ 9. $A\rightarrow B$ 10. $A\rightarrow B$ 11. $A\rightarrow B$

Samples

Input #1

3
5
1 5 3 2 4
5
1 2 3 4 5
6
5 3 6 1 4 2

Output #1

11
5
19

API Response (JSON)

{
  "problem": {
    "name": "[UESTCPC 2024] 汉诺塔排序问题",
    "description": {
      "content": "Natsuzora 在玩一个特殊规则的汉诺塔。 汉诺塔有 $A$、$B$、$C$ 共三根柱子，每根柱子上可以堆叠放置圆盘。圆盘可以在不同柱子之间移动，但必须遵守以下规则： - 一次只有一个圆盘被移动； - 每次移动只能将一个柱子最顶端的圆盘移动到另一个柱子的最顶端； - 在柱子 $B$ 和 $C$ 上，不允许任何圆盘放置在另外一个比它本身小的圆盘上； - **在柱子 $A$ 上，允许将较大的圆",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10327"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Natsuzora 在玩一个特殊规则的汉诺塔。\n\n汉诺塔有 $A$、$B$、$C$ 共三根柱子，每根柱子上可以堆叠放置圆盘。圆盘可以在不同柱子之间移动，但必须遵守以下规则：\n\n- 一次只有一个圆盘被移动；\n- 每次移动只能将一个柱子最顶端的圆盘移动到另一个柱子的最顶端；\n- 在柱子 $B$ 和 $C$ 上，不允许任何圆盘放置在另外一个比它本身小的圆盘上；\n- **在柱子 $A$ 上，允许将较大的圆...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments