[抄题报告][UVA]UVA – 12657 Boxes in a Line – 移动盒子

本题直接抄答案,故命名为“抄题报告”,以后但凡是先看参考答案再做题的都命名为抄题报告。

题目地址:

https://cn.vjudge.net/problem/UVA-12657

题目描述:

(爱词霸翻译)

Background
背景

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 .. n 从左到右。你的任务是模拟4种命令:

• 1 X Y : move box X to the left to Y (ignore this if X is already the left of Y )
1 X Y表示把盒子X移动到盒子Y左边(如果X已经在Y的左边则忽略此命令)
• 2 X Y : move box X to the right to Y (ignore this if X is already the right of Y )
2 X Y表示把盒子X移动到盒子Y右边(如果X已经在Y的右边则忽略此命令)
• 3 X Y : swap box X and Y
3 X Y表示交换盒子X和Y的位置
• 4: reverse the whole line.
4表示反转整条链

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.

指令保证合法,即X不等于Y。例如,当n = 6时在初始状态下执行1 1 4后,盒子序列为2 3 1 4 5 6.接下来执行2 3 5,盒子序列变成2 1 4 5 3 6。再执行3 1 6,得到2 6 4 5 3 1。最终执行4,得到1 3 5 4 6 2。

The 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.
输入包含不超过10组数据,每组数据第一行为盒子个数n和指令条数m (1 ≤ n, m ≤ 100, 000).以下m行每行包含一条指令。

The Output
输出

For each test case, print the sum of numbers at odd-indexed positions. Positions are numbered 1 to n from left to right.
每组数据输出一行,即所有奇数位置的盒子编号之和。位置从左到右编号为1~n。

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


 

我的分析

本题为双端队列。但由于前一题的影响,我选择先手看解析和参考代码。

本题中通过数组来存储左右两边元素的下标,是空间使用最少的方法。我十分欣赏。还有后面那个翻转逆序时,通过总数 – 偶数和来实现逆序时的奇数和。交换顺序不改变奇数和的值。然后,关于交换顺序,相邻的情况有两种,XY和YX。答案中直接将YX的情况swap转成XY去计算,省了一小部分代码。思路十分清晰。

通过自己写的link函数对顺序进行操作。不像指针那样繁杂容易出错,代码看起来十分干净。

最后,我们需要用long long来存储大数字。

代码