CFdiv2-Tournament Countdown-(思维+交互题套路)

D

题意：
就是说，给你2ⁿ 个人，然后两个人比赛，胜的晋级输的推掉。就是1vs2,3vs4,…。然后你每次可以询问a和b，他俩谁赢的多，如果返回1a多，2b多，0一样多。然后你最多查询1/3*2ⁿ⁺¹ 次。问你最终的胜者是谁。

思考：
1.当时看了看样例的图，如果最暴力的比较方法，要比较n-1次(比如n是总人数)。但是题目最多让你查询(2n+2)/3次。刚开始没啥感觉，刚开始我想先把一半用暴力求出来，这样是n/2次查询，但是另一半怎么凑呢，如果n/4也不行，所以就不行了。
2.然后想到交互题的查询次数都是很有意义的，为什么是这个。既然我用暴力可以n-1次求出来，最多查询(2n+2)/3次，那不就是暴力次数的2/3？也就是3场比赛你要用两次查咨求出来就可以了。只要想到这，题目就好处理了，既然是3场比赛，那么就是4个人，所以4个4个的看。
3.比如1 2 3 4
如果1=3，那么1和3都是输掉的，因为如果他俩都是胜者，那么晋级后肯定要有一个比较大。所以再比较晋级的2和4就可以了。
如果1>3，那么1肯定晋级，再查询1和4，比较一下就可以了。
如果1<3，那么3肯定晋级，再查询3和2，比较一下就可以了。
4.注意细节，数组循环什么时候停止，要用最直观的写法。这样最不容易错。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int va[N];
vector<int > v,vt;

int query(int a,int b)
{
	cout<<"? "<<a<<" "<<b<<"\n";cout.flush();
	int x;cin>>x;
	return x;
}

void solve()
{
	int anw = 0;
	while(1)
	{
		if(v.size()%4==0)
		{
			vt.clear();
			for(int i=0;i+3<=(int)v.size()-1;i+=4)
			{
				int a = v[i],b = v[i+1],c = v[i+2],d = v[i+3];
				int t1 = query(a,c);
				if(t1==0)
				{
					int t2 = query(b,d);
					if(t2==1) vt.pb(b);
					else vt.pb(d);
				}
				if(t1==1)
				{
					int t2 = query(a,d);
					if(t2==1) vt.pb(a);
					else vt.pb(d);
				}
				if(t1==2)
				{
					int t2 = query(c,b);
					if(t2==1) vt.pb(c);
					else vt.pb(b);
				}
			}
			v = vt;
		}
		else
		{
			int a = v[0],b = v[1];
			int t1 = query(a,b);
			if(t1==1) anw = a;
			else anw = b;
			break;
		}
	}
	cout<<"! "<<anw<<"\n";cout.flush();
}

signed main()
{
	cin>>T;
	while(T--)
	{
		cin>>n;
		v.clear();
		n = (1ll<<n);
		for(int i=1;i<=n;i++) v.pb(i);
		solve();
	}
	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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

总结：
多多思考，总结。