本文主要是介绍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
问题链接:UVA12657 Boxes in a Line
问题简述:(略)
问题分析:
占个位置,不解释。
程序说明:(略)
题记:(略)
参考链接:(略)
AC的C++语言程序如下:
/* UVA12657 Boxes in a Line */#include <bits/stdc++.h>using namespace std;const int N = 100000;
int left2[N + 2], right2[N + 2];void link(int x, int y)
{right2[x] = y;left2[y] = x;
}int main()
{int n, m, caseno = 0, op, x, y;while(~scanf("%d%d", &n, &m)) {// 初始化right2[0] = 1;left2[0] = n;for(int i=1; i<=n; i++)right2[i] = (i + 1) %(n + 1), left2[i] = i - 1;// 模拟操作int flag = 0;while(m--) {scanf("%d", &op);if(op == 4)flag = 1 - flag;else {scanf("%d%d", &x, &y);if(op == 3 && right2[y] == x)swap(x, y);if(op != 3 && flag)op = 3 - op;if(op == 1 && left2[y] == x)continue;if(op == 2 && right2[y] == x)continue;int leftx = left2[x], rightx = right2[x], lefty = left2[y], righty = right2[y];if(op == 1) {link(leftx, rightx);link(lefty, x);link(x, y);} else if(op == 2) {link(leftx, rightx);link(y, x);link(x, righty);}else{if(right2[x] == y)link(leftx, y), link(y, x), link(x,righty);elselink(leftx,y), link(y, rightx), link(lefty, x), link(x, righty);}}}int k = 0;long long ans=0;for(int i=1; i<=n; i++) {k = right2[k];if(i & 1)ans += k;}if(flag && n % 2 == 0)ans = (long long) n / 2 * (n + 1) - ans;// 输出结果printf("Case %d: %lld\n", ++caseno, ans);}return 0;
}
这篇关于UVA12657 Boxes in a Line【模拟】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!