P7115 [NOIP2020] 移球游戏

link
这道题我觉得是我做到过极好的构造题了，思路和优化的方法都比较有特点，对数据点范围的分析已经对数据的给分也比较恰到好处。之前做了这道题，特此写一篇题解。

首先要批判一下给的小样例，对解题很容易起到反作用。所以构造题不能只看样例，要自己去手搓一下，这样才方便去做。

本题我们可以把数据点分为三个部分，其对应分别为N=2的部分，时间复杂度为 \(O(n^2 m)\) ,以及时间复杂度为 \(O(nmlogn)\)的部分。

Sub1：n=2

看到这道题，我们就应该想到一道题面看上去极其相似的题目：汉诺塔。于是我们可以仿照汉诺塔的思路，找规律来完成此题。

此时我们假设有三根柱子 \(x,y,z\) ,初始的球在 \(x,y\) 上，\(z\) 为空柱子。
此时我们想要把1号球全部移到一根柱子上。假设现在有 \(c\) 个球在 \(x\) 柱上。

Step1：将 \(y\) 柱上 \(c\) 个球移动到空的柱子 \(z\) 上。目的：为移动 \(x\) 柱上的球以分类提供空间。
Step2：对 \(x\) 柱上的每个球进行分讨。具体的说，若当前球为1号球，则将其移至 \(y\) 柱上；否则，将其移至 \(z\) 柱上。目的：区分出 \(x\) 柱上每一个球。
Step3：将 \(z\) 柱上的 \((m-c)\) 个球移动到 \(x\) 柱上。
Step4：将 \(y\) 柱上的 \(c\) 个球移动到 \(x\) 柱上。 Step3、Step4目的：将 \(x\) 柱上的球整理为1号球在上，2号球在下
Step5：将 \(z\) 柱上的 \(c\) 个球移动到 \(y\) 柱上。 目的：讲 \(z\) 柱腾空，方便下一步操作
Step6：将 \(x\) 柱上的 \(c\) 个球移动到 \(z\) 柱上。 目的：就是将1号球全部移到另一根柱子上
Step7：对 \(y\) 柱上的每一个球进行分讨。具体的说，若当前球为1号球，则将其移至 \(z\) 柱上；否则，将其移至 \(x\) 柱上。目的：完成操作

这样，七步操作结束后，我们可以得到 \(x\) 柱上全是2号球，\(z\) 柱上全是1号球。时间复杂度为 \(O(m)\),可以过掉n=2的测试点。同时，这些操作也是这道题目的根本。

Sub2

我们的目的是整理好n根柱子上的球。此时我们可以一根一根的去做，从n到2依次递归完成。

具体做法：

假设我们现在要整理好第 \(k\) 种球。此时第 \(i\) 号柱子上有 \(c_i\) 个颜色为 \(k\) 的球。

Step1：枚举 \(i\) ：从1到n 目的：将所有颜色为 \(k\) 的球移到该柱子的顶端；

更具体一点的操作：
（一）：将 \(k\) 柱上 \(c_i\) 个球移到 \((k+1)\) 柱上。 目的：为 \(k\) 柱移动出 \(c_i\) 个空位。
（二）：对 \(i\) 柱上每一个球进行分讨。具体的说，若当前球颜色为 \(k\) ，则将其移动至 \(k\) 柱上，否则，则将其移动至 \((k+1)\) 柱上。目的：对 \(i\) 柱上每一个球进行区分筛选。
（三）：将 \((k+1)\) 柱上 \((m-c_i)\) 个球移回 \(i\) 柱上。目的：没什么目的，就是把其他球移回原柱底部
（四）：将 \(k\) 柱上 \(c_i\) 个球移回 \(i\) 柱上。 目的：没什么目的，就是把 \(k\) 球移动到原柱顶部
（五）：将 \((k+1)\) 柱上 \(c_i\) 个球移至 \(k\)。 目的：为下次操作留好一个空柱子。

Step2：枚举 \(i\) :将 \(i\) 柱顶端为 \(k\) 的球移到 \((k+1)\) 柱上。

Step3：对 \(k\) 柱上每一个球进行分讨。具体的说，若当前球颜色为 \(k\) 则将其移动至 \((k+1)\) 柱上，否则，则将其随便移动到一个未满的柱子上。

