UVA12657 移动盒子 Boxes in a Line

时间: 2023-12-16 admin IT培训

UVA12657 移动盒子 Boxes in a Line

UVA12657 移动盒子 Boxes in a Line

首先一看题,应该发现需要使用链表,并且有翻转操作,确定是双向,链表,对于操作1和2,我们直接删除x,然后把它插在相应的位置,不需要去判断,但是这里需要注意,翻转会影响左右,也就是一开始右边是next,翻转了右边就变成prev了,这个是非常容易出错的一个点,然后是三操作,由于我用的是数组模拟链表的写法,所以还用了散列数组来记录元素的位置,这里两个元素可能是挨着的,所以我们直接交换两个元素,就不需要考虑相邻的情况,这里交换元素需要注意,不仅要把元素对应的下标交换,还要把下标对应的元素交换,下标相当于地址,下标对应元素就是链表里我们要交换元素,由于我们有一个散列数组用来快速获得元素的地址,所以链表改完,这个也要改,不要忘记,最后分情况输出就行了,

总之还是用的建立链表然后在上面操作的思路,代码很长,但是思路简单,

#include <bits/stdc++.h>#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()using namespace std;typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;const int N = 1e5 + 5;struct Node {int value;int prev, next;
} node[N];int tot, head, tail;
int Hash[N];void init() {tot = 2;head = 1; tail = 2;node[1].next = 2;node[2].prev = 1;
}void insert_back(int &cur, int value) {int q = ++tot;node[q].value = value;node[q].prev = cur;node[q].next = node[cur].next;node[cur].next = q;node[node[q].next].prev = q;cur = q;
}void insert2(int p1, int p2) {node[p2].prev = p1;node[p2].next = node[p1].next;node[p1].next = p2;node[node[p2].next].prev = p2;
}void remove(int p) {node[node[p].prev].next = node[p].next;node[node[p].next].prev = node[p].prev;
}int main() {int n, m;int num = 1;while (cin >> n >> m) {init();int cur = 1;for (int i = 1; i <= n; i++) {insert_back(cur, i);Hash[i] = i + 2;}int ok = 0;while (m--) {int op;cin >> op;int x, y;if (op == 1) {cin >> x >> y;if (!ok) {remove(Hash[x]);insert2(node[Hash[y]].prev, Hash[x]);} else {remove(Hash[x]);insert2(Hash[y], Hash[x]);}} else if (op == 2) {cin >> x >> y;if (!ok) {remove(Hash[x]);insert2(Hash[y], Hash[x]);} else {remove(Hash[x]);insert2(node[Hash[y]].prev, Hash[x]);}} else if (op == 3) {cin >> x >> y;swap(node[Hash[x]].value, node[Hash[y]].value);swap(Hash[x], Hash[y]);} else {if (ok) ok = 0;else ok = 1;}}int cnt = 1;ll ans = 0;if (!ok) {int p = node[1].next;while (p != 2) {if (cnt++ % 2) ans += node[p].value;p = node[p].next;}} else {int p = node[2].prev;while (p != 1) {if (cnt++ % 2) ans += node[p].value;p = node[p].prev;}}cout << "Case " << num++ << ": " << ans << endl;}return 0;
}