自动搬运

查看原文

来自洛谷，原作者为

	Xy_top constructive thinking

搬运于2025-08-24 22:43:05，当前版本为作者最后更新于2023-06-21 20:57:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道好题。

观察数据，要求询问次数不超过 $\lceil2\log n\rceil-1$，相当困难。

我刚开始也在想二分，但这个东西并不具有单调性，但这个题具有的特点就是你不仅仅可以询问一个前缀，你还可以询问任意的集合。

首先发现如果能将 $n$ 个苹果分成 $S_1$ $S_2$ 两个长度接近的集合，且 $S_1$ 和 $S_2$ 中各出现了一个金苹果，就可以直接二分然后在 $\lceil2\log n\rceil-2$ 次询问内解决问题了（因为已经分成 $S_1$ $S_2$ 两个长度接近的集合了）。

怎么解决呢？我们假设去分 $S_1$，每次把它分成数量接近的两份 $S_3$ $S_4$，取其中一份。无论取 $S_3$ 还是 $S_4$，剩下的苹果中肯定有一个是金苹果了吧，因为 $S_2$ 中一定有一个金苹果。

随便取一个 $S_3$ 或者 $S_4$，如果得到的答案是 $1$，那么肯定在当前选择的区间中，继续递归，否则就在另一个区间中。

但是我们暂时没有想到合适的方法能够用 $1$ 次询问找到 $S_1$，$S_2$（貌似只有猜可以。

所以我想到了在求 $S_1$，$S_2$ 的过程中找到两个金苹果位置之间的关联。

这里需要用到二进制分组的技巧啦！

从高到低地考虑每一个二进制位，将所有的位置按照这一位二进制位分为两个部分：一是这一位是 $0$，二是这一位是 $1$。

我们来看看能够得到些什么，如果返回 $1$，就说明两个区间内各有一个金苹果，我们就成功了，并且还能够得到两个金苹果当前的二进制位不同。

如果是 $0$ 呢？只能够得到两个金苹果当前的二进制位是相同的。

这样一定能得到一组询问答案是 $1$ 吗？显然可以。如果全是 $0$，那么意味着两个金苹果每一个二进制位都相同，也就是同一个金苹果了，所以肯定有一个二进制位不同啦！

这样就花去了 $\lceil\log n\rceil$ 次询问，得到两个集合，接着再进行 $\lceil\log n\rceil -1$ 次二分，刚刚好能够求出一个金苹果的位置。

那另一个呢？我们不是求出金苹果两个每一个二进制位是否相同了吗？所以也解决了。其实熟练的人看一下就知道了那个是异或值，所以假如知道了 $a\oplus b=c$，那么 $b=a\oplus c$，就这样结束了。

超短代码：

#include <iostream>
#define For(i, a, b, j) for (int i = (a); i <= (b); i = (j) )
using namespace std;
int T, n, k, kx;
int x, oplus;
int a[505], b[505];
int find (int l, int r) {
    if (l == r) return b[l];
    int mid = l + r >> 1;
    printf ("? %d ", mid - l + 1);
    For (i, l, mid, i + 1) printf ("%d ", b[i]);
    printf ("\n");
    fflush (stdout);
    scanf ("%d", &x);
    if (x == 1) return find (l, mid);
    return find (mid + 1, r);
}
int main () {
    fflush (stdout);
    scanf ("%d", &T);
    while (T --) {
        oplus = 0;
        fflush (stdout);
        scanf ("%d", &n);
        For (m, 1, n, m << 1) {
            k = 0;
            For (i, 1, n, i + 1) if ( (i & m) == 0) a[++ k] = i;
            printf ("? %d ", k);
            For (i, 1, k, i + 1) printf ("%d ", a[i]);
            printf ("\n");
            fflush (stdout);
            scanf ("%d", &x);
            oplus += x * m;
            if (x == 1) {
                For (i, 1, k, i + 1) b[i] = a[i];
                kx = k;
            }
        }
        int ans = find (1, kx);
        printf ("! %d %d\n", min (ans, ans ^ oplus), max (ans, ans ^ oplus) );
        fflush (stdout);
    }
    return 0;
}