1 条题解
-
0
自动搬运
来自洛谷，原作者为
free_fall
do not go gentle into that good night搬运于
2025-08-24 22:19:55，当前版本为作者最后更新于2023-10-08 16:10:34，作者可能在搬运后再次修改，您可在原文处查看最新版自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多
以下是正文
关于这道题我有一种正常的写法和一种不需要大脑的写法，但是这里空白太小，正常的写不下……（
其实是楼上的大佬已经讲得很详细了）。于是我就来提供新的思路辣。
对一个二维数组的行和列进行数次 shift 操作，使得它最终变成一个和谐数组。
定义操作 为将第 行右移 次， 为将第 列下移 次。
对于前 行，我们将需要转移到 的点的坐标记为 ，假设当前需要转移的数字是 ，我们可以这样转移：
$\begin{matrix} &0 &1 &2 &3 \\ &4 &5 &6 &7 \\ &8 &? &? &? \\ &? &? &9 &? \end{matrix}$
move2(j,x-i):
$\begin{matrix} &0 &? &2 &3 \\ &4 &1 &6 &7 \\ &8 &5 &? &? \\ &? &? &9 &? \end{matrix}$
move1(x,(j-y+m)%m)：
$\begin{matrix} &0 &? &2 &3 \\ &4 &1 &6 &7 \\ &8 &5 &? &? \\ &? &9 &? &? \end{matrix}$
move2(j,i)：
$\begin{matrix} &0 &1 &2 &3 \\ &4 &5 &6 &7 \\ &8 &9 &? &? \\ &? &? &? &? \end{matrix}$
如果非常不巧，我们需要移的数和目标位置在同一行，只先需这样：
move2(y,1); move1(x+1,1); move2(y,n-1); x++,y=y%m+1;做完上述操作后，如果需要移的数和目标位置在同一列，再这样：
move1(x,1); y=y%m+1;最后做一遍上面带图的操作即可。至此，我们已经完成了前 行，只有最后一行是处于无序的状态。上面的操作是将第 行作为中转站来移动，但是最后一行我们显然不可以这么做，于是我们将 这个点作为中转站转移，这里我们枚举的 是当前目标的列数，目标为 ，现在我要将 13 移到对应位置，看起来大概是这样的：
$\begin{matrix} &0 &1 &2 &3 \\ &4 &5 &6 &7 \\ &8 &9 &10 &11 \\ &12 &? &13 &? \end{matrix}$
move2(m,1)：
$\begin{matrix} &0 &1 &2 &? \\ &4 &5 &6 &3 \\ &8 &9 &10 &7 \\ &12 &? &13 &11 \end{matrix}$
move1(n,m-y)：
$\begin{matrix} &0 &1 &2 &? \\ &4 &5 &6 &3 \\ &8 &9 &10 &7 \\ &11 &12 &? &13 \end{matrix}$
move2(m,n-1)：
$\begin{matrix} &0 &1 &2 &3 \\ &4 &5 &6 &7 \\ &8 &9 &10 &13 \\ &11 &12 &? &? \end{matrix}$
move1(n,y)：
$\begin{matrix} &0 &1 &2 &3 \\ &4 &5 &6 &7 \\ &8 &9 &10 &13 \\ &12 &? &? &11 \end{matrix}$
move1(n,m-i)：
$\begin{matrix} &0 &1 &2 &3 \\ &4 &5 &6 &7 \\ &8 &9 &10 &13 \\ &? &11 &12 &? \end{matrix}$
move2(m,1)：
$\begin{matrix} &0 &1 &2 &? \\ &4 &5 &6 &3 \\ &8 &9 &10 &7 \\ &? &11 &12 &13 \end{matrix}$
move1(n,i)：
$\begin{matrix} &0 &1 &2 &? \\ &4 &5 &6 &3 \\ &8 &9 &10 &7 \\ &12 &13 &? &11 \end{matrix}$
move2(m,n-1)：
$\begin{matrix} &0 &1 &2 &3 \\ &4 &5 &6 &7 \\ &8 &9 &10 &11 \\ &12 &13 &? &? \end{matrix}$
这样最后一列就解决了，到这里为止，我们几乎没有用到大脑就完成了……吗？其实有可能在你做完这些操作的时候最后的数组是长这样的：
$\begin{matrix} &0 &1 &2 &3 \\ &4 &5 &6 &7 \\ &8 &9 &10 &15 \\ &12 &13 &14 &11 \end{matrix}$
看，这个 和 的位置反了，解决这一步是非常难想的，然而这篇题解就是要教你怎么绕开这种情况。简单来说，最后你做到这一步出现这种情况的概率接近二分之一，我们只需要充分发扬人类智慧，每次做完上述操作之后判断是否和谐，如果不和谐就随机打乱，重新再做一次。
看起来很玄学，但是这个代码跑出正解的的期望次数是 ，因为是常数可以忽略，最终时间复杂度依然是 ，明显能过。
但是这里还有一些细节上的问题，比如这个 函数中的 有可能是负数，在这里的 spj 上判为错误，所以要加上 或者 取模，具体实现见代码：
#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; }
15011418730
LV 7
@ 2025-8-24 22:19:55
- 1
