SP1108 CTRICK - Card Trick 题解

scp020 · 2023-10-22 21:16:31 · 题解

SP1108 CTRICK - Card Trick 题解

一眼题。没在洛谷交，给出原网站的通过记录。

解法

考虑如何放置这些牌。

整个 n 张牌可以理解为一个循环链表，我们找到在放置第 i 张牌的时候，我们要从放置第 i-1 张牌的位置向后数 i + 1 张牌，在该位置放置第 i 张牌。注意到第 1 到 i-1已经抽走了，所以现在有 n-i+1 张牌。问题现在转化为：给定一个长度为 n-i+1 的循环链表和当前位置 pos，求出 pos 向后走 i+1 的位置，并且删除该位置。

转化后的问题非常好求，这里不多解释了，看下面的代码。

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,ans[20010];
struct mylist
{
    int front,next;
};
mylist a[20010];
inline void init() // 初始化循环链表
{
    for(int i=1;i<=n;i++) a[i].front=i-1,a[i].next=i+1;
    a[1].front=n,a[n].next=1;
}
inline void del(const int &pos)
{
    a[a[pos].front].next=a[pos].next,a[a[pos].next].front=a[pos].front;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n),init();
        for(int i=1,cnt,pos=1;i<=n;i++)
        {
            cnt=i%(n-i+1);
            while(cnt--) pos=a[pos].next;
            ans[pos]=i,del(pos),pos=a[pos].next;
        }
        for(int i=1;i<=n;i++) printf("%d ",ans[i]);
        printf("\n");
    }
    return 0;
}