CF1458C Latin Square

对于一个排列 \(p_i\) ，将其表示为 \((i,p_i)\) , 那么它的逆排列可表示为 \((p_i,i)\)

这道题 \(i,j,a_{i,j}\) 均为排列，考虑用三元组 \((i,j,a_{i,j})\) 表示。（为了方便下标从 \(0\) 开始）

那么操作可表示为：

• R \((i,j,k) \to (i,(j+1)\bmod n,k)\)
• L \((i,j,k) \to (i,(j-1)\bmod n,k)\)
• D \((i,j,k) \to ((i+1)\bmod n,j,k)\)
• U \((i,j,k) \to ((i-1)\bmod n,j,k)\)
• I \((i,j,k) \to (i,k,j)\)
• C \((i,j,k) \to (k,j,i)\)

只需要记录每一维的偏移量与最终的位置即可。

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

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000 , MAXM = 1e5;
int T , n , m , a[ MAXN + 5 ][ MAXN + 5 ][ 3 ] , b[ MAXN + 5 ][ MAXN + 5 ];
char op[ MAXM + 5 ];

int tag[ 3 ] , p[ 3 ];
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 ++ ) {
                a[ i ][ j ][ 0 ] = i, a[ i ][ j ][ 1 ] = j;
                scanf("%d",&a[ i ][ j ][ 2 ]); a[ i ][ j ][ 2 ] --;
            }

        scanf("%s", op + 1 );
        for( int i = 0 ; i < 3 ; i ++ ) p[ i ] = i , tag[ i ] = 0;
        for( int i = 1 ; i <= m ; i ++ ) {
            if( op[ i ] == 'R' ) tag[ p[ 1 ] ] ++;
            if( op[ i ] == 'L' ) tag[ p[ 1 ] ] --;
            if( op[ i ] == 'D' ) tag[ p[ 0 ] ] ++;
            if( op[ i ] == 'U' ) tag[ p[ 0 ] ] --;
            if( op[ i ] == 'I' ) swap( p[ 1 ] , p[ 2 ] );
            if( op[ i ] == 'C' ) swap( p[ 0 ] , p[ 2 ] );
        } 
        for( int i = 0 ; i < 3 ; i ++ ) tag[ i ] = ( tag[ i ] % n + n ) % n;
        for( int i = 0 ; i < n ; i ++ )
            for( int j = 0 ; j < n ; j ++ )
                b[ ( a[ i ][ j ][ p[ 0 ] ] + tag[ 0 ] ) % n ][ ( a[ i ][ j ][ p[ 1 ] ] + tag[ 1 ] ) % n ] = ( a[ i ][ j ][ p[ 2 ] ] + tag[ 2 ] ) % n;
        for( int i = 0 ; i < n ; i ++ )
            for( int j = 0 ; j < n ; j ++ )
                printf("%d%c", b[ i ][ j ] + 1 , j == n - 1 ? '\n' : ' ' );
    }
    return 0;
}