Magic Master【模拟/约瑟夫环】

题意：

求原序列。
题目链接：https://nanti.jisuanke.com/t/41352

分析：

（1）双端队列逆向模拟，复杂度 (O(N*M))。

代码：

#include<bits/stdc++.h>

using namespace std;
const int N=4e7+10;
deque<int>dq;
int p[N];
int main()
{
    int t,n,m,q,k;
    scanf("%d",&t);
    while(t--)
    {
        int cnt=0;
        scanf("%d%d%d",&n,&m,&q);
        dq.push_front(n);
        for(int i=n-1;i>=1;i--)
        {
            dq.push_front(i);
            if(i==1) continue;
            for(int j=1;j<=m;j++)
            {
                int tmp=dq.back();
                dq.pop_back();
                dq.push_front(tmp);
            }
        }
        while(!dq.empty())
        {
            p[++cnt]=dq.front();
            dq.pop_front();
        }
        while(q--)
        {
            scanf("%d",&k);
            printf("%d
",p[k]);
        }
    }
    return 0;
}

(2)约瑟夫环的逆过程：
从对牌的处理过程中可以看出，其过程和约瑟夫的处理过程完全相同，通过把牌从上面放到下面实现了环的效果。最后得到的序列，从下到上就是约瑟夫环的出队情况（不看 (1)）。
运行时间比模拟短的多。

代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t,n,m,q,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&q);
        m++;
        while(q--)
        {
            scanf("%d",&k);
            if(k==1)
            {
                printf("1
");
                continue;
            }
            k--;//去除1
            int ans=1,tol=n-1;//结果，总人数（除去第1个）
            while(1)//
            {
                if(tol<m)//总人数小于循环的长度
                {
                    int tk=m%tol;
                    if(tk==0) tk=tol;
                    if(tk==k)
                    {
                        printf("%d
",ans+1);
                        break;
                    }
                    if(tk<k) k-=tk;
                    else if(tk>k) k+=(tol-tk);
                    tol--;
                    ans++;
                    continue;
                }
                if(k%m==0)//此次处理中目标的序号是要除去的数中的一个
                {
                    printf("%d
",ans+k/m);
                    break;
                }
                //下一次处理时在环中对应的编号
                if(k>(tol/m)*m) k-=(tol/m)*m;
                else k=tol-(tol/m)*m+k-k/m;
                ans+=tol/m;//去除时的编号
                tol-=tol/m;//总人数减少
            }
        }
    }
    return 0;
}