CF1458C Latin Square

XXVI.CF1458C Latin Square

实际上此题使用的数据结构不很高级，甚至可以说很不高级——因为全程只用了数组。但是本题的思想绝对是非常高级的。

我们考虑上数据结构维护该操作。上下左右移动显然是没问题的；但是行中列中轮换应该咋办呢？

我们先考虑如果只有行上轮换应该怎么办。这玩意没什么好的数据结构维护，但如果我们把它二维数点地展开成\((i,p_i)\)就会发现，轮换一次就是\((i,p_i)\rightarrow(p_i,i)\)，即交换两维。这也是轮换的一个奇妙性质。

然后我们把它换成三维坐标\((i,j,a_{i,j})\)，就会发现行上轮换就是交换\(i,a_{i,j}\)，列上轮换就是交换\(j,a_{i,j}\)。这时候便很好维护了。

代码：

#include<bits/stdc++.h>
using namespace std;
int T,n,m,a[1010][1010],b[1010][1010],p[3],d[3],t[3];
char s[100100];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&a[i][j]),a[i][j]--;
		scanf("%s",s);
		for(int i=0;i<3;i++)p[i]=i,d[i]=0;
		for(int i=0;i<m;i++){
			if(s[i]=='U')(d[p[0]]+=n-1)%=n;
			if(s[i]=='D')(++d[p[0]])%=n;
			if(s[i]=='L')(d[p[1]]+=n-1)%=n;
			if(s[i]=='R')(++d[p[1]])%=n;
			if(s[i]=='I')swap(p[1],p[2]);
			if(s[i]=='C')swap(p[0],p[2]);
		}
		for(t[0]=0;t[0]<n;t[0]++)for(t[1]=0;t[1]<n;t[1]++){
			t[2]=a[t[0]][t[1]];
			b[(t[p[0]]+d[p[0]])%n][(t[p[1]]+d[p[1]])%n]=(t[p[2]]+d[p[2]])%n;
		}
		for(int i=0;i<n;i++){for(int j=0;j<n;j++)printf("%d ",b[i][j]+1);puts("");}puts("");
	}
	return 0;
}