\(Problem\)
你有 \(n\) 个磁铁，每个磁铁有属性，为下列三种之一
-
N、S、-（表示无磁性）
一次操作你可以选择不相交的两个磁铁的子集 \(S\) 和 \(T\)，假设 \(S\) 中有 \(n_1\) 个 N，\(s_1\) 个 S， \(T\) 中有 \(n_2\) 个 N，\(s_2\) 个 S。这些你都不知道。通过交互库你可以得到 \(n_1n_2-n_1s_2-n_2s_1+s_1s_2\)（化简得到：\((n_1-s_1)(n_2-s_2)\) ）。得到的数值可能 \(<0\)。
你可以花费不超过 \(n+\lfloor\log_2n\rfloor\) 次操作找出所有没有磁性的磁铁。
多组数据 \(T\leq 100\)，每次 \(n\leq 2000\)，\(\sum n\leq 2000\)。保证至少两个有磁极的磁铁和一个无磁极的磁铁。
\(Sol\)
如果我们能找到一个有磁极的磁铁，那么问题将非常简单。
然而要想找出一个有磁极的磁铁，必须借助另外至少一个有磁极的磁铁。
假象一种极端的边界：如果只有两块磁铁有磁极怎么办？只能硬着头皮一个一个找呗。
于是得到一种方案：每次查询 \(S=\{i\}\)，\(T=\{1,\cdots,i-1\}\)。当遇到第二块有磁极的磁铁之前，答案一定为 \(0\)（因式有一项必为 \(0\)）。当 \(i\) 是第二块有磁极的磁铁时，答案会变成 \(\pm 1\)，以此我们就能找出一块有磁极的磁铁了！
利用这块磁铁找出 \(>i\) 位置的无磁性的磁铁，这样总查询次数为 \(n-1\)。
但是第一块有磁性的磁铁我们还没有找到，如果找到了剩下的都是无磁性的磁铁。这时不必要一次一次找，观察题目使用技巧知道要二分找出来。于是继续构造 \(S=\{i\}\)，\(T=\{1,\cdots,j\}\) 来判断前缀 \(j\) 的磁铁中有没有有磁性的磁铁，然后二分，这部分查询次数为 \(\lceil\log_2n\rceil\)。
综上，总次数 \(=n-1+\lceil\log_2n\rceil\leq n+\lfloor\log_2n\rfloor\)。时间复杂度为 \(\mathcal O(Tn^2)\)。
\(Code\)
#include <bits/stdc++.h>
using std::vector;
const int N = 2005;
int T, n, F;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
printf("? 1 %d\n%d\n", i - 1, i);
for (int j = 1; j < i; j++) printf("%d ", j);
puts(""); fflush(stdout);
scanf("%d", &F);
if (F) {
vector<int> ans;
for (int j = i + 1; j <= n; j++) {
printf("? 1 1\n%d\n%d\n", i, j);
fflush(stdout);
scanf("%d", &F);
if (!F) ans.push_back(j);
}
int l = 1, r = i - 1;
while (l <= r) {
int mid = l + r >> 1;
printf("? 1 %d\n%d\n", mid, i);
for (int j = 1; j <= mid; j++) printf("%d ", j);
puts(""); fflush(stdout);
scanf("%d", &F);
if (F) r = mid - 1; else l = mid + 1;
}
for (int j = 1; j < i; j++)
if (j != r + 1) ans.push_back(j);
printf("! %d ", ans.size());
for (int j = 0; j < ans.size(); j++) printf("%d ", ans[j]);
puts(""); fflush(stdout); break;
}
}
}
return 0;
}