题解 CF1458C 【Latin Square】

· · 题解

来菜园采菜啊 \to George1123

题面

CF1458C Latin Square

数据范围：$1\le T\le 1000$，$1\le \sum n\le 1000$，$1\le \sum m\le 10^5$，$1\le a_{i,j}\le n$。

题解

刚才有个群友问我 G 菜鸡发生肾摸事了，我说怎么回事？给我发了几张 CF 分数对比图，我一看！嗷！原来是昨天，我打了一场 CF，爆零了，掉分到 newbie ，又被嘲讽了。

为了方便下标从 0 开始，即 i,j,a_{i,j} 的范围都是 [0,n)。

如果只有 UDLR 操作，维护两位的错位即可。

这个 IC 操作有很多性质，比如先 I 再 C 和直接 I 形成的矩阵正好是右上-左下翻转关系。

假如把一个题目中描述的矩阵看成 n\times n 个 (i,j,a_{i,j}) 三元组组成的集合，那么 I 就是让所有 (i,j,a_{i,j}) 变成 (i,a_{i,j},j)，C 就是让所有 (i,j,a_{i,j}) 变成 (a_{i,j},j,i)。

对于一个三元组 (i,j,k)，每次 R 就是让它变成 (i,(j+1)\bmod n,k)，LDU 同理。

所以可以维护对于每个三元组，原来的 3 维现在变到哪了，以及 3 维当前各有多少错位。

由于对于每个三元组情况是一样的，所以可以每次 \Theta(1) 维护。

然后最后把矩阵按变化构造即可，总时间复杂度 \Theta(n^2+m)。

代码

我菜，参考了 tourist 的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;

//Data
const int N=1000;
int n,m,a[N][N][3],b[N][N];
int p[3],o[3],f[3];
string str;

//Main
void Main(){
    cin>>n>>m;
    R(t,3) f[o[t]=t]=0;
    R(i,n)R(j,n){
        cin>>a[i][j][2],--a[i][j][2];
        a[i][j][0]=i,a[i][j][1]=j;
    }
    cin>>str;
    for(char c:str){
        if(c=='R') f[1]++;
        else if(c=='L') f[1]--;
        else if(c=='D') f[0]++;
        else if(c=='U') f[0]--;
        else if(c=='I') swap(o[1],o[2]),swap(f[1],f[2]);
        else if(c=='C') swap(o[0],o[2]),swap(f[0],f[2]);
    }
    R(i,3) (((f[i]%=n)+=n)%=n);
    R(i,n)R(j,n){
        R(t,3) p[t]=(a[i][j][o[t]]+f[t])%n;
        b[p[0]][p[1]]=p[2];
    }
    R(i,n)R(j,n) cout<<b[i][j]+1<<" \n"[n-j==1];
    cout<<'\n';  
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t; for(cin>>t;t--;Main());
    return 0;
}

祝大家学习愉快！