题解 CF1458C 【Latin Square】
Warriors_Cat
2020-12-23 17:30:05
[题面传送门](https://www.luogu.com.cn/problem/CF1458C)。
~~题意太长了不想描述，自己看吧qwq~~。
这题好神啊，思维含量真的高 orz。
---
### $Solution:$
很显然，如果这题只有 `RLDU` 这四个操作的话，那么就是一个 sb 题，直接维护行和列加了多少即可。
但，加上 `IC` 操作后，这题就变得有些困难了。
考虑 `IC` 操作的本质，对于一个坐标 $(i, a_i)$，其求逆操作其实就是变成 $(a_i, i)$。
照这样，我们考虑把每个点看成一个三维坐标 $(i, j, a_{i, j})$。进行 `I` 操作就相当于交换 $y$ 坐标和 $z$ 坐标，进行 `C` 操作就相当于交换 $x$ 和 $z$ 坐标。
于是每次我们都可以存储这个 $x, y, z$ 坐标现在对应的是什么类型，最后加回去就可以了。
很显然每一次操作都是 $O(1)$ 的，最后处理也是 $O(n \times n)$ 的。
over，时间复杂度为 $O(n^2 + m)$。没有任何的高级算法的思维题属实强。
---
### $Code:$
非赛时代码，码风可能有一点不同。
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
#define y0 y_csyakioi_0
#define y1 y_csyakioi_1
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = y; i >= x; --i)
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 1010, M = 100010;
int n, m, a[N * N][3], mov[10], pos[10], ans[N][N]; char s[M];
inline int id(int x, int y){ return (x - 1) * n + y; }
inline void work(){
n = read(); m = read();
rep(i, 1, n) rep(j, 1, n){
int k = id(i, j);
a[k][0] = i; a[k][1] = j; a[k][2] = read();
}
scanf("%s", s + 1);
rep(i, 0, 2) pos[i] = i, mov[i] = 0;
rep(i, 1, m){
if(s[i] == 'R') ++mov[pos[1]];
if(s[i] == 'L') --mov[pos[1]];
if(s[i] == 'D') ++mov[pos[0]];
if(s[i] == 'U') --mov[pos[0]];
if(s[i] == 'I') swap(pos[1], pos[2]);
if(s[i] == 'C') swap(pos[0], pos[2]);
}
rep(i, 1, n * n){
rep(j, 0, 2) a[i][j] = (a[i][j] + mov[j] - 1 + m * n) % n + 1;
ans[a[i][pos[0]]][a[i][pos[1]]] = a[i][pos[2]];
}
rep(i, 1, n){
rep(j, 1, n){
printf("%d ", ans[i][j]);
}
puts("");
}
}
int main(){ int T = read(); while(T--) work(); return 0; }
```