当前位置：首页 > news >正文

LGP7115 [NOIP 2020] 移球游戏学习笔记

news 2025/9/16 18:05:48

LGP7115 [NOIP 2020] 移球游戏学习笔记

Luogu Link

前言

$\texttt{NOIP2020}$ 笑传之 $\texttt{Change Content of Balls.in}$。

致敬传奇修改文件选手我也不知道是谁。

题意简述

你面前有 $n+1$ 根柱子。对于前 $n$ 个柱子，每根上有 $m$ 个球，而第 $n+1$ 根初始是空的。对于这 $n\times m$ 个球，它们分为 $n$ 种颜色，每种 $m$ 个球。

对于两根筑紫 $a$ 和 $b$，你可以将 $a$ 最上方的球移到 $b$ 的最上方，前提是移动后 $b$ 的球数不大于 $m$。

你的任务是：对于 $i\in [1,n]$，使得颜色相同的球落到同一根柱子上。另外，请在 $820000$ 次内达成该目标。

$2\le n\le 50$，$2\le m\le 400$。特别地，有 $10\text{pts}$ 的部分分满足 $n=2$。

做法解析

先思考 $n=2$ 的做法。或者再具体点，如果我们想把所有颜色为 $1$ 的球挪到一个柱子上，你应该做什么？

实际上这意味着，你需要对于每根柱子，都把它颜色为 $1$ 的和非 $1$ 的球彻底分离开。设这根柱子上有 $x$ 个颜色为 $1$ 的，这说明你需要让其它柱子中有一个空缺 $x$ 格的，有一个空缺 $m-x$ 格的（其它柱子则都填满了），这种局面下你才可以把它们分离干净。

正确性显然。我们来想想具体的操作顺序。

设有 $a,b,c$ 三个筑紫，$c$ 为空栈，我们希望造出一个全 $1$ 的柱子，而此时 $a$ 有 $x$ 个 $1$。首先，我们将 $b$ 中 $\min(x,m-x)$ 个球放到 $c$ 上，接着我们用 $a$ 的 $0$ 和 $1$ 分别填满 $b$ 和 $c$，然后再把来自 $a$ 的 $0$ 段和 $1$ 段先后放回 $a$（球少的那段后放），此时 $a$ 的 $0$ 和 $1$ 已经泾渭分明了。接下来，我们把 $c$ 中的球都移到 $b$ 上，再把 $a$ 上面那段移到 $c$ 中，最后 $b$ 中的球就可以简单分类了。注意，此时最后的空段变成 $c$ 了。

操作次数？$\frac{m}{2}+m+m+\frac{m}{2}+\frac{m}{2}+m=\frac{9m}{2}$。如果实现差的话可能是 $6m$。

接下来怎么扩展到正解呢？答案很简单：$01$ 值域分治！我们建一棵分治树，从 $[1,n]$ 开始，对于值域区间 $[l,r]$，将 $[1,mid]$ 内的所有颜色视为 $0$，$(mid,n]$ 内的颜色视为 $1$，先把这个意义下的 $0$ 和 $1$ 分开，然后依此类推分治下去，最后就做完了。对于每一层的 $r-l+1$ 根柱子，我们就要做 $r-l$ 次操作，每次选定两根柱子时，如果 $0$ 多就提取 $0$，$0$ 的个数可能大于 $m$，此时不妨将一些 $0$ 暂时视作 $1$。反之亦然。

最终的操作次数是 $O(nm\log n)$ 带一点常熟。大概在 $5.4 \times 10^5$ 左右，能过的！

代码实现

代码得把每一步都想清楚。详见注释版代码。

#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=55,MaxM=405;
int N,M,C[MaxN][MaxM],ktp[MaxN],T[MaxN][MaxM];
vector<pii> ans;queue<int> cur;
int acnt[2],tar,cem,wtd;
void amove(int a,int b){ans.push_back({a,b});ktp[b]++;C[b][ktp[b]]=C[a][ktp[a]];T[b][ktp[b]]=T[a][ktp[a]];ktp[a]--;
}
void extract(int a,int b,int mid){for(int i=1;i<=M;i++)T[a][i]=(C[a][i]>mid),T[b][i]=(C[b][i]>mid);acnt[0]=acnt[1]=0;for(int i=1;i<=M;i++)acnt[0]+=T[a][i],acnt[1]+=T[b][i];if(acnt[0]+acnt[1]<M){for(int i=1;i<=M;i++)T[a][i]^=1,T[b][i]^=1;acnt[0]=M-acnt[0],acnt[1]=M-acnt[1];}for(int i=1;i<=min(acnt[0],M-acnt[0]);i++)amove(b,cem);int flg=(acnt[0]<=M-acnt[0]);for(int i=M;i>=1;i--)amove(a,T[a][i]^flg?cem:b);for(int i=1;i<=max(acnt[0],M-acnt[0]);i++)amove(cem,a);for(int i=1;i<=min(acnt[0],M-acnt[0]);i++)amove(b,a);while(ktp[cem])amove(cem,b);for(int i=1;i<=min(acnt[0],M-acnt[0]);i++)amove(a,cem);wtd=T[a][1]?cem:a;for(int i=M,tar;i>=1;i--){tar=(T[b][i]^(wtd==cem)?cem:a);if(tar==a&&ktp[a]==M)tar=cem;if(tar==cem&&ktp[cem]==M)tar=a;amove(b,tar);}cem=b;
}
void solve(int l,int r){if(l==r)return;int mid=(l+r)>>1;for(int i=1;i<=N+1;i++)if(i!=cem&&l<=C[i][1]&&C[i][1]<=r)cur.push(i);while(cur.size()>1){int ca=cur.front();cur.pop();int cb=cur.front();cur.pop();extract(ca,cb,mid);cur.push(wtd);}cur.pop();solve(l,mid),solve(mid+1,r);
}
int main(){readis(N,M);for(int i=1;i<=N;i++)for(int j=1;j<=M;j++)readi(C[i][j]);cem=N+1;for(int i=1;i<=N;i++)ktp[i]=M;solve(1,N);writil(ans.size());for(auto [x,y] : ans)printf("%d %d\n",x,y);return 0;
}