然后我们递归去做每一次。一共要递归 \((n-1)\) 次。上述操作的时间复杂度为 \(O(nm)\) ，则总时间复杂度为 \(O(n^2m)\) ,可以得到70的高分。

Sub3

考虑对时间复杂度进行优化。上述过程可以分为两个部分去看，分别为执行操作与递归。发现操作的复杂度不好优化，选择优化递归。考虑多根颜色一起做，即分治算法。
建立一个 \(solve\) 函数，定义 \(mid=l+r>>1\),表示将所有颜色小于等于 \(mid\) 的球与颜色大于 \(mid\) 的球区分开。
即：不存在一根柱子上同时存在颜色大于等于 \(mid\) 的球与颜色小于 \(mid\) 的球，然后分治即可。

如何区分：每轮取出 \((r-l+1)\) 根柱子，每次取出两根柱子，若颜色小于等于 \(mid\) 的球数大于 \(m\) ,则任选 \(m\) 个小于等于 \(mid\) 的球，对其进行 \(Sub1\) 中的操作。大于同理。

分治总共要 \(logn\) 层。每次操作为 \(O(nm)\) 的时间复杂度，所以总时间复杂度为 \(O(nmlogn)\) 可以A掉此题。

这真是一道不可多得的构造好题娃。

哦还有代码

CODE

#include<bits/stdc++.h>
//#define int long long 
#define pa pair<int,int>

#define x first

#define y second

#define pb push_back

#define mp make_pair


using namespace std;

const int N=60,M=410,Q=820001;

int n,m;
int em;
int top[N],a[N][M];
bool impx[M],impy[M];

int T;
pa ans[Q];

void move(int x,int y)
{
	ans[++T]=mp(x,y);
	a[y][++top[y]]=a[x][top[x]--];
}

int merge(int x,int y,int mid)
{
	int cx=0,cy=0;
	
	for(int i=1;i<=m;++i)
		impx[i]=(a[x][i]<=mid),impy[i]=(a[y][i]<=mid),
		cx+=impx[i],cy+=impy[i];
		
	if(cx+cy>m)
	{
		cx=m-cx,cy=m-cy;
		for(int i=1;i<=m;++i)
			impx[i]^=1,impy[i]^=1;
	}	
	
	for(int i=1;i<=m;++i)
		if(!impx[i] && cx+cy<m)
			impx[i]=1,++cx;	
				
	for(int i=cx;i;--i)	move(y,em);
	for(int i=m;i;--i)
		if(impx[i])	move(x,y);
		else move(x,em);
	for(int i=m-cx;i;--i)	move(em,x);
	for(int i=cx;i;--i)	move(y,x);
	for(int i=cx;i;--i)	move(em,y);
	for(int i=cx;i;--i)	move(x,em);
	for(int i=m;i;--i)
		if(impy[i])	move(y,em);
		else 		move(y,x);
		
	int p=em;
	em=y;
	return p;
}

void solve(int l,int r)
{
	if(l==r)	return;
	
	int mid=l+r>>1;
	vector<int> now;
	
	for(int i=1;i<=n+1;++i)
	{
		if(i==em)	continue;
		if(l<=a[i][1] && a[i][1]<=r)
			now.pb(i);
	}
	
	for(int i=0;i+1<now.size();++i)
		now[i+1]=merge(now[i],now[i+1],mid);
		
	solve(l,mid),solve(mid+1,r);
}

signed main()
{
	freopen("ball.in", "r", stdin);
    freopen("ball.out", "w", stdout);

//	ios::sync_with_stdio(false);
//	cin.tie(0);cout.tie(0);
	
	scanf("%d%d",&n,&m);
	em=n+1;
	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			scanf("%d",&a[i][j]);
			
	for(int i=1;i<=n;i++)	top[i]=m;
	
	solve(1,n);
	
	printf("%d\n",T);
	for(int i=1;i<=T;++i)
		printf("%d %d\n",ans[i].first,ans[i].second);
		
	return 0;
}

哦，留个问题：为什么这道题关闭了输入输出流的cin,cout会比scanf,printf慢那么多？差点洛谷上过不了~~~（我太鶸了）