2019-ICPC-南昌网络赛-E
2019-09-08 / Luo Jinrong   

E. Magic Master

题意

一共有N张牌，要以某种规则将牌从1到N按顺序取出来，Q个询问，问初始牌的排列中第K张牌是什么。抽牌规则如下：

  • 将顶部的一张牌取出。
  • 将顶部的一张牌放至底部，重复M次。
  • 重复上述操作直到所有牌被取出。

做法

构造。我们考虑一般情况，在初始状态下，一部分牌的初始位置是容易得到的，即从第一张开始往后每隔m张牌（下标分别为1,(m+1)*1+1,(m+1)*2+1…）依次是1,2,3…我们暂且称这些数为已知数，其他为未知数，当我们恰好把所有已知数全部取出来之后（最后一个已知数取出但还没进行M次顶部到底部操作），牌的组合顺序为原排列中最后一个已知数后面的所有未知数+原排列中最后一个已知数前面的所有未知数，这样我们可以简单的得到我们要求的第k个数在这个序列里面排在第几个。然后再做M次顶部到底部的操作，再转化一下我们要求的那个位置在这个串中的下标。这样就转化出了一个原问题的子问题，就可以通过递归实现了，当我们所要求的位置恰好为已知数的时候就可以返回了。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,n,m,q,k;
ll dfs(ll len,ll pos){
    if(pos%(m+1)==1){
        return pos/(m+1)+1;
    }
    ll newp,pp=pos-((pos-1)/(m+1)+1),base=(len-1)/(m+1)+1,newl=len-base,lef=len-(base-1)*(m+1)-1;
    pp=(pp+lef-1)%newl+1;
    newp=(pp-m-1+20*newl)%newl+1;
    return base+dfs(newl,newp);
}
int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>n>>m>>q;
        while(q--){
            cin>>k;
            cout<<dfs(n,k)<<"\n";
        }
    }
}

return 0;

本文链接：
https://luojinrong.github.io/2019/09/08/2019-ICPC-南昌网络赛-E/