P7115 [NOIP2020] 移球游戏 解法

· · 个人记录

本文同步发于博客园

题目链接

题意

有 n+1 根柱子，每个柱子能放下 m 个球，其中前 n 个上放满了颜色不同的球，共 n 种颜色，每种颜色 m 个球，每次可将某个柱子顶部的球移至另一个没放满的柱子的顶部，求任意一个将同种颜色的球均放在同一个柱子上的方案数不超过 820000 的方案。

做法

70 pts

考虑将所有柱子的某种颜色的球都移至顶部，对于每个柱子需要另外两个一满一空的帮助。

在此基础上我们再加一点常数上的优化，每次只移动方案数最优的那个颜色，再加一点其他对不必要操作的减少，即可获得 70 pts，比较考验码力。

正解

我们考虑 n=2 的做法。

先算出第一个柱子颜色较少的那个的数量，将第二个柱子的同数量的球移到空柱，然后将第一个柱子的球分类，再将同一颜色的放回第一个柱子，再将第二个柱子的球也分了，这样就能解决了。操作次数为：5m-s，其中 s 是第一个柱子中颜色较少的那个的数量。

然后我们考虑将这种做法扩展至 n>2：

我们可以采用归并分治的思想，将颜色 \le mid 的看作 1，将 >mid 的看作 2。那么，分治到最后，整个球也都分类完了。

计算方案数：

T(n)=2\times T(\frac{n}{2})+5\times m\times n T(n)=5\times m\times n\times logn

可以通过本题！

具体实现就看代码吧！

code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
inline int rd(){
    int x=0,id=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')id=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*id;
}
int n,m,a[55][405],ans[800003][2],top[55],tot;
bool fg[55];
inline void op(int x,int y){
    ans[++tot][0]=x,ans[tot][1]=y,a[y][++top[y]]=a[x][top[x]--];
}
void sol(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    memset(fg,0,sizeof(fg));
    for(int i=l;i<=mid;i++)//将其分成两种，小于等于mid，大于mid 
        for(int j=mid+1;j<=r;j++){
            if(fg[i]||fg[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){
                s=0;
                for(int k=1;k<=m;k++)s+=(a[i][k]<=mid);//一顿操作猛如虎 
                for(int k=1;k<=s;k++)op(j,n+1);
                while(top[i])a[i][top[i]]<=mid?op(i,j):op(i,n+1);
                for(int k=1;k<=s;k++)op(j,i);
                for(int k=1;k<=m-s;k++)op(n+1,i);
                for(int k=1;k<=m-s;k++)op(j,n+1);
                for(int k=1;k<=m-s;k++)op(i,j);
                while(top[n+1]){
                    if(top[i]==m||a[n+1][top[n+1]]>mid)op(n+1,j);
                    else op(n+1,i);
                }
                fg[i]=1;
            }else{
                s=0;
                for(int k=1;k<=m;k++)s+=(a[j][k]>mid);//反向 
                for(int k=1;k<=s;k++)op(i,n+1);
                while(top[j])a[j][top[j]]>mid?op(j,i):op(j,n+1);
                for(int k=1;k<=s;k++)op(i,j);
                for(int k=1;k<=m-s;k++)op(n+1,j);
                for(int k=1;k<=m-s;k++)op(i,n+1);
                for(int k=1;k<=m-s;k++)op(j,i);
                while(top[n+1]){
                    if(top[j]==m||a[n+1][top[n+1]]<=mid)op(n+1,i);
                    else op(n+1,j);
                }
                fg[j]=1;
            }
        }
    sol(l,mid);sol(mid+1,r);
}
int main(){
    n=rd(),m=rd();
    for(int i=1;i<=n;i++)
        for(int j=1,x;j<=m;j++)x=rd(),a[i][++top[i]]=x;
    sol(1,n);
    cout<<tot<<"\n";
    for(int i=1;i<=tot;i++)cout<<ans[i][0]<<" "<<ans[i][1]<<"\n";
    return 0;
}