自动搬运

查看原文

来自洛谷，原作者为

	Jason331 这个家伙很菜，什么也没有留下

搬运于2025-08-24 22:59:54，当前版本为作者最后更新于2024-08-29 19:33:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

因为本篇文章篇幅较长，博客食用更佳。

前言

解题方法 and 前置芝士

• 二分

• 倍增

• 分类讨论加模拟

请求添加标签

请求为本题添加 二分 与 倍增 标签，理由见本文。

虽然我不确定其他的方法是否要用到倍增，但是二分在本题中是绝对要用到的。

我与此题的关联

此题一大半的提交都被我拿下了，不写个题解都说不过去了……

对本题的评价

非常毒瘤好的一道既能烧脑训练思维又能把人逼疯锻炼码力的题目，能够全方位地摧残提升做题的 oier，非常适合推荐给与你勾心斗角忠心耿耿的朋友去做。

基础解题思路

前置定义

因为本文较长，特作如下定义：

• 将“第 $i$ 个夸克”简称为“夸克 $i$”（$1 \leq i \leq N$）。对于任意自然数 $2 \le a \le N$，夸克 $a$ 与夸克 $a - 1$ 之间不存在任何夸克，这个理由在下文中可能不会具体说明。

• $k_i$ 表示夸克 $i$ 的位置（$1 \leq i \leq N,1 \leq k_i \leq 10^{18}$）。

• $opt_x$ 表示与位置 $x$ 相距第二近的夸克有多少个（$-10^{18} \leq x \leq 2 \times 10^{18},1 \leq opt_x \leq 2$，有关“相距第二近的夸克”的定义请看题面）。

• $l_x$ 表示与位置 $x$ 相距第二近的夸克的距离（$-10^{18} \leq x \leq 2 \times 10^{18},1 \leq l_x \leq 10^{18} - 1$，有关“相距第二近的夸克”的定义请看题面）。

• 将“询问与位置 $x$ 相距第二近的夸克的距离与数量” 简称为“询问 $x$”（$-10^{18} \leq x \leq 2 \times 10^{18}$）。

• 将“存储夸克 $i$ 的位置（为 $x$）”简称为“标记 $k_i$（为 $x$）”（$1 \leq i \leq N,1 \leq x \leq 10^{18}$）（出现这个短语时如果没有说清标记位置，说明对于位置的推理极为简单，请联系上下文自行实现）。

开始的几个夸克

仔细阅读题面，我们可以推断出：

询问 $0$，可得：

$$\begin{cases} l_0 = k_2\\ opt_0 = 1 \end{cases}$$

然后询问 $k_2$，得到的一定是夸克 $1$ 和夸克 $3$ 中距离 $k_2$ 较近的一个夸克的距离（因为离位置 $k_2$ 最近的一定是夸克 $2$，距离为 $0$）,此时如果 $opt_{k_2} = 2$，就可以直接标记 $k_1$ 和 $k_3$ ，然后跳过此部分，直达 接下来——一个一个地找夸克。

但是如果 $opt_{k_2} = 1$，如何确定 $l_{k_2}$ 是夸克 $1$ 与夸克 $2$ 的距离还是夸克 $3$ 与夸克 $2$ 的距离呢？

询问 $k_2 - 1$。

分类讨论

1. $opt_{k_2 - 1} = 2$，直接标记 $k_1$。

2. $l_{k_2 - 1} = l_{k_2} - 1$，标记 $k_1$ 为 $k_2 - l_{k_2}$，原因略。

3. $l_{k_2} = l_{k_2 - 1} = 1$，标记 $k_1$ 为 $k_2 - 1$，原因略。

如果上面三种情况都没有出现，那么可以标记 $k_3$ 为 $k_2 + l_{k_2}$，理由请自行证明。

然后，我们就可以二分了。

通过上面的操作，我们可以确定 $k_1 \in \lbrack 1,k_2 - 1 \rbrack$（$1 \le k_1 \le k_2 - 1$）。

对于任意位置 $x \in \lbrack 1,k_2 - 1 \rbrack$（$1 \le k_1 \le k_2 - 1$），如果：

$$k_2 < x + l_x < k_3 \small \bigvee \normalsize opt_{x} = 2 $$

