P3095 [USACO13DEC]The Bessie Shuffle S 题解

HyB_Capricornus · 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 张时要依次放到牌堆上。(本人被卡无数次)