项链

NC213760. 项链

描述

scimoon 意外得到了一个项链，这个项链非常的神奇：它有 N 个珠子，一开始每个珠子有一个编号，从左到右编号分别是 1 至 N，scimoon 进行了 M 次操作，每次操作有下面这么几种：

1 x y ：表示将编号为 x 的珠子移到编号为 y 的珠子的后面

2 x y ：表示将编号为 x 的珠子移到编号为 y 的珠子的前面

3 ：表示翻转这个项链，注意翻转后 1,2 操作中的前后关系会改变

4 ：从编号 1 的珠子开始从左到右输出每个珠子的编号

如果您没有完全理解题意，您可以通过阅读样例解释帮助理解

输入描述

第一行两个数： N 和 M 

第  行：输入每一次操作

输出描述

对于每次操作 4，输出这个项链每位置上的珠子的编号。

示例1

输入:

输出:

1 3 4 2 5
1 5 3 4 2
1 2 4 3 5

说明:

第一次操作后，2 号珠子被放到了 4 号珠子的后面，项链为 [1,3,4,2,5]

第二次操作输出当前的项链 [1,3,4,2,5]

第三次操作后，5 号珠子被放到了 3 号珠子的前面，项链为 [1,5,3,4,2]

第四次操作输出当前的项链 [1,5,3,4,2]

第五次操作翻转当前项链 [2,4,3,5,1]

第六次操作中，由于我们需要从 1 开始输出项链，因此输出 [1,2,4,3,5]

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 159ms, 内存消耗: 3504K, 提交时间: 2020-11-19 13:41:43

#include<bits/stdc++.h>
using namespace std;
int n,m,op,x,y;
int l[100010],r[100010];
bool rot;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		l[i]=i-1;
		r[i]=i+1;
	}
	l[1]=n,r[n]=1;
	while(m--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d",&x,&y);
			r[l[x]]=r[x];
			l[r[x]]=l[x];
			l[r[y]]=x;
			r[x]=r[y];
			r[y]=x;
			l[x]=y;
		}
		if(op==2)
		{
			scanf("%d%d",&x,&y);
			r[l[x]]=r[x];
			l[r[x]]=l[x];
			r[l[y]]=x;
			l[x]=l[y];
			l[y]=x;
			r[x]=y;
		}
		if(op==3)
		{
			for(int i=1;i<=n;i++)
			{
				int temp=r[i];
				r[i]=l[i];
				l[i]=temp;
			}
		}
		if(op==4)
		{
			printf("1");
			for(int i=r[1];i!=1;i=r[i])
			{
				printf(" %d",i);
			}
			printf("\n");
		}
	}
	return 0;
}

上一题

下一题

详情