温馨提示：$\bigvee$ 是逻辑或符号。

那么：

$$k_1 = x - l_x$$

原因：

因为 $k_2 < x + l_x$，可知夸克 $2$ 是距离 $x$ 最近的一个夸克，又因为 $x + l_x < k_3$，所以距离 $x$ 第二近的夸克肯定不是夸克 $3$，所以 $k_1 = x - l_x$。

关于 $opt_x = 2$ 时的证明请读者自行补证。

接下来，我们的问题就转化为了找到一个位置 $x$，使得上述式子成立。

开始正题——二分。

二分前记住我们的目的：

1. 夸克 $2$ 成为距离询问位置第一近的夸克。

2. 夸克 $1$ 成为距离询问位置第二近的夸克。

3. 夸克 $3$ 成为距离询问位置第三近的夸克。

右端点 $r \gets k_2 - 1$（将变量 $r$ 赋值为 $k_2 - 1$），左端点 $l \gets 1$。

取 $mid \gets \lceil (l + r) \div 2 \rceil$（其实向下取整和向上取整都可以，我这里只是示范）。

单次循环的步骤

询问 $mid$。

分类讨论：

1. $opt_{mid} = 2$，标记 $k_1$，退出循环，理由见上文。

2. $mid + l_{mid} = k_2$，说明夸克 $2$ 成为了第二近的夸克，我们要离夸克 $2$ 再近一点：$l \gets mid + 1$。

3. $mid + l_{mid} = k_3$，说明夸克 $3$ 成为了第二近的夸克，我们要离夸克 $3$ 再远一点：$r \gets mid - 1$。

如果上面三种情况都没有出现，那么标记 $k_1$，退出循环，理由见上文。

接下来——一个接一个地找夸克

进行定义

夸克 $a$ 是我们正在找的夸克（$3 \le a \le N$，因为我们在上一部分已经找到了 $2$ 或 $3$ 个夸克，所以 $3 \le a$）。

询问 $k_{a - 1}$。

如果 $k_{a - 1} - l_{k_{a - 1}} > k_{a - 2} \small \bigvee \normalsize opt_{k_{a - 1}} = 2$，那么标记 $k_a$ 为 $k_{a - 1} + l_{k_{a - 1}}$

原因：对于位置 $k_{a - 1}$，夸克 $a - 1$ 距此位置最近（距离为 $0$），如果夸克 $a - 2$ 不是距此位置唯一的第二近的夸克，那么夸克 $a$ 就是距此位置第二近的夸克。

倍增

设变量 $x \gets k_{a - 1} + l_{k_{a - 1}}$。

通过上面的操作，我们可以推断：在 $\lbrack k_{a - 1} + 1,x \rbrack$ 中，没有夸克（请自行补证）。

进行循环：

询问 $x$。

分类讨论

1. $opt_x = 2$，再次分类讨论：

   1. $x - l_x = k_{a - 1}$，跳出循环。

   2. $x - l_x = k_{a - 2}$，标记 $k_a$ 为 $x + l_x$，结束寻找。

      此时夸克 $a - 1$ 是距离位置 $x$ 最近的夸克，又因为 $opt_x = 2$，所以夸克 $a$ 必然是距离位置 $x$ 第二近的夸克。

2. $x - l_x = k_{a - 1}$，跳出循环。

3. $k_{a - 2} < x - l_x < k_{a - 1}$，标记 $k_a$ 为 $x + l_x$，结束寻找。

   此时夸克 $a - 1$ 是距离位置 $x$ 最近的夸克，而夸克 $a - 2$ 不是距离位置 $x$ 第二近的夸克，所以夸克 $a$ 为 $x + l_x$。

4. $x - l_x > k_{a - 1}$，跳出循环。

如果以上四种情况都没有发生，那么我们可以断定 $x - l_x = k_{a - 2} \small \bigwedge \normalsize opt_x = 1$，因为其他情况已经全部讨论过了。

温馨提示：$\small \bigwedge$ 是逻辑与符号。

因为 $x - l_x = k_{a - 2} \small \bigwedge \normalsize opt_x = 1$，所以夸克 $a - 2$ 是距离位置 $x$ 第二近的夸克，夸克 $a - 1$ 是距离位置 $x$ 最近的夸克，所以我们可以确定，在 $\lbrack k_{a - 1} + 1,x + l_x \rbrack$ 中，没有任何夸克。

