P6347 [CCO2017] 移动数组 题解

free_fall · 2023-10-08 16:10:34 · 题解

关于这道题我有一种正常的写法和一种不需要大脑的写法，但是这里空白太小，正常的写不下……（其实是楼上的大佬已经讲得很详细了）。

于是我就来提供新的思路辣。

对一个二维数组的行和列进行数次 shift 操作，使得它最终变成一个和谐数组。

定义操作 move1(x,y) 为将第 x 行右移 y 次，move2(x,y) 为将第 x 列下移 y 次。

对于前 n-1 行，我们将需要转移到 (i,j) 的点的坐标记为 (x,y)，假设当前需要转移的数字是 9，我们可以这样转移：

move2(j,x-i):

move1(x,(j-y+m)%m)：

move2(j,i)：

如果非常不巧，我们需要移的数和目标位置在同一行，只先需这样：

move2(y,1);
move1(x+1,1);
move2(y,n-1);
x++,y=y%m+1;

做完上述操作后，如果需要移的数和目标位置在同一列，再这样：

move1(x,1);
y=y%m+1;

最后做一遍上面带图的操作即可。至此，我们已经完成了前 n-1 行，只有最后一行是处于无序的状态。上面的操作是将第 i+1 行作为中转站来移动，但是最后一行我们显然不可以这么做，于是我们将 (n-1,m) 这个点作为中转站转移，这里我们枚举的 i 是当前目标的列数，目标为 (n,i)，现在我要将 13 移到对应位置，看起来大概是这样的：

move2(m,1)：

move1(n,m-y)：

move2(m,n-1)：

move1(n,y)：

move1(n,m-i)：

move2(m,1)：

move1(n,i)：

move2(m,n-1)：

这样最后一列就解决了，到这里为止，我们几乎没有用到大脑就完成了……吗？其实有可能在你做完这些操作的时候最后的数组是长这样的：

看，这个 11 和 15 的位置反了，解决这一步是非常难想的，然而这篇题解就是要教你怎么绕开这种情况。简单来说，最后你做到这一步出现这种情况的概率接近二分之一，我们只需要充分发扬人类智慧，每次做完上述操作之后判断是否和谐，如果不和谐就随机打乱，重新再做一次。

看起来很玄学，但是这个代码跑出正解的的期望次数是 2，因为是常数可以忽略，最终时间复杂度依然是 O(n^3)，明显能过。

但是这里还有一些细节上的问题，比如这个 move 函数中的 y 有可能是负数，在这里的 spj 上判为错误，所以要加上 n 或者 m 取模，具体实现见代码：

#include<bits/stdc++.h>
using namespace std;
const int N=105,M=1e5+5;
int n,m,a[N][N],b[N],mark[N][N],id[N*N],top;
bool flag;
struct op{
    int op,x,y;
}st[M];
int rand(int l,int r){
    return rand()%(r-l+1)+l;
}
void move1(int x,int y){
    if(y%m==0)return;
    y=(y%m+m)%m;
    st[++top]={1,x,y};
    for(int i=1;i<=m;i++){
        b[(i+y-1)%m+1]=a[x][i];
    }
    for(int i=1;i<=m;i++){
        a[x][i]=b[i];
        id[a[x][i]]=(x-1)*m+i;
    }
    return;
}
void move2(int x,int y){
    if(y%n==0)return;
    y=(y%n+n)%n;
    st[++top]={2,x,y};
    for(int i=1;i<=n;i++){
        b[(i+y-1)%n+1]=a[i][x];
    }
    for(int i=1;i<=n;i++){
        a[i][x]=b[i];
        id[a[i][x]]=(i-1)*m+x;
    }
    return;
}
bool check(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]!=(i-1)*m+j-1)return false;
        }
    }
    return true;
}
int main(){
    srand(time(0));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            mark[i][j]=a[i][j];
            id[a[i][j]]=(i-1)*m+j;
        }
    }
    while(!check()){
        top=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                a[i][j]=mark[i][j];
                id[a[i][j]]=(i-1)*m+j;
            }
        }
        for(int i=1;i<=n;i++){
            int op=rand(1,2);
            if(op==1)move1(rand(1,n),rand(1,m-1));
            if(op==2)move2(rand(1,m),rand(1,n-1));
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<=m;j++){
                int x=(id[(i-1)*m+j-1]-1)/m+1,y=(id[(i-1)*m+j-1]-1)%m+1;
                if(x==i&&y==j)continue;
                if(i==x){
                    move2(y,1);
                    move1(x+1,1);
                    move2(y,n-1);
                    x++,y=y%m+1;
                }
                if(j==y){
                    move1(x,1);
                    y=y%m+1;
                }
                move2(j,x-i);
                move1(x,(j-y+m)%m);
                move2(j,n-x+i);
            }
        }
        for(int i=1;i<=m;i++){
            int x=(id[(n-1)*m+i-1]-1)/m+1,y=(id[(n-1)*m+i-1]-1)%m+1,flag=y==m;
            if(x==n&&y==i)continue;
            if(x==n-1)continue;
            if(flag){
                move1(n,1);
                y=y%m+1;
            }
            move2(m,1),move1(n,m-y);
            move2(m,n-1),move1(n,y);
            if(flag)move1(n,m-1);
            move1(n,m-i),move2(m,1);
            move1(n,i),move2(m,n-1);
        }
        int x=(id[(n-1)*m-1]-1)/m+1,y=(id[(n-1)*m-1]-1)%m+1;
        if(x!=n-1||y!=m){
            move2(m,1),move1(n,m-y);
            move2(m,n-1),move1(n,y);
        }
    }
    printf("%d\n",top);
    for(int i=1;i<=top;i++){
        printf("%d %d %d\n",st[i].op,st[i].x,st[i].y);
    }
    return 0;
}

