DUTOJ-1007: 圆桌会议

参考博客：
https://blog.csdn.net/yefuner/article/details/78765921

分为以下几步：
①将数据分为三组
②利用矩阵理解较好

以
1 2 3 4 5 6 7 8 9
为例：

$\left[ \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix} \right] \tag{1}$

我们按行遍历输出结果即可
如果顺时针旋转，就改变初始输出的位置
我们用pos来标记当前在0的数字
通过取余和除法就可以定位元素，只需要给pos++即可

如果发生 2操作交换位置，分为两种情况
我们需要用一个数组来记录这样的列的置换关系
这里用
int order[3] = {0,1,2};

int order[3] = {0,1,2};
①如果2操作发生在0列的时候就是一个矩阵的变换，将第一列和第三列进行置换
order[3] = {2,1,0};
$\left[ \begin{matrix} 3 & 2 & 1 \\ 6 & 5 & 4 \\ 9 & 8 & 7 \end{matrix} \right] \tag{2}$

②如果2操作发生在 1 或者 2列的时候

假如当前pos指到矩阵1的2位置，即座位0上数字2
这时候需要跨行来交换，

$\left[ \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix} \right] \tag{3}$

$\left[ \begin{matrix} 8 & 4 & 3 \\ 2 & 7 & 6 \\ 5 & 1 & 9 \end{matrix} \right] \tag{4}$

这个时候指针在1的2位置，其实我们是想访问4元素，就需要将矩阵3的第一列个自己的第0列建立关系，这个已经用order数组实现，现在还需要另一个数组来存储，
int col_offset[3] = {0,0,0};
对应的列内的偏移，观察矩阵1，发现2 和 4 在列的位置上差了1，所以就有

col_offset[order[cur_col]] = (col_offset[order[cur_col]]+1)%n;

同理，当我们遍历到矩阵1的4元素，要对用输出2，这个时候：
col_offset[order[t_col]] = (col_offset[order[t_col]]-1 + n)%n;

全部代码

#include <iostream>
#include <stdio.h>

using namespace std;
int a[100001][3];
int n,q;
int  order[3] = {0,1,2};
int col_offset[3] = {0,0,0};

void disp(int corrpos){
    for(int i=0;i<3*n;i++){
        int row = ( corrpos/3 + col_offset[order[corrpos%3]])%n;
        int col = order[corrpos %3];
        printf("%d%c",a[row][col],i==(3*n-1)?'\n':' ');
        corrpos++;
        corrpos %= 3*n;
    }
}

int main()
{

    int corrpos = 0;

    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i][0]);
        scanf("%d",&a[i][1]);
        scanf("%d",&a[i][2]);
    }
    for(int i=0;i<q;i++){
        //cout<<"corrpos "<<corrpos<<endl;
        //cout<<"fang "<<fang<<endl;
        int chose;
        scanf("%d",&chose);
        if(chose == 1){
            scanf("%d",&chose);
            corrpos -= chose;
            corrpos %= 3*n;
            corrpos += 3*n;
            corrpos %= 3*n;
        }else if(chose==2){
            int cur_col = corrpos%3;
            int t_col = (cur_col+2)%3;
            swap(order[cur_col],order[t_col]);
            if(cur_col>0){
                col_offset[order[cur_col]] = (col_offset[order[cur_col]]+1)%n;
                col_offset[order[t_col]] = (col_offset[order[t_col]]-1 + n)%n;
            }
        }

    }
    disp(corrpos);

    return 0;
}

总结：
将所有的数存在一个二维数组中，用两个一维数组来代替二维数组的数字交换，降低时间开销

DUTOJ-1007: 圆桌会议

相关推荐