CF1491F Magnets 题解

题意：

这是一个交互题。

早苗有 $n$ 块磁石，编号为 $1,2,\cdots,n$。每块磁石的磁极可能是正极，负极，也可能没有磁性。她希望你能帮她找出所有没有磁性的磁石。

万幸的是，你有一台磁力检测仪。你每次可以将每个磁石放在这台机器的左托盘，右托盘或者不放。

机器将会返回此时的磁力强度。设托盘左边有 $n_1$ 个磁石为正极，$s_1$ 个磁石为负极，托盘右边中有 $n_2$ 磁石为正极，$s_2$ 个磁石为负极，则返回的磁力强度为 $ n_1n_2+s_1s_2-n_1s_2-n_2s_1 $。

如果一次测试中磁力强度的绝对值大于 $n$，这台机器就会坏掉。

你需要在 $n+\lfloor\log_2n\rfloor$ 次测试内找到所有没有磁性的磁石的编号，同时不能弄坏机器。

保证存在至少 $2$ 块磁石有磁性且至少 $1$ 块磁石没有磁性。

输入格式：

仅一行，包含一个正整数 $T$（$1\leq T\leq 100$），表示数据的组数。

对于每组数据，你需要先读入一个正整数 $n$（$3\leq n\leq 2000$），代表磁石的数量，保证每组数据的 $n$ 之和不超过 $2000$。

接下来，你可以向交互库提出若干次询问。对于每个询问，你需要输出三行：

第一行输出 ? L R，其中 $L$ 代表放在左托盘的磁石个数，$R$ 代表放在右托盘的磁石个数。

第二行输出 $L$ 个数 $a_1,a_2,\cdots,a_L$，代表放在左托盘的磁石编号。

第三行输出 $R$ 个数 $b_1,b_2,\cdots,b_R$，代表放在右托盘的磁石编号。

显然，你需要保证 $a_i\neq b_j$。

接下来，你需要刷新缓冲区。

（刷新缓冲区教程）

最后，你需要读入一个整数 $F$，代表这次测试的磁性大小。

如果你已经确定了答案，输出一行 ! k A 表示答案，其中 $k$ 代表没有磁性的磁石数量，$A$ 为一个长度为 $k$ 的序列，代表所有没有磁性的磁石编号。如果这不是最后一组数据，你应该继续处理下一组数据。如果这是最后一组数据，你应该立刻结束你的程序。

此题中，交互库是固定的。 每个磁石的状态不随着你的测试而改变。

先化简一下柿子，可得 $(n_1 - s_1) (n_2 - s_2)$

不难发现，只要天平一侧没有带磁极的，返回值一定是 $0$

但是直接求解依旧相当困难，因为返回值为 $0$ 的情况太多

考虑返回值不为 $0$ 时的情况，此时左右必定各有不少于 $1$ 个带磁极的

这意味着如果我们找到了一个带磁极的，问题求解将变得相当容易

于是我们枚举一个 $i$ ，每次询问 $A=\{i\},B=\{1,\cdots,i-1\}$ ，直到返回值不为 $0$ 。

这样的好处在于：如果返回值不为 $0$ ，则 $i$ 一定带磁极

知道 $i$ 带磁极，那 $i+1$ 到 $n$ 的就可以一个个查了

同时可知 $\{1,\dots,i-1\}$ 中必定有且仅有一个带磁极的

这个带磁极的可以通过询问 $A=\{i\}$ 和 $B = \{1,\cdots,j\}$ ，这里的 $j$ 是枚举的

仔细观察可以发现，这个 $j$ 没必要一个个询问，它是有单调性的。 \[ \texttt{总查询数} =n-1 + \left\lceil{\log_2 n}\right\rceil \le n + \left\lfloor{\log_2 n}\right\rfloor \] 时间复杂度 $O(Qn)$ ，然后我们就可以愉快地通过此题啦（

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

int Q,n,F;
vector<int> ans;
signed main()
{
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    scanf("%lld",&Q);
    while(Q--)
    {
        scanf("%lld",&n); ans.clear();
        for(int i=2; i<=n; i++)
        {
            printf("? 1 %lld\n%lld\n",i-1,i);
            for(int j=1; j<i; j++) printf("%lld%c",j," \n"[j==i-1]);
            fflush(stdout); scanf("%lld",&F);
            if(!F) continue;
            for(int j=i+1; j<=n; j++)
            {
                printf("? 1 1\n%lld\n%lld\n",i,j);
                fflush(stdout); scanf("%lld",&F); 
                if(!F) ans.push_back(j);
            }
            int l=1,r=i-1;
            while(l<r)
            {
                int mid=(l+r)>>1;
                printf("? 1 %lld\n%lld\n",mid,i);
                for(int j=1; j<=mid; j++) printf("%lld%c",j," \n"[j==mid]);
                fflush(stdout); scanf("%lld",&F);
                if(F) r=mid; else l=mid+1;
            }
            for(int j=1; j<i; j++)
                if(j!=l) ans.push_back(j);
            int len=ans.size(); printf("! %lld ",len);
            for(int j=0; j<len; j++) printf("%lld%c",ans[j]," \n"[j==len-1]);
            fflush(stdout); break;
        }
    }
    return 0;
}