CF1746E2 Joking (Hard Version) 题解
win114514
·
·
题解
非常厉害的一道交互题。
思路
由于交互库会说谎，我们考虑把两次询问划分成一组。
结论：假如一个集合在两次询问中都为不成立，那么这个集合也就一定不成立。
证明显然，因为这两次中总有一次时真话。
那么我们就可以想到一个比较暴力的想法。
每一次把集合划分为四个，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$ 分为 $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$，也就是可以直接进行询问。
那么转移就可以类似操作一样的枚举。
$$dp_{i,j}=1+\min_{l\le i,r\le j}(\max(dp_{l+r,i-l},dp_{i+j-l-r,l}))$$
记一下每个点从那里转移来的即可。
这样在集合大小较小时也能快速的排除。
### Code
```cpp
#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;
}
```