源自 IMO2012 D1T3。
题面
出了一道交互题，题目文件如下。
Game.zip
题解
我们考虑我们询问的一个集合 $S$。
如果回答为 No 那么其指向 $x \not = S$。
如果回答为 Yes 那么其指向 $x \not = \overline S$。
考虑不断排除。
首先我们发现所有数都是对称的，因此我们可以将它们重新标号。
我们不妨重新标号成 $0,1,\dots,2^K,\dots,m-1$。
我们这样做：
先询问 $K+1$ 次 $2^K$，如果全部都回答 No 那么 $x != 2^K$。
否则，我们在第一次回答 Yes 时停止继续询问。
然后对于每一个 $0 \leq i \leq K-1$，我们询问集合 $S$ 包含所有二进制第 $i$ 位为 $1$ 的 $\leq 2^K - 1$ 的元素。
每个问题的答案指向第 $i$ 位为 $0$ 或 $1$ 的元素 $\not = x$。
它们的并集恰好是一个数，同时还有上面的一次 Yes 的回答，总共 $K+1$ 次，必定包含一句真话。
所以这个数一定不是 $x$，排除掉，重新标号，继续做。
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
| #include<bits/stdc++.h>
using namespace std;
int test;
int n,m,K;
vector<int> V;
string s;
int cnt,tmp;
signed main(){
cin>>test;
cin>>n>>m>>K;
m=1<<K;
for(int i=1;i<=n;i++) V.push_back(i);
while((int)V.size()>m){
for(int i=1;i<=K+1;i++){
cout<<1<<" "<<V[m]<<endl;
cin>>s;
if(s=="Yes") break;
}
if(s=="No") V.erase(V.begin()+m);
else{
tmp=0;
for(int i=0;i<K;i++){
cout<<(m>>1)<<" ";
for(int j=0;j<m;j++)
if(j&(1<<i)) cout<<V[j]<<" ";
cout<<endl;
cin>>s;
if(s=="No") tmp|=1<<i;
}
V.erase(V.begin()+tmp);
}
}
cout<<0<<endl;
cout<<m<<" ";
for(int i:V) cout<<i<<" ";
cout<<endl;
return 0;
}
|