自动搬运

查看原文

来自洛谷，原作者为

	HyB_Capricornus 黄梅时节家家A，青草池塘处处WA，有WA不A过夜半，闲切红题冒火花

搬运于2025-08-24 21:45:16，当前版本为作者最后更新于2023-01-02 18:30:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本蒟蒻居然 AC 了紫题

本蒟蒻就把自己的思考过程写一下：

首先，本人想到了如果题面改为如下：

有 $m$ 张牌，进行 $n$ 次贝西洗牌A，求最后牌的顺序。

对于这个问题，我们可以很容易想到倍增。

倍增预处理

我们定义 $f_{i,j}$ 为从第 $i$ 次变换开始变换 $2^j$ 的序列，并且可以用求 LCA 的方法知道倍增预处理方法：

套倍增

但是如果换为题面，我们需要在每次交换时取出第一个，这个无法预处理，我们就无法用二进制拆分 $O(log_2n)$ 的解决，退化成了 $O(n)$ 了。

但是我们怎么把原始序列往里套呢？

下面给出我的方法，强烈建议先自行思考再阅读本文。

若还需要倍增，就需要通过长度为 $m$ 的 $p$ 序列构造长度为 $n$ 的 $q$ 序列，那么我们可以用时3天想到将已经取出的元素放置序列末尾。

我们可以如此构造 $q$ 序列：

• 对于 $i \in [1,m]$，$q_i=p_i-1$，其中 $p_i=1$ 的移到队尾：$n$。

• 对于 $i \in [m+1,n]$，我们仅需向前挪，及 $p_i=i-1$。

代码

本人给出本人被卡的地方，警示后人 (给个赞呗)。

1. 请注意本题是一个牌堆，相当于一个栈，所以牌堆最后的顺序是反着的。

2. 建议先将临时牌堆的数据存储下来，再 $O(1)$ 输出。 (本人不知为何 WA)

3. 注意题目中不足 $m$ 张时要依次放到牌堆上。(本人被卡无数次)