题解 UVA12657 【移动盒子 Boxes in a Line】

zhaite · 2020-11-06 15:46:03 · 题解

这道题别问，问就是静态链表模拟

首先定义两个vector<int>，用于维护静态链表。用一对指针进行操作，这样的好处是，在反转链表时，只需要交换两个指针变量的值即可

swap(pair.first, pair.second);

对于插入操作，先删值，再插入。对于1，2操作，本质上是同样的操作，把值插入到当前值左边值的右侧，既是插入到当前值的左侧。用了几个lambda类型。很少见有人在洛谷上直接用lambda。

#include <cstdio>
#include <functional>
#include <vector>
using namespace std;

int main(void)
{
    int n, m;
    for (int id = 1; ~scanf("%d %d", &n, &m); ++id)
    {
        vector<int> l(n + 1), r(n + 1);
        for (int i = 0; i <= n; ++i)
        {
            l[i] = (i + 1) % (n + 1);
            r[i] = (i + n) % (n + 1);
        }
        pair<vector<int> *, vector<int> *> pair = make_pair(&l, &r);
        function<void(int)> del = [&pair](int x) {
            pair.first->at(pair.second->at(x)) = pair.first->at(x);
            pair.second->at(pair.first->at(x)) = pair.second->at(x);
        };
        function<void(int, int)> ins = [&pair](int x, int y) {
            function<void(vector<int> &, int, int)> f = [](vector<int> &v, int x, int y) { int r = v[x]; v[x] = y;  v[y] = r; };
            f(*pair.first, x, y);
            f(*pair.second, pair.first->at(y), y);
        };
        while (m--)
        {
            int cmd, x, y;
            scanf("%d", &cmd);
            if (cmd == 4)
                swap(pair.first, pair.second);
            else
            {
                scanf("%d %d", &x, &y);
                if (cmd == 1)
                {
                    del(x), ins(pair.second->at(y), x);
                }
                else if (cmd == 2)
                {
                    del(x), ins(y, x);
                }
                else if (cmd == 3)
                {
                    int l1 = pair.second->at(x), l2 = pair.second->at(y);
                    int r1 = pair.first->at(x), r2 = pair.first->at(y);
                    swap(pair.first->at(l1), pair.first->at(l2));
                    swap(pair.first->at(x), pair.first->at(y));
                    swap(pair.second->at(r1), pair.second->at(r2));
                    swap(pair.second->at(x), pair.second->at(y));
                }
            }
        }
        unsigned long long total = 0;
        for (int i = 0, k = 0; i < n; ++i)
        {
            k = pair.first->at(k);
            total += i % 2 ? 0 : k;
        }
        printf("Case %d: %llu\n", id, total);
    }
    return 0;
}