当前位置: 代码迷 >> 综合 >> uva -12657 Boxes in a Line(数组实现双向链表)
  详细解决方案

uva -12657 Boxes in a Line(数组实现双向链表)

热度:57   发布时间:2024-03-06 02:10:17.0

题目链接

题意111 ~ nnn的数字原本按顺序摆好,接下来有四种操作。

  • 1XY1 X Y1XY :将XXX移动到YYY的左边
  • 2XY2 X Y2XY :将XXX移动到YYY的右边
  • 3XY3 X Y3XY :交换X,YX,YX,Y的位置
  • 444 :翻转整个数字串
    经过这一系列操作后,最后输出奇数位上的数字和。

题解 :有移动到左右的操作,所以想到了双向链表。由于是第一次写双向链表,写得很精污。注意 ∑i=1100000\sum_{i = 1}^{100000}i=1100000?会超出int范围,所以用longlonglong\ longlong long。在交换X,YX,YX,Y的位置的时候,要特判两个数字的位置是不是相邻的。

#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int maxn = 1e5 + 7;map<int, int> mp;
int n, m, op, x, y, l[maxn][2], cas;void init() {
    l[0][1] = 1;l[n + 1][0] = n;for (int i = 1; i <= n; ++i) {
    l[i][0] = i - 1;l[i][1] = i + 1;}mp[1] = 0, mp[2] = 1;
}void insert(int op, int x, int y) {
    if (l[y][op] == x) return;l[l[x][1]][0] = l[x][0];l[l[x][0]][1] = l[x][1];l[l[y][op]][op ^ 1] = x;l[x][op] = l[y][op];l[x][op ^ 1] = y;l[y][op] = x;
}void exc(int x, int y) {
    int ll = l[x][0], lr = l[x][1];int rl = l[y][0], rr = l[y][1];if (lr == y) {
    l[ll][1] = y;l[y][1] = x;l[y][0] = ll;l[x][0] = y;l[x][1] = rr;l[rr][0] = x;return;}if (ll == y) {
    l[rl][1] = x;l[x][1] = y;l[x][0] = rl;l[y][0] = x;l[y][1] = lr;l[lr][0] = y;return;}l[ll][1] = y, l[lr][0] = y;l[rl][1] = x, l[rr][0] = x;l[x][0] = rl;l[x][1] = rr;l[y][0] = ll;l[y][1] = lr;}void print(int op) {
    int head;ll res = 0;if (op) head = 0;else head = n + 1;int f = n, cnt = 1;while (f--) {
    head = l[head][op];if (cnt & 1) res += head;cnt ^= 1;}printf("Case %d: %lld\n", ++cas, res);
}void solve() {
    init();while (m--) {
    scanf("%d", &op);if (op == 4) {
    mp[1] ^= 1;mp[2] ^= 1;continue;}scanf("%d %d", &x, &y);if (op == 3) {
    exc(x, y);}else {
    insert(mp[op], x, y);}}print(mp[2]);
}
int _T;
int main() {
    while (~scanf("%d %d", &n, &m)) solve();return 0;
}
  相关解决方案