LY1090 [ 20230220 CQYC模拟赛IX T1 ] 矩阵

题意

给定一个矩阵，你需要支持：

• 循环左移
• 循环右移
• 循环下移
• 循环上移
• 按行置换求逆
• 按列置换求逆

Sol

前 \(4\) 个操作是 \(trivial\) 的。

如何处理后两个操作？

考虑设一个三元组：\((x, y, A_{xy})\)。

每次操作，对于每一个元素都能确定操作后另外某个元素。

不难发现后两个操作就是交换 \(x, A_{x, y}\) 或 \(y, A_{x, y}\)。

时间复杂度：\(O(n ^ 2 + m)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
using namespace std;
#ifdef ONLINE_JUDGE

/* #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) */
/* char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf; */

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int N = 1e3 + 5, M = 1e5 + 5;
char strbuf[M];

void Mod(int &x, int n) {
	if (x >= n) x -= n;
	if (x < 0) x += n;
}

array <array <int, N>, N> s, h;

int main() {
	int n = read(), m = read();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			s[i][j] = read();
	scanf("%s", strbuf + 1);
	array <int, 4> v = {0, 0, 0}, u = {0, 1, 2};
	for (int i = 1; i <= m; i++) {
		switch (strbuf[i]) {
		case 'R':
			Mod(v[1], n), v[1]++;
			break;
		case 'L':
			v[1]--, Mod(v[1], n);
			break;
		case 'D':
			Mod(v[0], n), v[0]++;
			break;
		case 'U':
			v[0]--, Mod(v[0], n);
			break;
		case 'C':
			swap(v[0], v[2]), swap(u[0], u[2]);
			break;
		case 'I':
			swap(v[1], v[2]), swap(u[1], u[2]);
			break;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			array <int, 3> tp1 = {i, j, s[i][j]}, tp2;
			for (int k = 0; k < 3; k++)
				tp2[k] = tp1[u[k]];
			for (int k = 0; k < 3; k++)
				tp2[k] = v[k] + tp2[k];
			for (int k = 0; k < 3; k++)
				if (tp2[k] > n) tp2[k] -= n;
			h[tp2[0]][tp2[1]] = tp2[2];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			write(h[i][j]), putchar(32);
		puts("");
	}
	return 0;
}