CSU-1982 小M的移动硬盘

2024-03-29 13:32:34

CSU-1982 小M的移动硬盘

Description

最近小M买了一个移动硬盘来储存自己电脑里不常用的文件。但是他把这些文件一股脑丢进移动硬盘后，觉得这些文件似乎没有被很好地归类，这样以后找起来岂不是会非常麻烦？
小M最终决定要把这些文件好好归类，把同一类地移动到一起。所以现在小M有了这几种操作：
1 u 表示把编号为u的文件放到最上面
2 u 表示把编号为u的文件放到最下面
3 u v 表示把编号为u的文件放到编号为v的文件的后面
已知在最开始的时候，1号文件到n号文件从上往下排布
现在小M已经给出了他所进行的所有操作，你能告诉他操作之后的序列是会变成什么样子吗？

Input

第一行为一个数字T（T<=10）表示数据组数
第二行为两个数字n、m（1<=n,m<=300000）表示序列长度和小M的操作次数
接下来m行每行两个或三个数字，具体含义见题面
保证数据合法

Output

输出一行表示小M操作结束后的序列

Sample Input

1
10 5
1 5
2 3
2 6
3 4 8
3 1 3

Sample Output

5 2 7 8 4 9 10 3 1 6

也是一道水题，但却WA了很多发，这题用数组模拟双向链表即可，先贴一开始WA的代码

#include<bits/stdc++.h>
#define maxn 300050
using namespace std;
struct node {
    int l, r;
} a[maxn];
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            a[i].l = i - 1;
            a[i].r = i + 1;
        }
        int head = 1, tail = n;
        for (int i = 1; i <= m; i++) {
            int q;
            scanf("%d", &q);
            if (q == 1) {
                int x;
                scanf("%d", &x);
                if (x == head) continue;
                if (x == tail) tail = a[x].l;
                a[a[x].l].r = a[x].r;
                a[a[x].r].l = a[x].l;
                a[head].l = x;
                a[x].l = 0;
                a[x].r = head;
                head = x;
            }
            if (q == 2) {
                int x;
                scanf("%d", &x);
                if (x == tail) continue;
                if (x == head) head = a[x].r;
                a[a[x].l].r = a[x].r;
                a[a[x].r].l = a[x].l;
                a[tail].r = x;
                a[x].l = tail;
                a[x].r = n + 1;
                tail = x;
            }
            if (q == 3) {
                int x, y;
                scanf("%d%d", &x, &y);
                if (x == y) continue;
                if (x == head) {
                    head = a[x].r;
                }
                if (y == tail) {
                    tail = x;
                }
                a[a[x].l].r = a[x].r;
                a[a[x].r].l = a[x].l;
                a[x].r = a[y].r;
                a[a[y].r].l = x;
                a[x].l = y;
                a[y].r = x;
            }
        }
        int now = head;
        for (int i = 1; i < n; i++) {
            printf("%d ", now);
            now = a[now].r;
        }
        printf("%d\n", now);
    }
    return 0;
}
/**********************************************************************
    Problem: 1982
    User: Artoriax
    Language: C++
    Result: WA
**********************************************************************/

这个代码只有一点没注意到，即在q==3时，x处于tail时也会导致tail变化，很容易想的一个点，但却WA了很多次，然后去网上搜题解，用a[0]表示链表头，用a[n + 1]表示表尾才AC, 之后对拍一发才发现这个愚蠢的错误。

网上题解版：

#include<bits/stdc++.h>
#define maxn 300050
using namespace std;
struct node {
    int l, r;
} a[maxn];
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            a[i].l = i - 1;
            a[i].r = i + 1;
        }
        a[0].r = 1;
        a[n + 1].l = n;
        for (int i = 1; i <= m; i++) {
            int q;
            scanf("%d", &q);
            if (q == 1) {
                int x;
                scanf("%d", &x);
                a[a[x].l].r = a[x].r;
                a[a[x].r].l = a[x].l;
                a[x].l = 0;
                a[x].r = a[0].r;
                a[a[0].r].l = x;
                a[0].r = x;
            }
            if (q == 2) {
                int x;
                scanf("%d", &x);
                a[a[x].l].r = a[x].r;
                a[a[x].r].l = a[x].l;
                a[x].r = n + 1;
                a[x].l = a[n + 1].l;
                a[a[n + 1].l].r = x;
                a[n + 1].l = x;
            }
            if (q == 3) {
                int x, y;
                scanf("%d%d", &x, &y);
                if (x == y) continue;
                a[a[x].l].r = a[x].r;
                a[a[x].r].l = a[x].l;
                a[x].r = a[y].r;
                a[a[y].r].l = x;
                a[x].l = y;
                a[y].r = x;
            }
        }
        int now = a[0].r;
        for (int i = 1; i < n; i++) {
            printf("%d ", now);
            now = a[now].r;
        }
        printf("%d\n", now);
    }
    return 0;
}
/**********************************************************************
    Problem: 1982
    User: Artoriax
    Language: C++
    Result: AC
    Time:556 ms
    Memory:4368 kb
**********************************************************************/

自己改正版:

#include<bits/stdc++.h>
#define maxn 300050
using namespace std;
struct node {
    int l, r;
} a[maxn];
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            a[i].l = i - 1;
            a[i].r = i + 1;
        }
        int head = 1, tail = n;
        for (int i = 1; i <= m; i++) {
            int q;
            scanf("%d", &q);
            if (q == 1) {
                int x;
                scanf("%d", &x);
                if (x == head) continue;
                if (x == tail) tail = a[x].l;
                a[a[x].l].r = a[x].r;
                a[a[x].r].l = a[x].l;
                a[head].l = x;
                a[x].l = 0;
                a[x].r = head;
                head = x;
            }
            if (q == 2) {
                int x;
                scanf("%d", &x);
                if (x == tail) continue;
                if (x == head) head = a[x].r;
                a[a[x].l].r = a[x].r;
                a[a[x].r].l = a[x].l;
                a[tail].r = x;
                a[x].l = tail;
                a[x].r = n + 1;
                tail = x;
            }
            if (q == 3) {
                int x, y;
                scanf("%d%d", &x, &y);
                if (x == y) continue;
                if (a[y].r == x) continue;
                if (x == head) {
                    head = a[x].r;
                }
                if (x == tail) {
                    tail = a[x].l;
                }
                if (y == tail) {
                    tail = x;
                }
                a[a[x].l].r = a[x].r;
                a[a[x].r].l = a[x].l;
                a[x].r = a[y].r;
                a[a[y].r].l = x;
                a[x].l = y;
                a[y].r = x;
            }
        }
        int now = head;
        for (int i = 1; i < n; i++) {
            printf("%d ", now);
            now = a[now].r;
        }
        printf("%d\n", now);
    }
    return 0;
}
/**********************************************************************
    Problem: 1982
    User: Artoriax
    Language: C++
    Result: AC
    Time:560 ms
    Memory:4368 kb
**********************************************************************/
上一篇：UVA 4879 Old Fafhioned Typefetting（易WA细节题）


下一篇：P1618 三连击（升级版）