然后，$x \gets x + l_x$。

继续循环。

补：我们在推导中的一个重要依据是：循环中的任意时刻，在 $\lbrack k_{a - 1} + 1,x \rbrack$ 中，没有任何夸克。

继续寻找

我们根据循环跳出后的情形，再次分类讨论：

1. $x - l_x = k_{a - 1} \small \bigwedge \normalsize opt_x = 2$

   由于题目的规定，此时有两种可能：

   1. $k_a = x + l_x$
   2. $k_{a + 1} = x + l_x,k_a \in \lbrack x + 1,x + l_x - 1 \rbrack$

   所以我们要确定在 $\lbrack x + 1,x + l_x - 1 \rbrack$ 中是否还有一个夸克。

   如何确定呢？询问 $x + 1$。

   分类讨论：

   1. $x + 1 - l_{x + 1} = k_{a - 1}$，标记 $k_a$ 为 $x + l_x$，结束寻找。

      如果在 $\lbrack x + 1,x + l_x - 1 \rbrack$ 中还有一个夸克，那此时距离位置 $x + 1$ 第二近的夸克一定是位于 $x + l_x$ 的夸克（$(x + l_x - 1) - (x + 1) < l_x - 1 < l_x + 1$）,所以 $k_a = x + l_x$。

   2. $l_x = l_{x + 1}$，标记 $k_a$ 为 $x + l_x$，标记 $k_{a + 1}$ 为 $x + 1 + l_{x + 1}$，结束寻找。

      因为有可能 $k_{a + 1} = k_a + 1$，此时 $l_x = l_{x + 1}$。

   如果两种情况都没有出现，那么说明在 $\lbrack x + 1,x + l_x - 1 \rbrack$ 中还有一个夸克。

   标记 $k_{a + 1}$ 为 $x + l_x$。

   二分的方法与“3. $x - l_x > k_{a - 1}$” 中一模一样。

2. $x - l_x = k_{a - 1} \small \bigwedge \normalsize opt_x = 1$

   因为 $x - l_x = k_{a - 1} \small \bigwedge \normalsize opt_x = 1$，所以距离位置 $x$ 第二近的夸克是夸克 $x - 1$，又因为在 $\lbrack k_{a - 1} + 1,x \rbrack$ 中，没有任何夸克。所以在 $\lbrack x + 1,x + l_x - 1 \rbrack$ 中有且只有一个夸克。

   继续二分。

   参考开始的几个夸克中的二分，我们需要找到一个位置 $y$，使得：

   $$k_{a - 2} < y - l_y < k_{a - 1} \small \bigvee \normalsize opt_{y} = 2 $$

   那么就可以标记 $k_a$ 为 $y + l_y$。

   证明就不写了，省略一大段，直接开始二分。

   右端点 $r \gets x - 1$，左端点 $l \gets k_{a - 1} + 1$。取 $mid \gets \lceil (l + r) \div 2 \rceil$。

   询问 $mid$。

   分类讨论：

   1. $opt_{mid} = 2$，标记 $k_a$，退出循环。

   2. $mid - l_{mid} = k_{a - 1}$，我们要离夸克 $a - 1$ 再近一点：$r \gets mid - 1$。

   3. $mid - l_{mid} = k_{a - 2}$，我们要离夸克 $a - 2$ 再远一点：$l \gets mid + 1$。

   如果上面三种情况都没有出现，那么标记 $k_a$，退出循环。

