题解 P7115 【移球游戏】

· · 题解

2020.12.19 upd：更新了时间复杂度与操作次数。

思路：分治 + 构造

个人认为这是 NOIP 历年以来最有思维含量的题目之一。

题解：

我们先考虑 n=2 的情况，个人认为用优秀的算法解决这一档部分分是通往正解的唯一途径。

由于 CCF 十分的良心，用他自己辛辛苦苦写的正解跑了第二个样例，然后考场上我就瞪着这个样例瞪出了优秀的做法。

我们考虑要把第一根柱子上的颜色 1 和颜色 0 分离开来，于是我们就要是状态最后变成第一根柱子上为原来第一根柱子上所有的 1，第二根柱子上为原来第二根柱子上所有的 0。我们设原来第 1 根柱子上有 s 个 1 于是我们就可以进行以下操作：

\texttt{Step\ 1}

\texttt{Step\ 2}

\texttt{Step\ 3}

\texttt{Step\ 4}

\texttt{Step\ 5}

于是，我们就解决了 n=2 的情况的优秀算法，操作次数为:

s+m+m+(m-s)+(m-s)+m=5m-s

这指引我们走向了正解。

对于只有两种颜色的情况我们很好解决，但是对于多种颜色，我们就很那解决，所以我们就要尽可能将多种颜色转化为两种颜色去求解，我们可以想到设一个阀值 x，使 \le x 的数全部变为 1，>x 的数全部变为 0，然后将 [1,x] 和 [x+1,n] 分治求解。很显然对于每个区间 [l,r] ，将 x 设为 \lfloor\frac{l+r}{2}\rfloor 时操作次数是最优的。

每次 solve(l,r) ，我们将 [l,mid] 和 [mid+1,r] 中没有复原的柱子两两匹配，我们令两根柱子分别为 i 和 j，这样，i 和 j 中如果 \le mid 的个数大于 >mid 的个数，那么将 i 还原，否则将 j 还原，然后继续递归下去 solve(l,mid) 和 solve(mid+1,r) 就行了。

操作次数：

T(n)=2T(n/2)+5mn T(n)=5mn\log n

时间复杂度\mathcal{O}(5mn^2\log n)

\mathcal{View\ Code} 
#include<bits/stdc++.h>
using namespace std;
const int N=55,M=405,K=820005;
int a[N][M],top[N],n,m,ans[K][2],tot;bool flag[N];
inline void pour(int x,int y) 
{
    ans[++tot][0]=x,ans[tot][1]=y;
    a[y][++top[y]]=a[x][top[x]--];
}
void solve(int l,int r)
{
    if(l==r) return;
    int mid=l+r>>1;
    memset(flag,0,sizeof(flag));
    for(int i=l;i<=mid;i++)
        for(int j=mid+1;j<=r;j++)
        {
            if(flag[i] || flag[j]) continue;
            int s=0;for(int k=1;k<=m;k++) s+=(a[i][k]<=mid);
            for(int k=1;k<=m;k++) s+=(a[j][k]<=mid);
            if(s>=m) //<=mid 
            {
                s=0;for(int k=1;k<=m;k++) s+=(a[i][k]<=mid);
                for(int k=1;k<=s;k++) pour(j,n+1); //1
                while(top[i]) a[i][top[i]]<=mid?pour(i,j):pour(i,n+1); //2
                for(int k=1;k<=s;k++) pour(j,i);
                for(int k=1;k<=m-s;k++) pour(n+1,i);
                for(int k=1;k<=m-s;k++) pour(j,n+1); //3
                for(int k=1;k<=m-s;k++) pour(i,j); //4
                while(top[n+1]) 
                {
                    if(top[i]==m || a[n+1][top[n+1]]>mid) pour(n+1,j);
                    else pour(n+1,i); 
                }
                flag[i]=1;
            }
            else //>mid
            {
                s=0;for(int k=1;k<=m;k++) s+=(a[j][k]>mid);
                for(int k=1;k<=s;k++) pour(i,n+1); //1
                while(top[j]) a[j][top[j]]>mid?pour(j,i):pour(j,n+1); //2
                for(int k=1;k<=s;k++) pour(i,j);
                for(int k=1;k<=m-s;k++) pour(n+1,j);
                for(int k=1;k<=m-s;k++) pour(i,n+1); //3
                for(int k=1;k<=m-s;k++) pour(j,i); //4
                while(top[n+1]) 
                {
                    if(top[j]==m || a[n+1][top[n+1]]<=mid) pour(n+1,i);
                    else pour(n+1,j); 
                }
                flag[j]=1;
            }
        }
    solve(l,mid);solve(mid+1,r);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) 
        for(int j=1,x;j<=m;j++)
            scanf("%d",&x),a[i][++top[i]]=x;
    solve(1,n);printf("%d\n",tot);
    for(int i=1;i<=tot;i++) printf("%d %d\n",ans[i][0],ans[i][1]);
    return 0;
}