P8849 题解

· · 题解

一道好题。

观察数据，要求询问次数不超过 \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;
}