TSOJ 1175 移动小球 [静态双向链表]

概述

这道题实际上之前做过一遍，但是神奇地哪里都找不到了。想法是大约半年前的想法，重新实现了一下。

没有什么好说的，静态双向链表，实现左侧插入和右侧插入。速度要比STL list快很多。

题目描述

你有一些小球，从左到右依次编号为1,2,3,…,n，如下图所示。
你可以执行两种指令。A X Y 把小球X移动到Y左边；B X Y 把小球X移动到Y右边。指令保证合法（X与Y不同）。

输入描述

输入: 第一行是2个正整数，第一个正整数是小球个数n，第二个正整数是指令条数m；随后输入m条指令。

输出描述

从左到右输出最后的序列中各小球序号。序号之间使用空格隔开。行末没有空格。

样例输入

6 2

A 1 4

B 3 5

样例输出

2 1 4 5 3 6

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2000;

int pre[N], nxt[N];

int main() {
    char t;
    int x, y, l, r;
    for(int n, m; ~scanf("%d%d", &n, &m);) {
        for(int i = 0; i <= n; i++) {
            pre[i + 1] = i;
            nxt[i] = i + 1;
        }
        pre[0] = -1;
        nxt[n + 1] = -1;
        while(m--) {
            while(!isalpha(t = getchar()));
            scanf("%d%d", &x, &y);
            l = pre[x], r = nxt[x];
            nxt[l] = r, pre[r] = l;
            if(t == 'A') {
                l = pre[y], r = y;
            } else {
                l = y, r = nxt[y];
            }
            nxt[l] = x, nxt[x] = r;
            pre[x] = l, pre[r] = x;
        }
        printf("%d", nxt[0]);
        for(int j = nxt[nxt[0]]; ~nxt[j]; j = nxt[j]) {
            printf(" %d", j);
        }
        putchar('\n');
    }
    return 0;
}

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.