CF835E 题解

· · 题解

题目大意

交互题，有一个长度为 n 的序列，其中有恰好两个 y，剩下 n-2 个为 x．其中 n,x,y 给定．每次可以询问一个集合的异或和，你需要用不超过 19 次询问找到两个 y 的下标．1 \le n \le 10^3，1 \le x,y \le 10^9．

简要做法

首先考虑如何利用题目给你的询问操作．我们可以发现在 x,y 均为常量的情况下，询问得到的回答只和询问集合大小的奇偶性和包含 y 个数的奇偶性有关，具体关系如下：

\def\arraystretch{1.5} \begin{array}{|c|c|c|} \hline \textsf{集合大小奇偶性} & \textsf{包含 $y$ 个数奇偶性} & \textsf{答案} \\ \hline \textsf{奇} & \textsf{奇} & y \\ \hline \textsf{奇} & \textsf{偶} & x \\ \hline \textsf{偶} & \textsf{奇} & x \oplus y \\ \hline \textsf{偶} & \textsf{偶} & 0 \\ \hline \end{array}

则询问操作转化为：每次询问所选集合 y 的个数的奇偶性．

考虑一个很简单的做法，对序列中元素进行二进制拆位分组，共分 \lceil \log_2 n \rceil 组，每组的一对集合按照二进制第 i 位分类．则可以证明，至少存在一组使得两个 y 恰好在一对集合中分开．然后分别对两个集合进行二分查找．即可找到两个 y 的下标．显然这种方式需要花费的次数为最多 \lceil \log_2 n \rceil + \lceil \log_2 \lfloor \frac n 2 \rfloor \rceil + \lceil \log_2 \lceil \frac n 2 \rceil \rceil 次．无法通过本题．

更进一步地，我们来分析二进制拆位的本质．当我们询问以第 i 位为依据拆出来的一对集合中的一个时，若得到的回答是包含奇数个 y，则表示两个 y 的下标的二进制表示中第 i 位取不同的值，否则代表这一位取相同的值．换句话说，我们可以在得到任意一个将两个 y 分开的集合对的同时得到两个 y 的下标的异或值．由于异或的逆运算还是异或，由此可以得出一个做法：当得到第一个 y 的下时，无需再对第二个 y 所在的集合进行二分查找，可以直接利用异或值与第一个 y 的下标计算．这种方式需要花费的次数为最多 \lceil \log_2 n \rceil + \lceil \log_2 \lfloor \frac n 2 \rfloor \rceil 次．可以通过本题．

代码参考

见 原始 OJ 提交．

CHANGELOG