题目描述
(n)个柱子，每个柱子上面(m)个大小相同、颜色不同的球，寻找一种移球方案使得每个柱子上面的球颜色相同。
题解
这题思维难度比较高，代码实现难度不大，考场打了一个假掉的做法，看了正解以后感觉非常之妙。
做法挺自然的，首先考虑只有两种颜色的情况：
- 考虑将所有黑色的球移动到白色的球上方。具体来说：先将要操作的柱子找出来，找到其里面有多少个黑球（设有(k)个），将随便另外一个柱子最上方的(k)个球移到空柱上，然后操作这个柱子，将黑球移到我们选的柱子上，白球移到空柱上，再将黑球和白球先后移会来，因为每时每刻空余位置数都是(m)，所以是合法的。
- 然后考虑将每种颜色的球移动到一个柱子上。可以考虑对于每一个要操作的柱子，找到另外一个要操作的柱子，分黑球数之和大于(m)和小于(m)来讨论，就可以容易实现。
对于(n>2)的情况，可以考虑分治，将所有球染为黑白两色，同颜色的也染为同颜色，然后给这些球各自分配一半的柱子，然后继续递归下去就可以解决了。大概计算一下，总共的移球次数是在(800000)左右。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 60
#define M 500
using namespace std;
int n,m,i,j,c[N][M],ans,ans1[1000000][3],num,id[M],cnt[N];
int read(){
int x=0;
char ch=getchar();
while (ch>'9'||ch<'0') ch=getchar();
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x;
}
void move(int x,int y,int num){
int i;
for (i=1;i<=num;i++){
cnt[x]--;cnt[y]++;
c[y][cnt[y]]=c[x][cnt[x]+1];c[x][cnt[x]+1]=0;
ans++;
ans1[ans][1]=x;ans1[ans][2]=y;
}
}
void dfs(int l,int r){
int mid=(l+r)/2,i,j,sum,x,y,s1,s2;
if (l==r) return;
num=0;
for (i=1;i<=n;i++)
if (c[i][1]>=l&&c[i][2]<=r)
id[++num]=i;
for (i=1;i<=num;i++){
sum=0;
x=id[i];y=id[i%num+1];
for (j=1;j<=m;j++)
if (c[x][j]>=l&&c[x][j]<=mid) sum++;
if (!sum) continue;
move(y,n+1,sum);
s1=s2=0;
for (j=m;j>=1;j--){
if (s1>=sum) break;
if (c[x][j]>=l&&c[x][j]<=mid){
s1++;
move(x,y,1);
}
else{
s2++;
move(x,n+1,1);
}
}
move(n+1,x,s2);
move(y,x,s1);
move(n+1,y,s1);
}
for (i=1;i<=num-1;i++){
x=id[i];y=id[i%num+1];
s1=s2=0;
for (j=1;j<=m;j++){
if (c[x][j]>=l&&c[x][j]<=mid) s1++;
if (c[y][j]>=l&&c[y][j]<=mid) s2++;
}
if (s1==m||s1==0) continue;
if (s1+s2>m){
move(x,n+1,m);
move(y,x,s2);
move(n+1,y,m-s1);
move(n+1,x,m-s2);
move(n+1,y,cnt[n+1]);
}
else{
move(x,n+1,s1);
move(y,n+1,s2);
move(y,x,s1);
move(n+1,y,s1+s2);
}
}
dfs(l,mid);dfs(mid+1,r);
}
int main(){
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
n=read();m=read();
for (i=1;i<=n;i++){
cnt[i]=m;
for (j=1;j<=m;j++)
c[i][j]=read();
}
dfs(1,n);
printf("%d
",ans);
for (i=1;i<=ans;i++) printf("%d %d
",ans1[i][1],ans1[i][2]);
return 0;
}