UVA12657 Boxes in a Line【双向链表】【数组模拟】

本文主要是介绍UVA12657 Boxes in a Line【双向链表】【数组模拟】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You have n boxes in a line on the table numbered 1 . . . n from left to right. Your task is to simulate 4

kinds of commands:

• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )
• 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y )
• 3 X Y : swap box X and Y

• 4: reverse the whole line.

Commands are guaranteed to be valid, i.e. X will be not equal to Y .

For example, if n = 6, after executing 1 1 4, the line becomes 2 3 1 4 5 6. Then after executing
2 3 5, the line becomes 2 1 4 5 3 6. Then after executing 3 1 6, the line becomes 2 6 4 5 3 1.

Then after executing 4, then line becomes 1 3 5 4 6 2

Input

There will be at most 10 test cases. Each test case begins with a line containing 2 integers n, m

(1 ≤ n, m ≤ 100, 000). Each of the following m lines contain a command.

Output

For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n

from left to right.

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

题目大意：你有一行盒子，从左到右编号为1~n，现在有4种操作。

1 X Y 表示把X盒子移到Y盒子的左边

2 X Y 表示把X盒子移到Y盒子的右边

3 X Y 表示交换X盒子和Y盒子的位置

4 将盒子顺序全部翻转过来

最后问进行m次操作后，奇数位置的盒子编号和为多少

思路：最好的方法使用双向链表。这里用数组的方法模拟，用Left[i]和Right[i]

分别表示编号为i的盒子左边和右边的盒子编号(为0表示没有盒子)。通过模拟

链表连接的方法改变连接顺序。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;int Left[100010],Right[100010];void link(int L,int R)
{Right[L] = R;Left[R] = L;
}int main()
{int n,m,kase = 0;while(cin >> n >> m){for(int i = 1; i <= n; i++){Left[i] = i-1;Right[i] = (i+1) % (n+1);}Right[0] = 1;Left[0] = n;int inv = 0,X,Y;while(m--){int op;cin >> op;if(op == 4)inv = !inv;else{cin >> X >> Y;if(op == 3 && Right[Y] == X)swap(X,Y);if(op != 3 && inv)op = 3 - op;if(op == 1 && X == Left[Y])continue;if(op == 2 && X == Right[Y])continue;int LX,RX,LY,RY;LX = Left[X], RX = Right[X], LY = Left[Y], RY = Right[Y];if(op == 1){link(LX,RX);link(LY,X);link(X,Y);}else if(op == 2){link(LX,RX);link(Y,X);link(X,RY);}else if(op == 3){if(Right[X] == Y){link(LX,Y);link(Y,X);link(X,RY);}else{link(LX,Y);link(Y,RX);link(LY,X);link(X,RY);}}}}int num = 0;long long ans = 0;for(int i = 1; i <= n; i++){num = Right[num];if(i&1)ans += num;}if(inv && !(n&1))ans = (long long)n*(n+1)/2 - ans;cout << "Case " << ++kase <<": " << ans << endl;}return 0;
}

这篇关于UVA12657 Boxes in a Line【双向链表】【数组模拟】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---