题解 P7115 【移球游戏（洛谷民间数据）】

_此题解纪念我在考场上通过了本题_ 考虑先枚举颜色，然后将此颜色的所有球移动到同一个柱子上 ### Step. 0 问题的转换 假设原来是这么一组数据：  为了方便，我们将每个柱子看作一列，从左到右标号为 $1..n$ 记 $now$ 表示当前枚举到的颜色，令所有 $a_{i,j}=now$ 的位置为 $1$，$a_{i,j}\not=now$ 的位置为 $0$ 记 $t_i$ 表示第 $i$ 列 $1$ 的个数 当 $now=1$ 时，那么图就变成了这个样子：  这时问题的目标就转化为了将所有的 $1$ 移到同一列上 ### Step. 1 制造全 $0$ 列 考虑对于每个颜色先制造出一个全 $0$ 列，然后再制造全 $1$ 列 至于为什么要先制造全 $0$ 列我后面会讲，这里先讲构造方法： 0. 还是为了方便，我们强制第 $n+1$ 列是空的（没有任何球） 具体操作时可以维护一个数组 $p$，其中 $p_i$ 表示当前第 $i$ 列的柱子在最开始时的编号为 $p_i$ 这样就可以通过 `swap` $p$ 中的两个数来使柱子的排列方便我们构造 1. 设 $tot=t_1$，将第 $n$ 列最上面的 $tot$ 个球移动到第 $n+1$ 列  （这里用的还是 `Step. 0` 中的例子） 2. 将第 $1$ 列中的 $1$ 全部移动到第 $n$ 列，$0$ 全部移动到第 $n+1$ 列  具体过程就是如果第一列的最上面为 $1$ 就移到第 $n$ 列，否则移到第 $n+1$ 列 此时可以发现第一列中的 $0$ 和 $1$ 被我们分离了 3. 将第 $n+1$ 列中的 $m-tot$ 个 $0$ 全部移回第 $1$ 列（其中 $tot$ 为第一步中的 $t_1$）  4. 将第 $2$ 列中的 $0$ 分离到第 $1$ 列，$1$ 分离到第 $n+1$ 列（如果第一列塞不下 $0$ 了就往第 $n+1$ 列丢）  此时我们就构造出了一个全 $0$ 列！ 至于第四步中为什么 $0$ 的数量一定够，是因为前两列中 $1$ 的个数一定不大于 $m$，所以 $0$ 的个数一定 $\geq 2m-1的数量$ ，即 $\geq m$。而这四步的本质也就是将前两列中的 $0$ 全部分离到第一列中，所以一定能构造出一个全 $0$ 列 `Step. 1` 实际上就是用第 $1,2,n,n+1$ 列构造了一个全 $0$ 列 #### Step. 2 构造全 $1$ 列 我们在 `Step. 1` 中构造全 $0$ 列的目的自然是为了方便将所有的 $1$ 移到同一列 依然是为了方便，我们强制在构造全 $1$ 列时第 $n$ 列要为全 $0$，第 $n+1$ 列要为空 所以在构造了全 $0$ 列的之后需要 $swap(p_1,p_n),swap(p_2,p_{n+1})$ （因为这时第一列为全 $0$，第二列为空） 然后自然是通过全 $0$ 列和全空列构造全 $1$ 列了（不然上一步构造全 $0$ 列干啥） 0. 开始的时候图长这样  1. 像 `Step. 1` 中的 1.2. 那样将第 $1$ 列分解到第 $n,n+1$ 列  然后你就会发现第 $1$ 列中的 $1$ 全部被移到了第 $n$ 列的最上方，然后第 $n+1$ 列构成了一个新的全 $0$ 列 所以我们第一步中构造全 $0$ 列的目的就是保证在这步中，第 $n$ 列除了最上面的第一列中的 $1$，其它都为 $0$（否则第 $n$ 列的下方可能出现其它的 $1$，第 $n+1$ 列也不一定是全 $0$） 然后你又能发现你可以用第 $n+1$ 列新产生的全 $0$ 列和第 $2$ 列继续操作，再用新的全 $0$ 列和第 $3,4,...,n-1$ 列操作 所有操作完成后，所有的 $1$ 都被移到了柱子的最上方，这时就可以将所有 $1$ 都移到空行，然后再用全 $0$ 列去填充产生的空当 然后我们发现当前枚举的颜色已经合法，剩下的相当于要将 $n-1$ 根柱子的颜色分离，用同样的方法求解即可 ### Step. 3 $n=2$ 也许你以为本题的做法到这里就结束了？其实并没有 你会发现这个做法根本过不了样例 因为当 $n=2$ 时，第 $2$ 列和第 $n$ 列是同一列，也就是说不能用上面的方法制造全 $0$ 列 所以要特判 $n=2$ 的情况 这个应该挺好做的，这里简单介绍一下我的做法： 0. 假设开始的图是这样的：  1. 还是像 `Step. 1` 中的 1.2. 那样将第 $1$ 列分解到第 $2,3$ 列  2. 然后再将分离后的丢回第 $1$ 列（先 $1$ 后 $2$）  这两步操作相当于将第一列排了个序 3. 将第三列移回第二列，然后将第一列上面的 $2$ 移到第三列  4. 然后类似 `Step. 1` 中的 1.2. 那样将第 $2$ 列分解到第 $1,3$ 列，就能得到全 $1$ 列和全 $2$ 列了 ### Step. 4 操作次数分析 最外层枚举颜色一个 $n$ ，每次构造全 $1$ 列时需要 $nm+m$（因为 $1$ 的总个数为 $m$，所以分解时的第一步均摊的总次数为 $m$） 因为列数随着颜色一个一个处理完会减小，所以 $nm+m$ 中的 $n$ 其实是个等差数列，也就是 $\sum\limits_{i=1}^n im+m$。所以有个 $1/2$ 的常数 构造全 $0$ 列时上限需要 $4m$ 次，所以操作次数上限为 $\sum\limits_{i=1}^n im+5m$，极限数据满打满算要操作 $600,000$ 次，可以轻松通过本题 复杂度 $=$ 操作次数，所以不需要管它 ### Step. 5 一些小细节 1. 所有对第 $i$ 列的操作实际上都是对 $p_i$ 进行的，因为上面说第 $i$ 列只是方便思考，实际上时对 $p_i$ 进行的操作 2. 每次移完球需要动态更新 $p$ 数组，否则会惨烈爆蛋 3. 祝大家省选 rp++！ $Code\ Below$ ```cpp #include<bits/stdc++.h> using namespace std; const int N=55; const int M=405; const int OPT=820005; int read() { int s=0; char c=getchar(),lc='+'; while (c<'0'||'9'<c) lc=c,c=getchar(); while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar(); return lc=='-'?-s:s; } void write(int x) { if (x<0) { putchar('-'); x=-x; } if (x<10) putchar(x+'0'); else { write(x/10); putchar(x%10+'0'); } } void print(int x=-1,char c='\n') { write(x); putchar(c); } int L[OPT],R[OPT],CNT=0,n,m; int a[N][M],cnt[N],tot[N],p[N]; void move(int x,int y) { ++CNT; L[CNT]=x; R[CNT]=y; a[y][++cnt[y]]=a[x][cnt[x]--]; } int count(int x,int y) { int ret=0; for (int i=1;i<=m;i++) ret+=a[x][i]==y; return ret; } inline int top(int x) { return a[x][cnt[x]]; } int main() { freopen("ball.in","r",stdin); freopen("ball.out","w",stdout); n=read(); m=read(); for (int i=1;i<=n;i++) { cnt[i]=m; for (int j=1;j<=m;j++) a[i][j]=read(); } cnt[n+1]=0; for (int i=1;i<=n+1;i++) p[i]=i; //empty:n+1 //full :n for (int now=n;now>=3;now--) { int tmp=count(p[1],now); for (int i=1;i<=tmp;i++) move(p[now],p[now+1]); for (int i=1;i<=m;i++) if (top(p[1])==now) move(p[1],p[now]); else move(p[1],p[now+1]); for (int i=1;i<=m-tmp;i++) move(p[now+1],p[1]); for (int i=1;i<=m;i++) if (top(p[2])==now||cnt[p[1]]==m) move(p[2],p[now+1]); else move(p[2],p[1]); //构造全 0 列 swap(p[1],p[now]); swap(p[2],p[now+1]); for (int k=1;k<now;k++) { tmp=count(p[k],now); for (int i=1;i<=tmp;i++) move(p[now],p[now+1]); for (int i=1;i<=m;i++) if (top(p[k])==now) move(p[k],p[now]); else move(p[k],p[now+1]); swap(p[k],p[now+1]); swap(p[k],p[now]); } for (int i=1;i<now;i++) while (top(p[i])==now) move(p[i],p[now+1]); for (int i=1;i<now;i++) while (cnt[p[i]]<m) move(p[now],p[i]); //构造全 1 列 } int tmp=count(p[1],1); for (int i=1;i<=tmp;i++) move(p[2],p[3]); for (int i=1;i<=m;i++) if (top(p[1])==1) move(p[1],p[2]); else move(p[1],p[3]); for (int i=1;i<=tmp;i++) move(p[2],p[1]); for (int i=1;i<=m-tmp;i++) move(p[3],p[1]); while (cnt[p[3]]) move(p[3],p[2]); for (int i=1;i<=m-tmp;i++) move(p[1],p[3]); for (int i=1;i<=m;i++) if (top(p[2])==1) move(p[2],p[1]); else move(p[2],p[3]); //特判 n=2 print(CNT); for (int i=1;i<=CNT;i++) { print(L[i],' '); print(R[i]); } return 0; } ```