其实这个对换两个数的操作可以稍微修改一下，但是思路过于复杂，这里就随便贴一下代码满足强迫症患者的需求吧：

#include<bits/stdc++.h>
using namespace std;
const int N=105,M=1e5+5;
int n,m,a[N][N],b[N],mark[N][N],id[N*N],top,cnt;
struct op{
    int op,x,y;
}st[M];
void move1(int x,int y){
    if(y%m==0)return;
    y=(y%m+m)%m;
    st[++top]={1,x,y};
    for(int i=1;i<=m;i++){
        b[(i+y-1)%m+1]=a[x][i];
    }
    for(int i=1;i<=m;i++){
        a[x][i]=b[i];
        id[a[x][i]]=(x-1)*m+i;
    }
    return;
}
void move2(int x,int y){
    if(y%n==0)return;
    y=(y%n+n)%n;
    st[++top]={2,x,y};
    for(int i=1;i<=n;i++){
        b[(i+y-1)%n+1]=a[i][x];
    }
    for(int i=1;i<=n;i++){
        a[i][x]=b[i];
        id[a[i][x]]=(i-1)*m+x;
    }
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            mark[i][j]=a[i][j];
            id[a[i][j]]=(i-1)*m+j;
        }
    }
    for(int i=1;i<n;i++){
        for(int j=1;j<=m;j++){
            int x=(id[(i-1)*m+j-1]-1)/m+1,y=(id[(i-1)*m+j-1]-1)%m+1;
            if(x==i&&y==j)continue;
            if(i==x){
                move2(y,1);
                move1(x+1,1);
                move2(y,n-1);
                x++,y=y%m+1;
            }
            if(j==y){
                move1(x,1);
                y=y%m+1;
            }
            move2(j,x-i);
            move1(x,(j-y+m)%m);
            move2(j,n-x+i);
        }
    }
    for(int i=1;i<m;i++){
        int x=(id[(n-1)*m+i-1]-1)/m+1,y=(id[(n-1)*m+i-1]-1)%m+1;
        if(y==i)continue;
        move1(n,m-y);
        if(cnt&1)move2(m,1);
        else move2(m,n-1);
        move1(n,y);
        move1(n,m-i);
        if(cnt&1)move2(m,n-1);
        else move2(m,1);
        move1(n,i);
        move1(n,m-y);
        if(cnt&1)move2(m,1);
        else move2(m,n-1);
        move1(n,y);
        cnt++;
    }
    if(a[1][m]!=m-1){
        for(int i=1;i<n;i++){
            if(i&1)move1(1,m-1);
            else move1(1,1);
            move2(m,n-1);
        }
        move2(m,n-1);
        if(n&1)move1(1,m-1);
        else move1(1,1);
    }
    printf("%d\n",top);
    for(int i=1;i<=top;i++){
        printf("%d %d %d\n",st[i].op,st[i].x,st[i].y);
    }
    return 0;
}