Boxes in a Line UVA

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

Sample Output

Case 1: 12

Case 2: 9

Case 3: 2500050000

HINT

这个题重点就是如何解决超时的问题，如果老老实实的按照题目的要求来反转链表，那超时是肯定的了。另外利用函数查找也是超时。一开始值考虑到反转超时，没考虑查找超时问题，看了vj上一个大佬的思路用数组储存地址。因为链表只有反转后和反转前两种状态，而当链表为反转时，x放到y的右侧就是真的右侧，而反转后便是y的左侧。因此只需要一个标志位记录链表的状态就好。等到最后输出的时候在看链表时反转的还是正向的，进行选择反转。然后计算答案输出。

Accepted

#include<bits/stdc++.h>

using namespace std;

int main() {

	int m, n, op, x, y, num = 0;

	while (cin >> m >> n) {

		int q = 1;

		list<int>L(m);			//这里必须先说明大小为m否则如果m过大会卡死程序，不知道为啥~

		vector<list<int>::iterator>pointer(m+1);	//这里必须先说明大小为m否则如果m过大会卡死程序，不知道为啥~

		for (auto temp = L.begin();temp != L.end();temp++) {	//初始化

			*temp = q++;

			pointer[q - 2] = temp;

		}

		int flag = 1;		//判断正反1为正，-1为反

		while (n--) {

			cin >> op;

			if (op == 4)flag = -1 * flag;		//标记反转

			else {

				cin >> x >> y;

				x--;y--;

				if (op == 3) {					//交换的时候要值和地址一起交换

					swap(*pointer[x], *pointer[y]);

					swap(pointer[x], pointer[y]);

				}

				else {

					auto temp1 = pointer[x];		//先插到y的右面

					pointer[x] = L.insert(pointer[y], *pointer[x]);

					L.erase(temp1);

					if (flag == 1 && op == 2 || flag == -1 && op == 1) {	//如果要查到右边就交换x,y

						swap(*pointer[x], *pointer[y]);

						swap(pointer[x], pointer[y]);

					}

				}

			}

		}

			unsigned long long int sum = 0;			//计算

			auto temp = L.begin();

			if (flag == -1)temp = --L.end();

			m = L.size() - 1;

			for (int i = 0;i < L.size();i++, m--)

			{

				if (i % 2 == 0)sum += *temp;

				if (flag == 1)temp++;				//对反转还是正向进行区分

				else if (temp != L.begin()) temp--;

			}

			cout << "Case " << ++num << ": " << sum << endl;

	}

}

巴特西

Boxes in a Line UVA - 12657