自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:36:06，当前版本为作者最后更新于2022-02-04 23:08:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

不困难但非常有意思的题目。

我们先考虑一下，假设第一次调用了 Query(pos)：

• 返回 $-1$：最快的方法显然是把 $[1,n-pos]$ 的方法搬到 $[pos+1,n]$ 上。
• 返回 $0$：最快的方法是在 $[1,pos]$ 和 $[pos,n]$ 上分别二分左右端点。(*)
• 返回 $1$：最快的方法显然是当作 $[1,pos-1]$ 的问题做。

(*) 似乎不太显然，此处给出证明：
再调用 Query(pos) 已经没有意义；对于 $u<pos$ 调用 Query(u) 只能得到待猜区间左端点和 $u$ 的大小关系（大于或小于等于）；对于 $u>pos$ 调用 Query(u) 只能得到待猜区间右端点和 $u$ 的大小关系（小于或大于等于）。
这样原问题就变成了两个互不影响的问题（分别猜测左右端点），每个问题都可以用一次询问来得到两种答案之一，因此至少需要 $\lceil\log_2|L|\rceil+\lceil\log_2|R|\rceil$ 次询问，其中 $|L|,|R|$ 表示两个问题的可能解集大小。
这两个问题都是经典二分问题，使用二分恰好能做到上面给出的最小值。因此二分即为最优。

那么，如果记保证能猜对的最小猜测次数为 $f(n)$，显然有：

$f(n)=1+\min\limits_{1\le a\le n}\{\max\{f(a-1),f(n-a),\lceil\log_2a\rceil+\lceil\log_2(n-a+1)\rceil\}\}$

边界条件为 $f(0)=f(1)=0$。

在 init() 内如此暴力递推并记录转移位置即可获得 $100$ 分。我没写这部分做法，不保证这句话正确

注：$f(1500)=20$。出题人卡的很死（无贬义或辱骂情绪）。

---

那么 $101$ 分做法呢？

上面的递推很难优化，我们应该试图寻找最优转移位置的规律。记 $n$ 的最小最优转移位置为 $p(n)$。

我写了一段打表 js：

f=[0,0];
p=[0,1];
for(n=2;n<=99;++n)
{
    f.push(n);p.push(1);
    for(i=1;i<=n;++i)
    {
        c=1+Math.max(Math.ceil(Math.log2(i))+Math.ceil(Math.log2(n-i+1)),f[i-1],f[n-i]);
        if(c<f[n]) f[n]=c,p[n]=i;
    }
}
console.log(p);

观察输出结果，规律实在太明显了：

[0, 1, 
 1, 
 1, 
 1, 2, 
 1, 2, 
 1, 2, 3, 4, 
 1, 2, 3, 4, 
 1, 2, 3, 4, 5, 6, 7, 8, 
 1, 2, 3, 4, 5, 6, 7, 8, 
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 
 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 
 1, 2, 3, 4]

稍微提炼一下，规律可以表示为：对于 $2^m\le n<2^{m+1}$，$p(n)=(n\bmod 2^{m-1})+1$。

此规律可以和 Bonus 中提到的其他规律使用数学归纳法一起证明。细节由读者补充。

那么我们就有了 $O(\log n)$ 计算 $p(n)$ 的方法，时间复杂度 $O(T\log^2n)$，显然不会超时。实测可以拿到 $101$ 分。

也可以把 $p(n)$ 搬到 init() 内进行线性预处理，时间复杂度 $O(n+T\log n)$。我没写这部分做法，不保证这句话正确

---

参考实现：

#include <utility>//因为这个 CE 了一次
int Query(int);//因为这个 CE 了第二次
inline int getGuessPosition(int len)//return in [0,len)
{
	int i=0;while(len>>i)++i;
	return len%(1<<(i-2));
}
inline std::pair<int,int> finalGuess(int l,int mid,int r)
{
	int l0,r0,mid0;
	l0=l,r0=mid;
	while(r0>l0)
	{
		mid0=(l0+r0)>>1;
		if(Query(mid0)) l0=mid0+1;else r0=mid0;
	}
	int a=l0;
	l0=mid,r0=r;
	while(r0>l0)
	{
		mid0=(l0+r0)>>1;
		if(Query(mid0+1)) r0=mid0;else l0=mid0+1;
	}//这两个二分实际上可以写一起
	int b=l0;
	return std::make_pair(a,b);
}
std::pair<int,int> guess(int l,int r)
{
	if(l==r) return std::make_pair(l,r);
	int pos=l+getGuessPosition(r-l+1);
	int ret=Query(pos);
	if(ret==-1) return guess(pos+1,r);
	if(ret==0) return finalGuess(l,pos,r);
	return guess(l,pos-1);//一开始 1 和 -1 应该执行的操作写反了一次
}
std::pair<int,int> Guess(int n,int c)
{
	return guess(1,n);
}
void init(){}

---

Bonus：$f(n)$ 的表达式

用上面那段程序计算 $f(n)$，规律也很明显：

[0, 0, 
 2,
 3,
 4, 4,
 5, 5,
 6, 6, 6, 6,
 7, 7, 7, 7,
 8, 8, 8, 8, 8, 8, 8, 8,
 9, 9, 9, 9, 9, 9, 9, 9,
 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
 13, 13, 13, 13]

也就是：对于 $2^m\le n<2^{m+1}$，$f(n)=2m+[n\ge3\cdot2^{m-1}]$。

容易发现 $m+[n\ge3\cdot2^{m-1}]$ 可以表示为 $\lfloor\log_2\frac{4n}3\rfloor$，因此 $f(n)=\lfloor\log_2n\rfloor+\lfloor\log_2\frac{4n}3\rfloor$，与题目中的表达式一致。出题人你卡的真死（无贬义或辱骂情绪）。

---

Bonus Bonus：所有最优转移位置

上面我们只计算了最小最优转移位置，那么所有最优转移位置是个什么情况呢？

我们用 $P(n)$ 代表 $n$ 的所有最优转移位置构成的集合。

仍然使用上面那段程序，计算结果我使用 Excel 可视化了一下：

标灰代表此位置不存在，标黑代表这是最优转移位置，标白代表这不是最优转移位置。

稍微提炼一下：对于$2^m\le n<2^{m+1}$，$1\le i\le n$，$i\in P(n)$ 当且仅当 $(i-1)\bmod 2^{m-1}\ge n\bmod 2^{m-1}$。

结论和图片都很美。

P.S. 可以算出（图形无穷大时）$S=\dfrac{5}{24}a^2$，$a$ 为底边长。