观察数据，要求询问次数不超过 $\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;
}
标签：金苹果,log,二进制位,询问,JROI,P8026,mid,hibernal,rceil From： https://www.cnblogs.com/Xy-top/p/17500676.html