题解：P3098 [USACO13DEC] The Bessie Shuffle G

a_cow_of_FJ · 2025-10-22 11:02:42 · 题解

来一发线性复杂度的做法。

思路

首先感性理解一下洗牌过程。

发现就是一个大小为 m 的滑动窗口，每次操作在其内部按规则打乱（我们称之为「置换」），并向下滑动一格。

若以这个滑动窗口为参照物，可以理解为是整个牌堆在向上移动。那么窗口内的第 i 张牌洗一次就会变成新窗口内的第 p_i-1 张牌，若 p_i-1=0 则出局。这样，我们得到了一个新的置换。

对于原牌堆中的第 i (m \le i \le n - m + 1) 张牌，它总是作为窗口的第 m 张牌进入，每次从 j 变为 p_j-1，直到变为 0 才从顶部离开。发现这个从 m 到 0 的过程，所经历的置换轮数是固定不变的，和第 i 张牌本身无关。

设这个轮数为 c，考虑处理某个询问 q_i。既然是临时堆中从上到下的第 q_i 张牌，必定是倒数第 q_i 个被淘汰的，它被淘汰时一定在 n-q+1 的位置。此时窗口位于其正下方，即 [n-q+2,n-q+m+1]。设这张牌是原来的第 x 张牌，因为它第一次进入窗口时位于窗口底部，所以窗口底部位于 x。因为到出局又经历了 c 轮变换，每变换一次窗口往下一格，因此得到方程

x + c = n - q + m + 1

意思时窗口底部本来位于 x ，经历 c 轮变换往下 c 格后该牌被洗出局，此时窗口底部位于 n-q+m+1。

解方程得 x=n-q+m+1-c。因为 n,m,q,c 都是已知常数，故答案可以 O(1) 快速回答。

但是，上述结论仅适用于从窗口底部进入，从顶部离开的牌，所以编号为 1 ~ m-1 和 n-m+2 ~ m 的牌不能这么计算。前者并非从底部进入；后者不一定从顶部离开。

于是下面考虑前 m-1 张牌和倒数 m-1 张牌如何处理。

先考虑前者。对于窗口内第 i (i \le m-1) 张牌，设其需要经历 d_i 次置换被淘汰。因为每次置换都会恰好淘汰一张牌，所以第 i 张牌一定是第 d_i 张被淘汰的，即临时堆中第 n-d_i+1 张牌编号为 i。

但是有个两个问题：

万一这张牌永远洗不掉，d_i=+\infty 时怎么办？
由于一共只洗 n-m+1 次，万一 n-m+1<d_i 怎么办？

这两种情况可以放在一起处理。这种情况下，每次洗牌该牌都会参与，即它会经历共 n-m+1 轮置换。我们直接计算出它经历 n-m+1 轮置换会到哪里，记录下来，回答时直接用就好了。

下面考虑如何处理倒数 m-1 张牌。由于它们也是从窗口底部进入，之前的 c 可以拿来直接用。显然倒数第 i 张牌最多经历 \min(n-m+1, i) 轮置换。这时分类讨论：当 c \le \min(n-m+1,i) 时，该牌会从窗口顶部淘汰，答案即为 n-q+m+1-c，不用处理；当 c > \min(n-m+1,i) 时，我们直接计算其经历 \min(n-m+1,i) 轮置换后的位置，记录下来供回答时使用即可。

到这里为止说的很抽象，可以接着往下看，

实现

在考虑代码之前，先考虑一下如果给置换 \sigma=(p_1-1)(p_2-1)\cdots(p_n-1) 建图，图长什么样。

显然除了 0 号点和 m 号点，所有点入度出度均为 1。而 0 号点入度为 1，出度为 0，m 号点相反。

容易发现，图由一条 m 到 0 的链和若干环组成。这也保证了窗口底部的牌总会被淘汰出局。

考虑把链和环记录到若干个 vector 中，并记 bel_i 为 i 所属于的 vector 编号，记 pos_i 为 i 在其属于的 vector 中的下标。特别地，我们把链存在 vec[1] 中，环存在 vec[2] 及以后，vec[1] 的首尾元素分别为 m,0。

这么做有如下好处：

可以用 vec[bel[i]][ pos[i] + x ] 方便地表示 i 经过 x 轮置换后的位置（前提是不越界）。
前文提到的 c 即为 vec[1].size()-1，d_i 即为 vec[1].size() - 1 - pos[i]。
若 bel[i]=1 则点 i 在链上，否则在环上，且 vec[bel[i]].size() 即为循环节。

下面贴高清无注释的代码：

参考代码

#include <iostream>
#include <vector>
using namespace std;

const int M = 1e5 + 5;
int n, m, pre[M], bel[M], pos[M], siz[M], cur;
vector<int> vec[M];
int res1[M], res2[M];

void prep() {
  for (int i = 0; i <= m; i++)
    if (!bel[i]) {
      vec[++cur].push_back(i);
      bel[i] = cur;
      for (int j = pre[i]; j && !bel[j]; j = pre[j]) {
        vec[cur].push_back(j);
        bel[j] = cur, pos[j] = vec[cur].size() - 1;
      }
    }
  for (int i = 1; i <= cur; i++) {
    siz[i] = vec[i].size();
    if (i > 1) {
      for (int j = 0; j < siz[i]; j++)
        vec[i].push_back(vec[i][j]), pos[ vec[i][j] ] += siz[i];
    }
  }
  for (int i = 1; i < m; i++) {
    if (bel[i] == 1 && pos[i] <= n - m + 1)
      res1[ pos[i] ] = i;
    else {
      int r = (n - m + 1) % siz[ bel[i] ];
      res2[ m - vec[ bel[i] ][ pos[i] - r ] ] = i;
    }
    if (min(i, n - m + 1) <= siz[1] - 1)
      res2[ m - vec[1][ siz[1] - 1 - min(i, n - m + 1) ] ] = n - i + 1;
  }
}

int query(int x) {
  if (x > n - m + 1 && res1[n - x + 1])
    return res1[n - x + 1];
  if (x < m)
    return res2[x];
  return n + m + 1 - siz[1] + 1 - x;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int q;
  cin >> n >> m >> q;
  for (int i = 1, x; i <= m; i++) {
    cin >> x;
    pre[x - 1] = i;
  }
  prep();
  while (q--) {
    int x;
    cin >> x;
    cout << query(x) << '\n';
  }
}

如果给这份代码加个快读就变成了次优解（至少目前是这样）。

完结撒花~~