非常厉害的一道交互题。
思路
由于交互库会说谎，我们考虑把两次询问划分成一组。
结论：假如一个集合在两次询问中都为不成立，那么这个集合也就一定不成立。
证明显然，因为这两次中总有一次时真话。
那么我们就可以想到一个比较暴力的想法。
每一次把集合划分为四个，\(S_{0,0},S_{0,1},S_{1,0},S_{1,1}\)。
| 第一次询问 | 第二次询问 | 排除的集合 |
|---|---|---|
| \(\text{Yes}\) | \(\text{Yes}\) | \(S_{0,0}\) |
| \(\text{Yes}\) | \(\text{No}\) | \(S_{0,1}\) |
| \(\text{No}\) | \(\text{Yes}\) | \(S_{1,0}\) |
| \(\text{No}\) | \(\text{No}\) | \(S_{1,1}\) |
这样就可以做到 \(\log_{\frac{3}{4}}n\) 的次数将集合缩小到三。
缩小到三后分类讨论一下就可以过简单版本了。
但这个时候我们可以意识到其实不需要分组。
可以直接不断考虑相邻的两次询问。
继续从结论出发。
假如上一次询问的是 \(S\)，且 \(S\) 被回答为 \(\text{Yes}\)（假如本来是 \(No\) 的话就直接取补集即可），\(S\) 的补集为 \(T\)。
如果我们这一次询问一个集合 \(U\)，它的补集为 \(P\)。
假如答案为 \(\text{Yes}\)，那么排除的集合为 \(T\cap P\)。
假如答案为 \(\text{No}\)，那么排除的集合为 \(T\cap U\)。
我们的目的就是让排除的集合尽量多。
总结一下过程。
维护两个东西，\(S\) 与 \(T\)。
\(S\) 是上次询问得到的合法的集合，\(T\) 则是 \(S\) 的补集。
贪心的，每一询问将 \(S\) 分为 \(S_0,S_1\)，\(T\) 分为 \(T_0,T_1\)。
然后询问 \(S_0\cup T_0\)。
假如答案为 \(\text{Yes}\)，那么更改集合为 \(S\gets S_0\cup T_0,T\gets S_1\)。
假如答案为 \(\text{No}\)，那么更改集合为 \(S\gets S_1\cup T_1,T\gets S_0\)。
在集合大小较大时，我们可以直接均分两个集合，就比较优秀。
但在测试样例的时候可能会发现程序会一直询问。
这是因为在集合大小较小时，直接均分就不是特别优秀。
甚至有可能会产生无法排除的情况。
那么考虑在集合大小较小时进行特殊处理。
我们设 \(dp_{i,j}\) 表示 \(S\) 大小为 \(i\)，\(T\) 大小为 \(j\) 时最多还需要分几次。
初始状态为 \(i+j\le 2,dp_{i,j}=0\)，也就是可以直接进行询问。
那么转移就可以类似操作一样的枚举。
记一下每个点从那里转移来的即可。
这样在集合大小较小时也能快速的排除。
Code
#include <bits/stdc++.h>
using namespace std;
#define eb(...) emplace_back(__VA_ARGS__)
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
auto ask = [&](vector<int> a) {
cout << "? " << a.size() << " ";
for(auto i : a) cout << i << " ";
cout << endl;
string b; cin >> b;
return (b == "YES" ? 1 : 0);
};
auto getEnd = [&](int x) {
cout << "! " << x << endl;
string b; cin >> b;
if(b == ":)") exit(0);
return;
};
auto Mer = [&](vector<int> a, vector<int> b) {
for(auto i : b) a.eb(i); return a;
};
vector<int> s, t;
array<array<int, 100>, 100> dp;
array<array<pair<int, int>, 100>, 100> pre;
for(int i = 1;i <= n;i++)
s.eb(i);
for(int i = 0;i < 100;i++)
for(int j = 0;j < 100;j++)
dp[i][j] = 1e9;
for(int k = 0;k < 100;k++) {
for(int i = 0;i < 100;i++)
for(int j = 0;j < 100;j++) {
if(i + j != k) continue;
if(i + j <= 2) dp[i][j] = 0;
for(int l = 0;l <= i;l++) {
for(int r = 0;r <= j;r++) {
if(dp[i][j] > 1 + max(dp[l + r][i - l], dp[i + j - l - r][l])) {
dp[i][j] = 1 + max(dp[l + r][i - l], dp[i + j - l - r][l]);
pre[i][j] = {l, r};
}
}
}
}
}
while(s.size() + t.size() >= 3) {
int len1 = s.size(), len2 = t.size();
int pre1 = len1 / 2, pre2 = len2 / 2;
if(len1 + len2 < 100)
pre1 = pre[len1][len2].first,
pre2 = pre[len1][len2].second;
vector<int> s0(s.begin(), s.begin() + pre1);
vector<int> s1(s.begin() + pre1, s.end());
vector<int> t0(t.begin(), t.begin() + pre2);
vector<int> t1(t.begin() + pre2, t.end());
int flag = ask(Mer(s0, t0));
if(flag == 1) s = Mer(s0, t0), t = s1;
if(flag == 0) s = Mer(s1, t1), t = s0;
}
for(auto i : s) getEnd(i);
for(auto i : t) getEnd(i);
return 0;
}