专栏文章

题解：P3098 [USACO13DEC] The Bessie Shuffle G

aa_cow_of_FJ
P3098题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minjcixq
此快照首次捕获于
2025/12/02 03:21
3 个月前
此快照最后确认于
2025/12/02 03:21
3 个月前
查看原文
来一发线性复杂度的做法。

思路

首先感性理解一下洗牌过程。
发现就是一个大小为 mm 的滑动窗口，每次操作在其内部按规则打乱（我们称之为**「置换」**），并向下滑动一格。
若以这个滑动窗口为参照物，可以理解为是整个牌堆在向上移动。那么窗口内的第 ii 张牌洗一次就会变成新窗口内的第 pi−1p_i-1 张牌，若 pi−1=0p_i-1=0 则出局。这样，我们得到了一个新的置换。
对于原牌堆中的第 ii (m≤i≤n−m+1m \le i \le n - m + 1) 张牌，它总是作为窗口的第 mm 张牌进入，每次从 jj 变为 pj−1p_j-1，直到变为 00 才从顶部离开。 发现这个从 mm 到 00 的过程，所经历的置换轮数是固定不变的，和第 ii 张牌本身无关。
设这个轮数为 cc，考虑处理某个询问 qiq_i。既然是临时堆中从上到下的第 qiq_i 张牌，必定是倒数第 qiq_i 个被淘汰的，它被淘汰时一定在 n−q+1n-q+1 的位置。此时窗口位于其正下方，即 [n−q+2,n−q+m+1][n-q+2,n-q+m+1]。设这张牌是原来的第 xx 张牌，因为它第一次进入窗口时位于窗口底部，所以窗口底部位于 xx。因为到出局又经历了 cc 轮变换，每变换一次窗口往下一格，因此得到方程
x+c=n−q+m+1x + c = n - q + m + 1
意思时窗口底部本来位于 xx ，经历 cc 轮变换往下 cc 格后该牌被洗出局，此时窗口底部位于 n−q+m+1n-q+m+1。
解方程得 x=n−q+m+1−cx=n-q+m+1-c。因为 n,m,q,cn,m,q,c 都是已知常数，故答案可以 O(1)O(1) 快速回答。
但是，上述结论仅适用于从窗口底部进入，从顶部离开的牌，所以编号为 11 ~ m−1m-1 和 n−m+2n-m+2 ~ mm 的牌不能这么计算。前者并非从底部进入；后者不一定从顶部离开。
于是下面考虑前 m−1m-1 张牌和倒数 m−1m-1 张牌如何处理。
先考虑前者。对于窗口内第 ii (i≤m−1i \le m-1) 张牌，设其需要经历 did_i 次置换被淘汰。因为每次置换都会恰好淘汰一张牌，所以第 ii 张牌一定是第 did_i 张被淘汰的，即临时堆中第 n−di+1n-d_i+1 张牌编号为 ii。
但是有个两个问题：
  1. 万一这张牌永远洗不掉，di=+∞d_i=+\infty 时怎么办？
  2. 由于一共只洗 n−m+1n-m+1 次，万一 n−m+1<din-m+1<d_i 怎么办？
这两种情况可以放在一起处理。这种情况下，每次洗牌该牌都会参与，即它会经历共 n−m+1n-m+1 轮置换。我们直接计算出它经历 n−m+1n-m+1 轮置换会到哪里，记录下来，回答时直接用就好了。
下面考虑如何处理倒数 m−1m-1 张牌。由于它们也是从窗口底部进入，之前的 cc 可以拿来直接用。显然倒数第 ii 张牌最多经历 min⁡(n−m+1,i)\min(n-m+1, i) 轮置换。这时分类讨论：当 c≤min⁡(n−m+1,i)c \le \min(n-m+1,i) 时，该牌会从窗口顶部淘汰，答案即为 n−q+m+1−cn-q+m+1-c，不用处理；当 c>min⁡(n−m+1,i)c > \min(n-m+1,i) 时，我们直接计算其经历 min⁡(n−m+1,i)\min(n-m+1,i) 轮置换后的位置，记录下来供回答时使用即可。
到这里为止说的很抽象，可以接着往下看，

实现

在考虑代码之前，先考虑一下如果给置换 σ=(p1−1)(p2−1)⋯(pn−1)\sigma=(p_1-1)(p_2-1)\cdots(p_n-1) 建图，图长什么样。
显然除了 00 号点和 mm 号点，所有点入度出度均为 11。而 00 号点入度为 11，出度为 00，mm 号点相反。
容易发现，图由一条 mm 到 00 的链和若干环组成。这也保证了窗口底部的牌总会被淘汰出局。
考虑把链和环记录到若干个 vector 中，并记 belibel_i 为 ii 所属于的 vector 编号，记 posipos_i 为 ii 在其属于的 vector 中的下标。特别地，我们把链存在 vec[1]vec[1] 中，环存在 vec[2]vec[2] 及以后，vec[1]vec[1] 的首尾元素分别为 m,0m,0。
这么做有如下好处：
  1. 可以用 vec[bel[i]][pos[i]+x]vec[bel[i]][ pos[i] + x ] 方便地表示 ii 经过 xx 轮置换后的位置（前提是不越界）。
  2. 前文提到的 cc 即为 vec[1].size()−1vec[1].size()-1，did_i 即为 vec[1].size()−1−pos[i]vec[1].size() - 1 - pos[i]。
  3. 若 bel[i]=1bel[i]=1 则点 ii 在链上，否则在环上，且 vec[bel[i]].size()vec[bel[i]].size() 即为循环节。
下面贴高清无注释的代码：

参考代码

CPP
#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';
  }
}
如果给这份代码加个快读就变成了次优解（至少目前是这样）。
完结撒花~~

评论

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

正在加载评论...