3. $x - l_x > k_{a - 1}$

   标记 $k_{a + 1}$ 为 $x + l_x$，因为此时夸克 $a - 1$ 至少是第三远的夸克，而在 $\lbrack k_{a - 1} + 1,x \rbrack$ 中，没有任何夸克，所以夸克 $a$ 在 $\lbrack x + 1,k_{a + 1} - 1 \rbrack$ 中。

   再次使用二分。

   参考开始的几个夸克中的二分，我们需要找到一个位置 $y$，使得：

   $$k_{a - 2} < y - l_y < k_{a - 1} \small \bigvee \normalsize opt_{y} = 2 $$

   证明就不写了，省略一大段，直接开始二分。

   右端点 $r \gets x - 1$，左端点 $l \gets k_{a - 1} + 1$。取 $mid \gets \lceil (l + r) \div 2 \rceil$。

   询问 $mid$。

   分类讨论：

   1. $opt_{mid} = 2$，分类讨论：

      1. $mid + l_{mid} \not = k_{a + 1}$ 标记 $k_a$，退出循环。

         如果 $mid + l_{mid} \not = k_{a + 1}$，此时位置 $mid + l_{mid}$ 就只能是夸克 $a$ 了。

      2. 其他情况，说明夸克 $a - 1$ 是第二近的夸克，要离夸克 $a - 1$ 再近一点：$r \gets mid - 1$。

   2. $mid - l_{mid} = k_{a - 1}$，我们要离夸克 $a - 1$ 再近一点：$r \gets mid - 1$。

   3. $mid - l_{mid} = k_{a - 2}$，我们要离夸克 $a - 2$ 再远一点：$l \gets mid + 1$。

   4. $mid + l_{mid} = k_{a + 1}$，我们要离夸克 $a + 1$ 再远一点：$r \gets mid - 1$。

   如果上面四种情况都没有出现，那么标记 $k_a$，退出循环，理由见上文。

以上就是本题的基本思路。

优化

以上的代码只能获得 60 分，我们需要再添加一些优化。

其一，使用 map 存储即可

观察代码，会发现有些位置可能会重复询问，所以可以使用 STL 中的 map（python 党用字典）来存储询问的信息。

其二

在一个一个地找夸克-继续寻找-3. $x - l_x > k_{a - 1}$ 中，我们已经知道了夸克 $a + 1$ 的位置。

询问 $k_{a + 1}$。

如果 $opt_{k_{a + 1}} = 2$，就可以直接标记 $k_a$ 和 $k_{a + 2}$ 然后结束寻找了。

否则此时我们可以知道：

$$k_{a + 1} + l_{k_{a + 1}} = k_{a + 2} \small \bigvee \normalsize k_{a + 1} - l_{k_{a + 1}} = k_{a} $$

原因有过说明。

所以此时我们可能直接得到 $k_a$。

但是如何确定距离夸克 $a + 1$ 最近的夸克是夸克 $a$ 还是夸克 $a + 2$ 呢？

用与开始的几个夸克中类似的办法。

询问 $k_{a + 1} - 1$。

分类讨论

1. $opt_{k_{a + 1} - 1} = 2$，直接标记 $k_1$。

2. $l_{k_{a + 1} - 1} = l_{k_{a + 1}} - 1$，标记 $k_a$ 为 $k_{a + 1} - l_{k_{a + 1}}$，原因略。

3. $l_{k_{a + 1}} = l_{k_{a + 1} - 1} = 1$，标记 $k_1$ 为 $k_{a + 1} - 1$，原因略。

如果上面三种情况都没有出现，那么可以标记 $k_{a + 2}$ 为 $k_{a + 1} + l_{k_{a + 1}}$，理由请自行证明。

这样，就可能再次减少询问次数。

你还可以把这个方法用到一个一个地找夸克-继续寻找-1. $x - l_x = k_{a - 1} \small \bigwedge \normalsize opt_x = 2$ 中，因为这两种情况的都能在找到夸克 $a$ 之前确定夸克 $a + 1$ 的位置。

其三，倍增倍数扩大

在一个一个地找夸克-倍增中，我们在单次循环结束后将变量 $x$ 赋值为 $x + l_x$。

我们不妨用两次倍增。

在第一次倍增开始时：

$$x \gets k_{a - 1} + l_{k_{a - 1}}\\ lx \gets x$$

在第一次倍增的循环中：

如果 $x - l_x = k_{a - 2}$，就说明在 $\lbrack k_{a - 1},x + l_x \rbrack$ 中没有任何夸克，进行以下操作：

$$lx \gets x\\ x \gets x + t \times l_x$$

否则跳出循环。

$lx$ 用来记录变量 $x$ 的历史版本。

第二次倍增开始时，$x \gets lx$。

再开始原来的倍增。

可以看出，这是在外面的倍增里面又套了一层倍增。

