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

QwQcOrZ · 2020-12-07 14:53:22 · 题解

此题解纪念我在考场上通过了本题

考虑先枚举颜色，然后将此颜色的所有球移动到同一个柱子上

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 列我后面会讲，这里先讲构造方法：

还是为了方便，我们强制第 n+1 列是空的（没有任何球）

具体操作时可以维护一个数组 p，其中 p_i 表示当前第 i 列的柱子在最开始时的编号为 p_i

这样就可以通过 swap p 中的两个数来使柱子的排列方便我们构造
设 tot=t_1，将第 n 列最上面的 tot 个球移动到第 n+1 列

（这里用的还是 Step. 0 中的例子）
将第 1 列中的 1 全部移动到第 n 列，0 全部移动到第 n+1 列

具体过程就是如果第一列的最上面为 1 就移到第 n 列，否则移到第 n+1 列

此时可以发现第一列中的 0 和 1 被我们分离了
将第 n+1 列中的 m-tot 个 0 全部移回第 1 列（其中 tot 为第一步中的 t_1）
将第 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 列干啥）

开始的时候图长这样
像 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 的情况

这个应该挺好做的，这里简单介绍一下我的做法：

假设开始的图是这样的：
还是像 Step. 1 中的 1.2. 那样将第 1 列分解到第 2,3 列
然后再将分离后的丢回第 1 列（先 1 后 2）

这两步操作相当于将第一列排了个序
将第三列移回第二列，然后将第一列上面的 2 移到第三列
然后类似 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 一些小细节

所有对第 i 列的操作实际上都是对 p_i 进行的，因为上面说第 i 列只是方便思考，实际上时对 p_i 进行的操作
每次移完球需要动态更新 p 数组，否则会惨烈爆蛋
祝大家省选 rp++！

Code\ Below

#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;
}