前言
astray.
题目
题目大意：
这是一道交互题。
\(t\) 组数据，每组数据有 \(n\) 个磁铁，每个磁铁可能是 \(N\) 极、\(S\) 极和被消磁的磁铁。你需要通过不超过 \(n+\lfloor\log_2n\rfloor\) 次询问找到所有被消磁的磁铁。
用于询问的是一个破破烂烂的机器，你可以在其两端放磁铁，它会告诉它们之间力。设托盘左边有 \(n_1\) 个磁铁是 \(N\) 极，\(s_1\) 个是 \(S\) 极，右边有 \(n_2\) 个是 \(N\) 极，\(s_2\) 个是 \(S\) 极。那么他们产生的力为：\(n_1n_2+s_1s_2-n_1s_2-n_2s_1\)。可以注意到这并不一定是非负数。
这个机器如果测的力的大小超过 \(n\) 就会碎成渣渣。
数据保证至少有两块磁铁有磁性，一块磁铁没有磁性。
\(1\le t\le 100;3\le n\le 2000;\sum n\le 2000.\)
讲解
迷
通过询问次数 \(n+\lfloor\log_2n\rfloor\) 的限制很容易陷入先二分找一个带磁性的磁铁，再依次判断每个磁铁是否带磁性的误区。
破
如果跳出了上面的迷，那么问题应该就变得好想了。首先我们找出一块带磁性的磁铁是肯定的，但是询问次数不受 \(\lfloor\log_2n\rfloor\) 的限制。
考虑一个一个找！
具体操作为：枚举 \(i\in[2,n]\)，询问 \([1,i-1]\) 与 \({i}\) 之间的力。如果有力，那么第 \(i\) 块磁铁一定是有磁性的，对于 \([i+1,n]\) 块磁铁逐一询问即可。
那么对于 \([1,i-1]\) 的磁铁呢？显然有且仅有一块磁铁是有磁性的，二分把它找出来即可。
询问次数为：\(n-1+\lceil\log_2n\rceil\)，刚好符合要求。
代码
int Q(int l1,int r1,int l2,int r2)
{
putchar('?'); putchar(' '); Put(r1-l1+1,' '),Put(r2-l2+1,'\n');
for(int i = l1;i <= r1;++ i) Put(i,' '); putchar('\n');
for(int i = l2;i <= r2;++ i) Put(i,' '); putchar('\n');
fflush(stdout);
return Read();
}
bool de[MAXN];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
for(int T = Read(); T ;-- T)
{
cnt = n = Read();
for(int i = 1;i <= n;++ i) de[i] = 1;
int ID = 0;
for(int i = 2;i <= n && !ID;++ i)
if(Q(1,i-1,i,i))
ID = i;
for(int i = ID+1;i <= n;++ i)
if(Q(ID,ID,i,i)) de[i] = 0,cnt--;
cnt--;
de[ID] = 0;
int ret = 0,l = 1,r = ID-1;
while(l <= r)
{
if(l == r)
{
ret = l;
break;
}
int mid = (l+r) >> 1;
if(Q(l,mid,ID,ID))
{
if(l == mid) {ret = l;break;}
r = mid;
}
else l = mid+1;
}
de[ret] = 0; cnt -= (ret > 0);
putchar('!'); putchar(' '); Put(cnt,' ');
for(int i = 1;i <= n;++ i) if(de[i]) Put(i,' ');
putchar('\n');
fflush(stdout);
}
return 0;
}