【UVA 12657】Boxes in a Line 题解（静态双向链表）

您在编号为1的表格上有n个方框。n从左到右。您的任务是模拟4 命令类型： •1 X Y：将框X向左移动到Y（如果X已经是Y的左侧，则忽略此项） •2 X Y：将框X向右移动到Y（如果X已经是Y的右侧，则忽略此项） •3 X Y：交换盒X和Y •4：反转整条线路。 命令保证有效，即X不等于Y。 例如，如果n＝6，在执行1 1 4之后，该行变为2 3 1 4 5 6。然后在执行之后 2 3 5，直线变为2 1 4 5 3 6。然后在执行3 1 6之后，该行变为2 6 4 5 3 1。 然后在执行4之后，行变为1 3 5 4 6 2

输入 最多有10个测试用例。每个测试用例以包含2个整数n，m的行开始 （1≤n，m≤100000）。以下m行中的每一行都包含一个命令。 输出 对于每个测试用例，在奇数索引位置打印数字的和。位置编号为1到n 从左到右。

Sample Input 6 4 1 1 4 2 3 5 3 1 6 4 6 3 1 1 4 2 3 5 3 1 6 100000 1 4 Sample Output Case 1: 12 Case 2: 9 Case 3: 2500050000

思路

实现静态双向链表及插入元素、删除元素、移动元素、交换元素等操作。交换元素a和b时有三种情况，ab相邻且a在b前、ab相邻且a在b后、ab不相邻，要分情况解决。用rev来标记链表是否被翻转，若被翻转输出反向奇数索引之和，反向奇数索引之和等于所有索引之和减去正向奇数索引之和。

AC代码

#include <iostream>
#include <list>
#include <algorithm>
#define AUTHOR "HEX9CF"
using namespace std;

#define maxn 100005

int n, m;
int rev = 1;
int cmd;
int l[maxn], r[maxn];
int x, y;
int k = 1;

void link(int a, int b)
{
    r[a] = b;
    l[b] = a;
}

void del(int x)
{
    link(l[x], r[x]);
}

void ins(int a, int c, int b)
{
    link(a, c);
    link(c, b);
}

void swp(int x, int y)
{
    if (l[y] == x)
    {
        int a = l[x];
        int b = r[y];
        link(a, y);
        link(y, x);
        link(x, b);
    }
    else if (r[y] == x)
    {
        int a = l[y];
        int b = r[x];
        link(a, x);
        link(x, y);
        link(y, b);
    }
    else
    {
        int a = l[x];
        int b = r[x];
        int c = l[y];
        int d = r[y];
        link(c, x);
        link(x, d);
        link(a, y);
        link(y, b);
    }
}

void print()
{
    cout << "l ";
    for (int i = 1; i <= n; i++)
    {
        cout << l[i] << " ";
    }
    cout << endl
         << "r ";
    for (int i = 1; i <= n; i++)
    {
        cout << r[i] << " ";
    }
    cout << endl;
}

void show()
{
    int t = 0;
    for (int i = 1; i <= n; i++)
    {
        t = r[t];
        cout << t << " ";
    }
    cout << endl;
}

int main()
{
    while (cin >> n >> m)
    {
        rev = 1;
        for (int i = 1; i <= n + 1; i++)
        {
            l[i] = i - 1;
            r[i] = (i + 1) % (n + 1);
        }
        l[0] = n;
        r[0] = 1;
        // show();

        for (int i = 0; i < m; i++)
        {
            cin >> cmd;
            if (4 == cmd)
            {
                rev *= -1;
                continue;
            }
            cin >> x >> y;
            if ((1 == cmd && rev > 0) || (2 == cmd && rev < 0))
            {
                // 将盒子x 移动到y 的左侧
                // cout << "1 " << rev << endl;
                del(x);
                ins(l[y], x, y);
            }
            else if ((2 == cmd && rev > 0) || (1 == cmd && rev < 0))
            {
                // 将盒子x 移动到y 的右侧
                // cout << "2 " << rev << endl;
                del(x);
                ins(y, x, r[y]);
            }
            else if (3 == cmd)
            {
                // 交换盒子x 和y 的位置。
                // cout << x << " swap " << y << endl;
                swp(x, y);
            }
            // show();
        }
        // print();
        // show();
        int t = 0;
        long long sum = 0, j = 0;
        for (int i = 1; i <= n; i++)
        {
            t = r[t];
            sum += t;
            if (i % 2)
            {
                j += t;
            }
        }
        // cout << sum << endl;
        if (!(n % 2) && (rev < 0))
        {
            j = sum - j;
        }
        cout << "Case " << k << ": " << j << endl;
        k++;
    }
    return 0;
}