本文最后更新于：2023年4月26日 晚上
题目大意
有 \(2^{n}\)
个人进行一轮淘汰赛，每次可以询问其中任意两人谁赢的场数多，最后输出淘汰赛的冠军。
分析
一道优质交互题。
首先看最多的交互次数，是 $\lceil 1/3 \times 2^{n+1} \rceil $ ，即
$\lceil 2/3 \times 2^{n} \rceil $ ，考虑到总的比赛场数是 \(2^{n}-1\) ，可以尝试用 \(2\) 次询问获得 \(3\) 场比赛的结果。
那么如何用 \(2\) 次询问获得 \(3\) 场比赛的结果呢？
我们来分析一下，\(4\)
个人之间（假设这四个人分别是 \(p_{1}\)
， \(p_{2}\) ， \(p_{3}\) ， \(p_{4}\) ），会进行 \(3\) 场比赛，先是 \(p_{1}\) 和 \(p_{2}\) 比赛 ， 然后 \(p_{3}\) 和 \(p_{4}\)
比赛。我们如果对第一轮直接交战的人进行比较，那么就错了。
我们考虑先对 \(p_{1}\) 和 \(p_{3}\) 进行比较，如果 \(p_{1}\) 和 \(p_{3}\)
胜利场数一样，那么他们不可能同时进入下一轮，因为如果同时进入下一轮，他们当中就一定会有一个人胜利，胜利场数就不可能一样，所以直接比较
\(p_{2}\) 和 \(p_{4}\) 就可以知道这 \(4\) 个人中胜者是谁。
接下来分析 \(p_{1}\) 比 \(p_{3}\)
胜利场数多的情况。在这种情况下，\(p_{3}\) 不可能是 \(4\) 个人中的胜者，同时 \(p_{1}\) 一定通过了第 \(1\) 轮，即 \(p_{2}\) 不是 \(4\) 个人中的胜者了。所以只需要比较 \(p_{1}\) 和 \(p_{4}\) 即可。
同理，\(p_{1}\) 比 \(p_{3}\) 胜利场数少时，只需要比较 \(p_{2}\) 和 \(p_{3}\) 即可。
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
| #define sx fflush(stdout)
int win[(1<<17)|5]={};
void wk() {
int n,result;
read(n);
int m=1<<n;
for(int i=1;i<=m;++i) win[i]=i;
for(int l=1;l<=n;l+=2,m/=4) {
if(l==n) {
printf("? %d %d\n",win[1],win[2]);
sx;
read(result);
if(result==1) {
printf("! %d\n",win[1]);
}
else printf("! %d\n",win[2]);
sx;
return ;
}
for(int i=1;i*4<=m;++i) {
printf("? %d %d\n",win[i*4-3],win[i*4-1]);
sx;
read(result);
if(!result) {
printf("? %d %d\n",win[i*4-2],win[i*4]);
sx;
read(result);
if(result==1) win[i]=win[i*4-2];
else win[i]=win[i*4];
}
else if(result==2) {
printf("? %d %d\n",win[i*4-2],win[i*4-1]);
sx;
read(result);
if(result==1) win[i]=win[i*4-2];
else win[i]=win[i*4-1];
}
else {
printf("? %d %d\n",win[i*4-3],win[i*4]);
sx;
read(result);
if(result==1) win[i]=win[i*4-3];
else win[i]=win[i*4];
}
}
}
printf("! %d\n",win[1]);
sx;
}
|