专栏文章

题解：P10327 [UESTCPC 2024] 汉诺塔排序问题

MMoeebius
P10327题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipoaqph
此快照首次捕获于
2025/12/03 15:15
3 个月前
此快照最后确认于
2025/12/03 15:15
3 个月前
查看原文
这也太难了！！！！！！
本题解参考了 GD 省集的官方题解，但是官方题解过于晦涩难懂了，这是一个（可能）说人话的版本。
下文中的 AA 序列即题面中的 pp。
考虑将整个过程倒过来：一开始，BB 柱上有（从上到下）1∼n1 \sim n 的圆盘，我们要将其按照指定顺序挪到 AA 上。
不难发现，如果 AA 底部的圆盘归位了，我们之后一定不会再移动它，因为它并不会影响之后所有圆盘。因此，我们一定自底向上将 AA 排好，这是不劣的。
定义 posxpos_x 表示 ≥x\ge x 且未归位的元素个数。 定义 prexpre_x 表示 xx 在未归位圆盘中的（大小）前驱，nxtxnxt_x 表示其在未归位圆盘中的后继。
不妨假设我们要将 BB 中的某个圆盘挪到 AA 顶部。手玩可以发现，最优操作一定形如将 BB 和 CC 顶部的若干圆盘先归并到 AA，再全部挪到 CC（特别的，这些圆盘中最大的一个可以直接挪到 CC，从而节省一次操作）。这时我们要的圆盘已经在 BB 顶部了，我们将其直接挪到 AA。（从 CC 中取圆盘的流程同理。）
我们称一次这样的操作为基本操作。对于一次挪动了 kk 个额外圆盘（即操作结束后没有放置在 AA 上的圆盘）的基本操作，其额外代价（即挪动额外圆盘所需代价）为 2k−12k-1。总代价即为所有基本操作的额外代价之和加上 nn。定义一次基本操作的“下界”为 poslst−1pos_{lst}-1，其中 lstlst 表示该次基本操作移动的额外圆盘中最大的一个。
下图是一次基本操作的示例。
基本操作
考虑如何快速维护移动过程中的状态。观察到，一次基本操作对 B,CB,C 归并后形成的序列，影响只有删除这个序列中一个元素。此外，基本操作相当于“推平”了这个序列的一个前缀，将这个前缀中的所有元素依次放在某个栈顶部。
因此，我们可以尝试使用一个“虚栈” stst 实时维护“实栈” B,CB,C 归并后形成序列中的非平凡元素。具体来说，如果一个元素 xx 不在 stst 中，我们认为他和 prexpre_x 在同一个“实栈”中——显然，xx 在“实栈”中位于 prexpre_x 的正下方。虚栈初始为空。
假设 Ai=pA_i = p。于是，我们可以一直弹出“虚栈”中的元素，直到虚栈栈顶元素 xx 满足 posx≤posppos_x \le pos_p。假设弹出的元素中与 pp 位于同一“实栈”的最大的元素是 yy，那么这轮操作的额外代价是 2((n−i+1)−y+1)−12((n - i + 1) - y + 1) - 1……吗？
考虑如下 Hack：
A={3,5,2,1,4}A=\{3,5,2,1,4\}
考虑前两步，如果每轮都只操作“必须操作的位置”（即图 1），那么第二轮需要重新挪动 1,21,2 两个圆盘，最终比第一步操作到圆盘 44（图 2）多一次操作。
因此，我们不仅有可能新进行一次基本操作，还有可能“拓展”之前进行的基本操作。
我们不妨先不管这一点，观察基本操作对虚栈造成的影响。注意到，留在栈中的元素，其 pospos 是不会改变的，因此可以直接维护；每次弹栈结束后，pp 下方的元素状态会改变，可能造成一次入栈。
也就是说，我们至少需要给虚栈中元素两个属性：pospos 和 diffdiff，后者表示该元素和 prexpre_x 是否在同一个实栈中。
现在考虑可能拓展已有操作的情形，我们还要额外维护一个属性 tagtag，定义为可以拓展到该元素的基本操作的最小下界。
弹栈时维护一个变量 tag′tag'，表示目前可以拓展到栈顶的基本操作的最小下界。同时维护这一轮操作的最小额外代价 curcur。
不难发现，假设要拓展已有操作将栈顶元素上方（不含栈顶）元素清空，就相当于让 curcur 加上 2(tag′−pos)2(tag'-pos)。
对于栈顶元素 pos>posppos > pos_p 的情形：
先令 tag′←min⁡{tag′,tag}tag' \gets \min\{tag', tag\}。
  • 如果其 diff=truediff = \text{true}，则意味着其前驱必须成为额外圆盘。此时，拓展已有操作的代价是 cur+2(tag′−pos)cur+2(tag'-pos)，将这轮的额外操作设为到 nxt(pos)nxt(pos) 为止的代价是 max⁡{0,2(n−i+1−pos)−1}\max\{0,2(n-i+1-pos)-1\}，取。无论如何，操作完成之后 tag′tag' 都会变为 pospos。
  • 否则，则意味着我们可以暂时不用管该元素。
处理结束后，弹出栈顶。
弹栈结束后，考虑栈顶元素。
  • 如果其 pos=posppos=pos_p：
    先令 tag′←min⁡{tag′,tag}tag' \gets \min\{tag', tag\}。
    • 如果其 diff=truediff = \text{true}，我们不用管，因为这意味着 pp 上方的元素已经清空了；
    • 否则，其前驱必须成为额外圆盘，处理方法同上。
    处理结束后，弹出栈顶。
  • 否则，相当于上面 diff=falsediff = \text{false} 的情形，同样令其前驱成为额外圆盘。注意此时 tag′tag' 不会减小。
最后，由于基本操作将所有额外圆盘归并到了与 pp 不同的实栈上，考虑目前的栈顶元素：
  • 如果其 pos=posp−1pos=pos_p-1，将 diff←diff⊕1diff \gets diff \oplus 1。
  • 否则 posp−1pos_p-1 位置对应的元素变得非平凡，插入一个 pos=posp−1,tag=tag′,diff=1pos = pos_p - 1, tag = tag', diff = 1 的新元素。
不难验证其正确性。
综上，我们解决了本题，时间复杂度 O(nlog⁡n)O(n \log n)，瓶颈在使用树状数组求 posppos_p。代码比较好写。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...