本文主要是介绍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:
• 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 .
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
(1 ≤ n, m ≤ 100, 000). Each of the following m lines contain a command.
Output
from left to right.
Sample Input
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 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【双向链表】【数组模拟】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
