D. Tournament Countdown（交互题）

题意
有 $2^n$ 进行两两决斗，胜者进入下一轮。
每次可以询问系统两个人胜利的场次。
在不超过 $\lceil \frac{1}{3}\cdot 2^{n+1}\rceil$ 次询问的条件下，求出最终的胜者。

$1\le n\le 17$

思路
设一共有 n 人。
如果朴素询问的话，从最底层每次询问两个，分别询问每一局的胜者是谁，一共 n-1 局，得到最终胜者的询问次数为 n-1。
但是注意要求不超过 $\lceil \frac{2}{3}\ast n\rceil$ 次询问，也就是说，每 3 局最多询问 2 次就要确定一个胜者。

三局一共 4 人，分别记为 a, b, c, d。例如图中的 1, 2, 3, 4。

首先询问 a 和 c 的胜利次数：

• 如果 a 的胜利次数 大于 c 的胜利次数，那么说明 c 输给了 d，那么再让 a 和 d 比较，赢者便是这 4 人中的最终胜者。
• 如果 a 的胜利次数 小于 c 的胜利次数，那么说明 a 输给了 b，那么再让 b 和 c 比较，赢者便是这 4 人中的最终胜者。
• 如果 a 的胜利次数 和 c 的胜利次数相同，那么说明 a 赢了 b，c 赢了 d，或者 a 输给了 b，c 输给了 d。但是如果两个都赢的话，这两个也会决斗，只有一人胜利，胜利次数不可能相同。所以只有后面那种情况，a 输给了 b，c 输给了 d。那么再让 b 和 d 比较，赢者便是最终胜者。

这样将初始的 n 人四个四个求出初胜者，得到 n/4 个胜者，再不断进行下去，最终剩下 2 个或者 1 个。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0) 

const int N = 200010, mod = 1e9+7;
int T, n, m;

int ask(int x, int y)
{
	cout << "? " << x << " " << y << endl;
	cout.flush();
	int ans; cin >> ans;
	return ans;
}

signed main(){ //注意交互题不要加 ios
	cin >> T;
	while(T--)
	{
		cin >> n;
		n = 1 << n;
		queue<int> que;
		for(int i=1;i<=n;i++) que.push(i);
		
		while(que.size() >= 4)
		{
			int a = que.front(); que.pop(); //队头取出四个
			int b = que.front(); que.pop();
			int c = que.front(); que.pop();
			int d = que.front(); que.pop();
			
			int x;
			
			int ac = ask(a, c);
			if(ac == 1){
				int ans = ask(a, d);
				if(ans == 1) x = a;
				else x = d;
			}
			else if(ac == 2){
				int ans = ask(b, c);
				if(ans == 1) x = b;
				else x = c;
			}
			else{
				int ans = ask(b, d);
				if(ans == 1) x = b;
				else x = d;
			}
			que.push(x); //结果放到队尾
		}
		if(que.size() == 2){
			int a = que.front(); que.pop();
			int b = que.front(); que.pop();
			int ans = ask(a, b);
			if(ans == 1) que.push(a);
			else que.push(b);
		}
		cout << "! " << que.front() << endl;
	}
	
	return 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
63
64

---

经验
注意题目给的询问次数限制有提示作用，不是平白无故给你的，如果把这个看懂的话，题目也就差不多了。