P3098 [USACO13DEC] The Bessie Shuffle G
2026-09-09
题解
顺推难以考虑,正难则反,看看怎么逆推处理。
我们发现 A 洗牌的逆推可以定义为 pre[p[i]]=i。
而 B 洗牌则是对于当前位置 x,先洗到 p[x],再拿走一张变到 p[x]−1,确实可以直接倒过来,但是我们发扬人类智慧,考虑最后一次洗牌前的位置,也就是上一轮拿完以后,这一轮洗牌以前。
假设当前位置为 s,这次洗牌后为 pre[s],加上拿走的一张就是 pre[s]+1。
这样就可以使用倍增了。
最终的第 x 张牌实际上是第 n−x+1 被淘汰的牌,找到其在洗后、淘汰前的位置,也就是 x<m 时为 m−x+1;否则为 1。
我们还需要知道最大的倍增轮数,不洗时最多 n−m,洗时被淘汰为 n−x,只需要取最小值即可。
如果倒推过程中牌出了洗牌区域呢?容易发现倒推时,每向前一轮如果不洗牌只会导致一直加牌,也就是位置始终 >m,此时可以二分一下出洗牌区最小次数 l,剩余轮数减去 l 加上 m+1 即为原位置。
如果没有出洗牌区域,只需要再取一次 pre[x] 即可。
