P10645 夸克显微镜 题解

Jason331 · 2024-08-29 19:33:13 · 题解

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

前言

解题方法 and 前置芝士

• 二分

• 倍增

• 分类讨论加模拟

请求添加标签

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

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

我与此题的关联

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

对本题的评价

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

基础解题思路

前置定义

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

• 将“第 i 个夸克”简称为“夸克 i”（1 \leq i \leq N）。对于任意自然数 2 \le a \le N，夸克 a 与夸克 a - 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，可得：

然后询问 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。

分类讨论

如果上面三种情况都没有出现，那么可以标记 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），如果：

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

那么：

原因：

因为 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。

分类讨论：

如果上面三种情况都没有出现，那么标记 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. 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$ 第二近的夸克。
3. 此时夸克 $a - 1$ 是距离位置 $x$ 最近的夸克，而夸克 $a - 2$ 不是距离位置 $x$ 第二近的夸克，所以夸克 $a$ 为 $x + l_x$。

如果以上四种情况都没有发生，那么我们可以断定 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. 如果在 $\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. 因为有可能 $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。

   分类讨论：

   如果上面三种情况都没有出现，那么标记 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. 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$。

   如果上面四种情况都没有出现，那么标记 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。

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

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

询问 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 - l_x = k_{a - 2}，就说明在 \lbrack k_{a - 1},x + l_x \rbrack 中没有任何夸克，进行以下操作：

否则跳出循环。