这样倍增中的询问次数就减少了，如果设两个夸克之间的距离为 $j$，原来倍增部分的复杂度是 $\lceil \log _2 j \rceil$，现在的复杂度就是 $\lceil \log _{t + 1} j \rceil + \lceil \log _2 (t + 1) \rceil$。经过分析，$t$ 取 $100 \sim 200$ 时次数最少，但是由于 long long 类型的储存上限是 $9 \times 10^{18}$，所以 $t$ 最多只能取到 $18$（不想证明了），再大就有可能溢出了（当然你可以判断一下会不会移除再用更大的 $t$）。

通过调整 $t$ 的大小，最多询问次数的测试点可以达到 2250 次左右。

经过以上 3 个优化，就可以 AC 了。

代码

#include <bits/stdc++.h>
using namespace std;

struct rq
{
	long long length;
	int ot;
};
map <long long,rq> dict;
long long n,t,kk[110];

long long get_mid(long long a,long long b)
{
	return ((a - b ) >> 1) + b;
}

rq q(long long address)
{
	map <long long,rq>::iterator it;
	it = dict.find(address);
	if(it != dict.end())
		return it->second;
	rq r;
	cout << "? " << address << endl;
	cout.flush();
	cin >> r.length >> r.ot;
    dict[address] = r;
	return r;
}

void put(int num)
{
	cout << "! ";
	for(int i = 0;i < num;i++)
	    cout << kk[i] << " ";
    cout.flush();
 } 

void start()
{
	rq reply,reply2,reply3;
	reply = q(0);
	kk[1] = reply.length;
	reply = q(kk[1]);
	if(reply.ot == 2)
	{
		kk[0] = kk[1] - reply.length;
		kk[2] = kk[1] + reply.length;
		return;
	}
	reply2 = q(kk[1] - 1);
	if(reply2.ot == 2)
	{
		kk[0] = kk[1] - 1 - reply2.length;
		return;
    }
    if(reply2.length == reply.length - 1)
    {
    	kk[0] = kk[1] - reply.length;
    	return;
	}
	if(reply2.length == 1 && reply.length == 1)
	{
		kk[0] = kk[1] - 1;
		return;
	 } 
    kk[2] = kk[1] + reply.length;
    long long l = 1,r = kk[1],q_mid;
	while(true)
	{
		q_mid = get_mid(l,r);
		reply3 = q(q_mid);
		if(reply3.ot == 2)
		{
			kk[0] = q_mid - reply3.length;
			return;
		}
		if(q_mid + reply3.length == kk[1])
			l = q_mid + 1;
		else if(q_mid + reply3.length == kk[2])
        	r = q_mid - 1;
		else
		{
			kk[0] = q_mid - reply3.length;
			return;
		}
	} 
} 

void f1_m1(int address,rq l_reply,long long ge)
{
	rq reply,reply2;
    long long l = kk[address - 1] + 1,r = ge - 1,q_mid;
	while(true)
	{
		q_mid = get_mid(l,r);
		reply2 = q(q_mid);
		if(reply2.ot == 2)
		{
		    kk[address] = q_mid + reply2.length;
		    return;
	    }
	    if(q_mid - reply2.length == kk[address - 2])
	    	l = q_mid + 1;
	    else if(q_mid - reply2.length == kk[address - 1])
	    	r = q_mid - 1;
		else
		{
		    kk[address] = q_mid + reply2.length;
	        return;
		}
    }

}

