自动搬运

查看原文

来自洛谷，原作者为

	断清秋 黄金时代的眼泪 || 算法竞赛业余爱好者

搬运于2025-08-24 22:39:32，当前版本为作者最后更新于2022-08-12 14:13:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题意自己看。

考虑最小化 $m$ 的值，如果 $m=n$ 就有很显然的做法，直接随便问一个袋子把那个袋子的数写黑板上就行了，可以获得 $5pts$。

然后考虑一点比较聪明的策略，比较两个数大小没必要枚举，可以比较每一位的值就行，每次写一个数的最高位，比另一个数的相应位置即可。这样你需要记录黑板上的数是哪一位上的。假如你存的是一个 $b$ 进制数，那当前位取值就是 $[0,b)$，那这个跟 $n \times m$ 矩阵中的点 $(i,j)$ 一维映射成 $(i-1) \times m+j$ 是一样的。但是考虑最后一位为 $0$ 的情况，你需要跟初始状态为 $0$ 作区分，因此你只需要额外 $+1$，所以在第 $i$ 位的原数上加个 $(i-1) \times b+1$ 即可。

然后你考虑一共有 $\left\lceil\log_b n\right\rceil$ 位，每一位最大值为 $b-1$，所以 $m$ 的最大值为 $b(\left\lceil\log_b n\right\rceil-1)+1+b-1$，即 $m=b\left\lceil\log_b n\right\rceil$。

当 $n=5000$ 时，取 $b=3$ 得到最优解，此时 $m=24$。

然后考虑 $[1,m]$ 每个值都对应一次比较，那么减少需要比较的情况就相当于减少 $m$。发现 $A \neq B$，所以无论如何它们比较到最后一位时不会相等。而最后一位只有 $0,1,2$ 三种可能性，查询到最大值 $2$ 和最小值 $0$ 时都可以直接看，只有看到 $1$ 时需要再比较一次，那么也就是有两种情况不需要比较，于是可以做到 $m=22$。

但是会发现 $m=22$ 已经是这个做法瓶颈了，考虑一些新做法。

想象一棵搜索树，可以想到进制位这种做法类似链式结构，宽度不大而深度很深，考虑把这棵树改成类似线段树的形式，以宽度换深度。

那么不难想到类似线段树的结构，判断每个决策点可能属于哪个区间，每次递归下去，最后找到单点。

然后你惊喜地发现这个东西很有优化前途，因为每次递归到一个区间 $[l,r]$，都可以运用之前的优化去掉最大值最小值，使需要比较的区间变为 $[l+1,r-1]$，于是每次区间长度 $-2$。

然后这个东西显然全用 $3$ 进制就不是很优秀了，考虑 $2$ 和 $3$ 混合使用，然后你可以递推一下每一层比较用哪个底数比较好，其中一种比较优秀的方式是 $2,3,3,3,3,3,3$，然后这样就能做到 $m=20$。

这个东西实现很麻烦，需要微调底数位置，然后可以通过递归或者倍增实现。以下给出一份递归实现的代码。

代码：

#include<bits/stdc++.h>
#include"prison.h"
#define ll long long
#define back return
#define ri int
using namespace std;
vector<vector<int>> s;
void work(int p,int d,int id,int pl,int pr,int l,int r)
{
	int now=3*(d-1)+id;
	for(ri i=pl;i<=pr;i++)
		s[p][i]=now;
	for(ri i=l;i<=pl;i++)
		s[now][i]=-s[now][0]-1;
	for(ri i=pr;i<=r;i++)
		s[now][i]=s[now][0]-2;
	pl++,pr--;
	if(pl>pr)
		back ;
	if(pr-pl<=1)
	{
		work(now,d+1,1,pl,pr,pl-1,pr+1);
		back ;
	}
	if(pr-pl<=3)
	{
		int mid=(pl+pr)/2;
		work(now,d+1,1,pl,mid,pl-1,pr+1);
		work(now,d+1,2,mid+1,pr,pl-1,pr+1);
		back ;
	}
	int mid1=(pl*2+pr)/3,mid2=(pl+pr*2)/3;
	work(now,d+1,1,pl,mid1,pl-1,pr+1);
	work(now,d+1,2,mid1+1,mid2,pl-1,pr+1);
	work(now,d+1,3,mid2+1,pr,pl-1,pr+1);
}
vector<vector<int>> devise_strategy(int n)
{
	for(ri i=0;i<=20;i++)
		s.push_back(vector<int>(n+1,0));
	s[0][0]=s[4][0]=s[5][0]=s[6][0]=s[10][0]=s[11][0]=s[12][0]=s[16][0]=s[17][0]=s[18][0]=1;
	work(0,0,3,1,n,1,n);
	back s;	
}