第一次在场上做出月赛交互题。
题意简述
在一个长为 $n$ 的数列中，有两个特殊数字，你需要找到这两个数的下标，每次你可以向交互库询问一个集合，如果这个集合中恰好有 $1$ 个特殊数字，交互库返回 $1$，否则交互库返回 $0$。$n\le 1000$，最多向交互库询问 $19$ 次。
思路
首先，在值域上是做是不方便的，假如每次询问一个前缀区间，那么必然答案在中间一段才会是 $1$，普通的二分和倍增无法很好处理，而三分法又必须满足严格单调。
考虑到 $19\approx 2\log n$，尝试每一位考虑。二进制分组，对于每一位来说，仅询问该位上是 $0$ 的数字，那么如果交互库返回 $0$，则说明两个数在该位上相同，否则说明两个数在该位上不同。两个数的二进制表示至少有一位是不同的，记不同的位中最高的那位是第 $c$ 位。
记两个数较小的下标为 $x$，较大的下标为 $y$，则 $x$ 的第 $c$ 位必然为 $0$，$y$ 的第 $c$ 位必然为 $1$。现在我们要确定其它位上的值。我们知道两个数在每位上是否相同，所以只需知道一个数即可知道另一个数，此处以 $x$ 为例。对于不是 $c$ 的每个二进制位，仅询问第 $c$ 为上是 $0$ 且这一位上也是 $0$ 的数。$y$ 必然不在这个集合内，所以当返回 $1$ 时，$x$ 这一位是 $0$，否则这一位是 $1$。
记 $k$ 为 $n$ 的二进制数位个数，则需询问 $2k-1$ 次，当 $n=1000$ 时，$k=10$，恰好 $19$ 次。
Code
注意不能询问大小为 $n$ 和大小为 $0$ 的集合，需要特判，此时答案为 $0$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
namespace lly
{
constexpr int N=1005;
int s[N],t=0;
int choose[N],n;
inline int ask()
{
if(t==0||t==n) return 0;
cout<<"? "<<t<<" ";
for(int i=1;i<=t;i++) cout<<s[i]<<" ";
cout<<"\n";
cout.flush();
int x;cin>>x;
return x;
}
inline void put(int x,int y)
{
cout<<"! "<<x<<" "<<y<<"\n";
cout.flush();
}
inline void solve()
{
cin>>n;
int d=__lg(n);
memset(choose,0,sizeof(choose));
for(int i=0;i<=d;i++)
{
t=0;
for(int j=1;j<=n;j++)if(j&(1<<i))s[++t]=j;
choose[i]=ask();
}
int c;
for(int i=d;i>=0;i--)if(choose[i]){c=i;break;}
int x=0,y=0;
y|=(1<<c);
for(int i=d;i>=0;i--)
{
if(i==c)continue;
t=0;
for(int j=1;j<=n;j++) if((j&(1<<i))==0&&(j&(1<<c))==0)s[++t]=j;
int z=ask();
if(choose[i]){if(z)y|=1<<i;else x|=1<<i;}
else{if(!z)x|=1<<i,y|=1<<i;}
}
put(x,y);
}
inline void work()
{
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T;cin>>T;
while(T--) solve();
}
}
int main()
{
lly::work();
return 0;
}
|