CF1746E 题解

发表于 更新于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

题意

题面传送门

这是一道交互题。

目标：求出整数 x∈1∼nx\in 1\sim n。

每次询问一个集合 SS，交互库会返回是否 x∈Sx\in S。交互库会骗你，但不会连续两次骗你。

其中，n≤105n\leq 10^5，至多询问 5353 次。交互库自适应

题解

我们可以把条件转化为怎么确定一个数不是 xx：连续两次的回答不符。这里“不符”指的是，交互库返回 YES 但 xx 不在询问的集合中，或者交互库返回 NO 但 xx 在询问的集合中。

先不考虑如何询问，只考虑如何最优化交互次数。可以设计一个 dp：

我们发现所有可能的数只有两种状态：连续 00 次与回答不符和连续 11 次与回答不符。因为如果连续 22 次，那么这个数就不可能是我们要求的答案

设 fi,jf_{i,j} 表示当前有 ii 个数连续 00 次与回答不符，有 jj 个数连续 11 次与回答不符，至少要问几次，则：

fi,j=min⁡x=0imin⁡y=0jmax⁡(fi+j−x−y,x,fx+y,i−x)+1f_{i,j}=\min\limits_{x=0}^i \min\limits_{y=0}^j \max(f_{i+j-x-y,x},f_{x+y,i-x})+1

相当于：对于每次询问，从这 ii 个数中挑出 xx 个数，从 jj 个数中挑出 yy 个数，组成本次的询问集合。

  • 若交互库返回 NO，则剩下的 i+j−x−yi+j-x-y 个数数都是符合本次回答的，而挑出来的这 x+yx+y 个数都是不符的，因此这 xx 个数变成了连续一次不符，yy 个数连续两次不符被丢掉，剩下的 i+j−x−yi+j-x-y 个数就都变成了连续 00 次与回答不符，因此对应 fi+j−x−y,xf_{i+j-x-y,x}
  • 若交互库返回 YES，则这 x+yx+y 个数是符合的，剩下的 i+j−x−yi+j-x-y 个数不符合，那么 x+yx+y 个数都变成了连续 00 次与回答不符，i−xi-x 个变成连续 11 次不符，j−yj-y 个因为连续两次不符被丢掉，因此对应 fx+y,i−xf_{x+y,i-x}
  • 由于交互库是自适应的，它会挑使你交互次数尽可能大的那个答案，因此要从两种结果中取 max⁡\max。
  • 由于 xx 和 yy 是可以自己挑的，所以肯定尽可能调使答案最小的那个结果。

下面我们来考虑具体怎么询问

  • 我们把 fi,jf_{i,j} 展开，维护两个集合 A,BA,B ，AA 集合代表连续 00 次不符的数组成的集合，BB 集合代表连续 11 次不符的数组成的集合
  • 从前面 ff 数组中找到最优的 x,yx,y， 然后从 AA 中随便选出 xx 个数组成集合 A1A_1，AA 中剩下的数组成集合 A2A_2， 从 BB 中选出 yy 个数组成集合 B1B_1，BB 中剩下的数组成集合 B2B2， 然后向交互库询问 A1∪B1A_1\cup B_1
  • 根据交互库返回的结果，按照上面的 dp 的转移方式得到新的集合 A,BA,B，以此类推

考虑优化，这个 dp 的复杂度显然是 O(n4)O(n^4)，直接爆算肯定不行，那么我们可以在 i,ji,j 比较大的时候估计一个较优的 x,yx,y，小范围（例如 i+j<20i+j<20）的时候再直接 dp。至于怎么估计，当然是人类智慧，我们可以发现均分 AA 和 BB 是比较优的。

一些细节见代码：

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
84
85
86
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int dp[21][21], xm[21][21], ym[21][21];
vector<int> a, b;
int main()
{
	ios::sync_with_stdio(false);
	memset(dp, 0x3f, sizeof(dp));
	for (int l = 0; l <= 20; l++)
	{
		for (int i = 0; i <= l; i++)
		{
			int j = l - i;
			if (l <= 2)
				dp[i][j] = 0;
			for (int x = 0; x <= i; x++)
			{
				for (int y = 0; y <= j; y++)
				{
					int tmp = max(dp[i + j - x - y][x], dp[x + y][i - x]) + 1;
					if (tmp < dp[i][j])
						dp[i][j] = tmp, xm[i][j] = x, ym[i][j] = y;
				}
			}
		}
	}
	cin >> n;
	for (int i = 1; i <= n; i++)
		a.push_back(i);
	while (a.size() + b.size() > 2)
	{
		int x, y;
		if (a.size() + b.size() <= 20)
			x = xm[a.size()][b.size()], y = ym[a.size()][b.size()];
		else
			x = a.size() / 2, y = b.size() / 2;
		vector<int> a1(a.begin(), a.begin() + x), a2(a.begin() + x, a.end());
		vector<int> b1(b.begin(), b.begin() + y), b2(b.begin() + y, b.end());
		a.clear(), b.clear();
		cout << "? " << a1.size() + b1.size() << " ";
		for (int i : a1)
			cout << i << " ";
		for (int i : b1)
			cout << i << " ";
		cout << endl;
		string in;
		cin >> in;
		if (in == "YES")
		{
			for (int i : a1)
				a.push_back(i);
			for (int i : b1)
				a.push_back(i);
			for (int i : a2)
				b.push_back(i);
		}
		else
		{
			for (int i : a2)
				a.push_back(i);
			for (int i : b2)
				a.push_back(i);
			for (int i : a1)
				b.push_back(i);
		}
	}
	for (int i : a)
	{
		cout << "! " << i << endl;
		string in;
		cin >> in;
		if (in == ":)")
			return 0;
	}
	for (int i : b)
	{
		cout << "! " << i << endl;
		string in;
		cin >> in;
		if (in == ":)")
			return 0;
	}
	return 0;
}