题目链接:https://ac.nowcoder.com/acm/problem/213760

到主站看:https://blog.csdn.net/weixin_43346722/article/details/110257456

题目

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

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

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

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

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

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

输入

第一行两个数:

行:输入每一次操作

输出

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

样例输入

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

样例输出

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

样例解释

第一次操作后, 号珠子被放到了 号珠子的后面,项链为

第二次操作输出当前的项链

第三次操作后, 号珠子被放到了 号珠子的前面,项链为

第四次操作输出当前的项链

第五次操作翻转当前项链

第六次操作中,由于我们需要从 开始输出项链,因此输出

数据范围

保证操作 不超过

思路

这道题其实就是一个链的模拟。

因为要翻转,那我们就模拟双向的。

然后就把翻转了奇数次和翻转了偶数次的情况下的模拟分开来写。

然后讲一下每一个操作要怎么模拟:(这里默认翻转偶数次,就是正常的从左到右)

  1. 操作一,把一个珠子 移到珠子 的后面。那就是 左右要连起来, 的后面就是 的后面就是 原来的后面。(写代码的时候按上面的顺序反过来写,才不会要用的值被之前覆盖)
  2. 操作二,把一个珠子 移到珠子 的前面。那其实差不多,也是 左右连起来,那这一次就是 的前面是 原来的后面, 的后面是 。(写代码的时候也要反过来,原因一样)
  3. 操作三,翻转。那其实简单,就弄一个 记录它当前是正的反的。然后又一次操作三就
  4. 操作四,输出。那更容易,如果现在是正的就直接从左到右输出,否则就从右到左输出。

    代码

#include<cstdio>

using namespace std;

int n, m, bef[10001], nxt[10001], turn, op, x, y;

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        bef[i] = i - 1;
        nxt[i] = i + 1;
    }
    bef[1] = n;
    nxt[n] = 1;

    for (int i = 1; i <= m; i++) {
        scanf("%d", &op);

        if (op == 1) {
            scanf("%d %d", &x, &y);

            if (!turn) {
                nxt[bef[x]] = nxt[x];
                bef[nxt[x]] = bef[x];
                bef[nxt[y]] = x;
                nxt[x] = nxt[y];
                bef[x] = y;
                nxt[y] = x;
            }
            else {
                nxt[bef[x]] = nxt[x];
                bef[nxt[x]] = bef[x];
                nxt[bef[y]] = x;
                bef[x] = bef[y];
                nxt[x] = y;
                bef[y] = x;
            }

            continue;
        }
        if (op == 2) {
            scanf("%d %d", &x, &y);

            if (!turn) {
                nxt[bef[x]] = nxt[x];
                bef[nxt[x]] = bef[x];
                nxt[bef[y]] = x;
                bef[x] = bef[y];
                nxt[x] = y;
                bef[y] = x;
            }
            else {
                nxt[bef[x]] = nxt[x];
                bef[nxt[x]] = bef[x];
                bef[nxt[y]] = x;
                nxt[x] = nxt[y];
                bef[x] = y;
                nxt[y] = x;
            }

            continue;
        }
        if (op == 3) {
            turn ^= 1;

            continue;
        }
        if (op == 4) {
            if (!turn) {
                printf("1 ");
                for (int j = nxt[1]; j != 1; j = nxt[j])
                    printf("%d ", j);
                printf("\n");
            }
            else {
                printf("1 ");
                for (int j = bef[1]; j != 1; j = bef[j])
                    printf("%d ", j);
                printf("\n");
            }

            continue;
        }
    }

    return 0;
}