SP1108 CTRICK - Card Trick 题解

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;
}