题目
https://qoj.ac/contest/1849/problem/9783/statement/zh_cn
思路
记 d(u,v) 代表 u,v 节点之间的距离，不难注意到： query(\mathbf A) + query (\mathbf B) \ne query (\mathbf A \cup \mathbf B) 等价于 \exist a \in \mathbf A,b \in \mathbf B: d(a,b) \le 2 ，此处略去证明。
如此我们可最多通过三次查询确定两个点集之间的连通情况。
定义 \mathbf S := \{u | \forall u,v \in \mathbf S: u与v连通\} ，且初始不妨设 \mathbf S = \{1\} .
当 |S| \ne |V| 时，考虑每次加入一个点，首先若 query(\mathbf S)=0 知不连通，直接结束。若 query(\mathbf S) \ne 0 ，那么令 \mathbf S' := \mathbf V \backslash \mathbf S ，将 \mathbf S' 均分为两个集合 \mathbf {L,R} ，不难证明 \mathbf S 与两集合中至少一个连通，由上述方法判断与 \mathbf L 是否连通 ，否则，必定与 \mathbf R 连通，以此类推，必定能找到一个连通的点加入。
分析总操作次数，最坏情况为 (n-1)(1+2 [\log_2(n-1)]) < 3500 ，可通过。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool vst[209];
int v;
int cnt;
int ask(string &s) {
cout << "? " << s << endl;
int res;
cin >> res;
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> v;
string s(v, '0');
s[0] = '1';
cnt = 1;
while (cnt < v) {
int q = ask(s);
if (q == 0) {
cout << "! 0" << endl;
return 0;
}
vector<int> c;
for (int i = 0; i < v; i++) {
if (s[i] == '0')
c.push_back(i);
}
int l = 0, r = c.size();
while (l < r - 1) {
int mid = (l + r) >> 1;
string s1(v, '0'), s2 = s;
for (int i = l; i < mid; i++) {
s1[c[i]] = '1';
s2[c[i]] = '1';
}
int q1 = ask(s1), q2 = ask(s2);
if (q + q1 != q2)
r = mid;
else
l = mid;
}
s[c[l]] = '1';
cnt++;
}
cout << "! 1" << endl;
return 0;
}