void f1_m2(int &address,rq l_reply,long long ge)
{
    kk[address + 1] = ge + l_reply.length;
    long long l = kk[address - 1],r = ge,q_mid;
    rq reply,reply2 = l_reply,reply3 = q(kk[address + 1]),reply4;
	if(reply3.ot == 2)
	{
		kk[address] = kk[address + 1] - reply3.length;
		kk[address + 2] = kk[address + 1] + reply3.length;
		address += 2;
		return;
    } 
    reply4 = q(kk[address + 1] - 1);
    if(reply4.length == 1)
	{
		if(reply4.ot == 1)
		    kk[address] = kk[address + 1] - 1;
        else
            kk[address] = kk[address + 1] - 2;
		return;
	}
    if(reply4.length == reply3.length - 1)
    {
    	kk[address] = kk[address + 1] - reply3.length;
    	return;
	}
    if(reply4.length == reply3.length)
    {
    	kk[address] = kk[address + 1] - 1 - reply4.length;
    	kk[address + 2] = kk[address + 1] + reply3.length;
    	address += 2;
    	return;
	}
	if(reply4.length == reply3.length + 1)
		kk[address + 2] = kk[address + 1] + reply3.length;
	while(true)
	{
		q_mid = get_mid(l,r);
		reply2 = q(q_mid);
		if(reply2.ot == 2)
		{
			if(q_mid + reply2.length != kk[address + 1])
			{
				kk[address] = q_mid + reply2.length;
			    return;
			}
			r = q_mid - 1;
   	    }
	    if(q_mid - reply2.length == kk[address - 2])
	    	l = q_mid + 1;
	    else if(q_mid - reply2.length == kk[address - 1])
	    	r = q_mid - 1;
		else
		{
			if(q_mid + reply2.length != kk[address + 1])
			{
				kk[address] = q_mid + reply2.length;
			    return;
			}
            r = q_mid - 1;
		}
    }
}

void find_1(int address,rq l_reply,long long ge)
{   
    if(ge - l_reply.length == kk[address - 1])
    	f1_m1(address,l_reply,ge);
    else
        f1_m2(address,l_reply,ge);
}

void find_2(int address,rq l_reply,long long ge)
{
	rq reply2 = l_reply,reply_a = q(ge + 1);
    if(ge + 1 - reply_a.length == kk[address - 1])
	{
		kk[address] = ge + reply2.length;
		if(reply_a.ot == 2)
		    kk[address + 1] = ge + 1 + reply_a.length;
		return;
    }
	if(reply_a.length == reply2.length)
	{
		kk[address] = ge + reply2.length;
		kk[address + 1] = ge + 1 + reply_a.length;
		return;
	}
	f1_m2(address,l_reply,ge);
}

void find(int address)
{
	if(kk[address])
	    return;
	rq reply = q(kk[address - 1]);
	if(kk[address - 1] - reply.length > kk[address - 2] || reply.ot == 2)
	{
		kk[address] = kk[address - 1] + reply.length;
		return;
	}
	long long ee = kk[address - 1] + reply.length + 1,e = ee;
	while(ee <= 1e18)
	{
		reply = q(ee);
		if(ee - reply.length == kk[address - 2])
		{
			e = ee;
			if(reply.ot == 2)
			{
				kk[address] = ee + reply.length;
				return;
			}
			ee += reply.length * 18;
		}
		else
		    break;
	}
	reply = q(e);
	while(e - reply.length == kk[address - 2])
	{
		e += reply.length;
		if(reply.ot == 2)
		{
			kk[address] = e;
			return;
	    }
		reply = q(e);
	}
	if(e - reply.length < kk[address - 1])
	{
		kk[address] = e + reply.length;
		return;
	}
    if(reply.ot == 2)
		find_2(address,reply,e);
	else
	    find_1(address,reply,e);
}

int main()
{
	cin >> n >> t;
	start();
	for(int i = 0;i < n;i++)
	    find(i);
	put(n);
	return 0;
 } 

后记

本题思路极其复杂（用本人的方法），能看到这里来，已经很不容易了，您能给我点个赞吗？

主要思路一共 3 个二分，2 个倍增，还有数不尽的分类讨论加模拟，而询问次数最多的测试点还是危险的卡在 2200 次以上，欢迎各位读者出一些毒瘤的 hack 来卡我的代码，我会积极优化代码，推出更加优秀的题解！

做此类题的关键技能

1. 使用模块化的编程思想，让程序架构更加清晰，维护与查错更加方便。
2. 仔细推敲每一个细节，反复寻找被漏掉的可能情况。
3. 巨大的耐心。

---

完结撒花！（呼！终于写完了……）

upd 2024.9.14: 修复了一些文法问题，增加了纯解法链接。

upd 2024.11.30：修复了一些文法问题，删了一些废话，删除了纯解法链接（没必要了）。

upd 2025.6.29：没有必要不公开代码，想抄就抄吧，只不过是自己心境的问题。