Matrix Multiplication

Matrix Multiplication

时间： 1ms        内存：64M

描述：

You are given a matrix M of type 1234x5678. It is initially filled with integers 1...1234x5678 in row major order. Your task is to process a list of commands manipulating M. There are 4 types of commands:
"R x y" swap the xth and yth row of M; 1<=x, y<=1234.
"C x y" swap the xth and yth column of M; 1<=x, y<=5678.
"Q x y" write out M(x, y); 1<=x<=1234.1<=y<=5678.
"W z" write out x and y where z=M(x, y). 1<=z<=7006652 (1234 * 5678)

输入：

The input file contains several test cases. The first line is N: the number of test cases. Then follows N lines. A list of valid commands.1 <= N <= 10000.

输出：

For each "Q x y" write out one line with the current value of M(x, y), for each "W z" write out one line with the value of x and y (described as above) separated by a space.

示例输入：

10
R 1 2
Q 1 1
Q 2 1
W 1
W 5679
C 1 2
Q 1 1
Q 2 1
W 1
W 5679

示例输出：

5679
1
2 1
1 1
5680
2
2 2
1 2

提示：

参考答案（内存最优[856]）：

#include <cstdio>
#include <algorithm>
using namespace std;

int r[1234], r_pos[1234], c[5678], c_pos[5678];
int ncases;

void swap_row();
void swap_column();
void output_num();
void output_pos();

int main()
{
	scanf("%d", &ncases);
	for (int i = 0; i < 1234; ++i)
	{
		r[i] = r_pos[i] = i;
	}
	for (int i = 0; i < 5678; ++i)
	{
		c[i] = c_pos[i] = i;
	}
	while (ncases--)
	{
		char buf[10];
		scanf("%s", buf);

		char cmd = buf[0];
		if (cmd == 'R')
		{
			swap_row();
		}
		else if (cmd == 'C')
		{
			swap_column();
		}
		else if (cmd == 'Q')
		{
			output_num();
		}
		else if (cmd == 'W')
		{
			output_pos();
		}
	}
	return 0;
}

void swap_row()
{
	int x, y;
	scanf("%d%d", &x, &y);
	swap(r_pos[r[x - 1]], r_pos[r[y - 1]]);
	swap(r[x - 1], r[y - 1]);
}

void swap_column()
{
	int x, y;
	scanf("%d%d", &x, &y);
	swap(c_pos[c[x - 1]], c_pos[c[y - 1]]);
	swap(c[x - 1], c[y - 1]);
}

void output_num()
{
	int x, y;
	scanf("%d%d", &x, &y);
	printf("%d\n", r[x - 1] * 5678 + c[y - 1] + 1);
}

void output_pos()
{
	int num;
	scanf("%d", &num);
	printf("%d %d\n", r_pos[(num - 1) / 5678] + 1, c_pos[(num - 1) % 5678] + 1);
}

参考答案（时间最优[12]）：

#include <cstdio>
#include <algorithm>
using namespace std;

int r[1234], r_pos[1234], c[5678], c_pos[5678];
int ncases;

void swap_row();
void swap_column();
void output_num();
void output_pos();

int main()
{
	scanf("%d", &ncases);
	for (int i = 0; i < 1234; ++i)
	{
		r[i] = r_pos[i] = i;
	}
	for (int i = 0; i < 5678; ++i)
	{
		c[i] = c_pos[i] = i;
	}
	while (ncases--)
	{
		char buf[10];
		scanf("%s", buf);

		char cmd = buf[0];
		if (cmd == 'R')
		{
			swap_row();
		}
		else if (cmd == 'C')
		{
			swap_column();
		}
		else if (cmd == 'Q')
		{
			output_num();
		}
		else if (cmd == 'W')
		{
			output_pos();
		}
	}
	return 0;
}

void swap_row()
{
	int x, y;
	scanf("%d%d", &x, &y);
	swap(r_pos[r[x - 1]], r_pos[r[y - 1]]);
	swap(r[x - 1], r[y - 1]);
}

void swap_column()
{
	int x, y;
	scanf("%d%d", &x, &y);
	swap(c_pos[c[x - 1]], c_pos[c[y - 1]]);
	swap(c[x - 1], c[y - 1]);
}

void output_num()
{
	int x, y;
	scanf("%d%d", &x, &y);
	printf("%d\n", r[x - 1] * 5678 + c[y - 1] + 1);
}

void output_pos()
{
	int num;
	scanf("%d", &num);
	printf("%d %d\n", r_pos[(num - 1) / 5678] + 1, c_pos[(num - 1) % 5678] + 1);
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。