题目#
https://qoj.ac/contest/1849/problem/9783/statement/zh_cn ↗
思路#
记 代表 节点之间的距离,不难注意到: 等价于 ,此处略去证明。
如此我们可最多通过三次查询确定两个点集之间的连通情况。
定义 ,且初始不妨设 .
当 时,考虑每次加入一个点,首先若 知不连通,直接结束。若 ,那么令 ,将 均分为两个集合 ,不难证明 与两集合中至少一个连通,由上述方法判断与 是否连通 ,否则,必定与 连通,以此类推,必定能找到一个连通的点加入。
分析总操作次数,最坏情况为 ,可通过。
代码#
#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;
}
cpp