题解：CF1687B Railway System

FiraCode · 2024-08-15 10:21:15 · 题解

看到 2m 次询问，考虑先把所有边的权值从小到大排序。

然后，考虑模拟 Kruskal，那么难点在判断当前边是否是链接了已联通的连通块。

那么我们可以考虑询问当前最小生成森林上的边加上当前边。

如果相比之前（设此时最大生成森林权为 w），加上边后的值若是 w+v_i，那么这条边就可以加到最大生成森林中。

询问次数为 2m-1。

#include <bits/stdc++.h>

using namespace std;

int n, m;
pair<int, int> v[100010];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        string s;
        for (int j = 1; j <= m; ++j)
            if (j != i) s += '0';
            else s += '1';

        cout << "? " << s << endl;
        cin >> v[i].first;
        v[i].second = i;
    }

    sort(v + 1, v + 1 + m);
    int la = v[1].first, sum = v[1].first;
    string s;
    for (int i = 1; i <= m; ++i) 
        if (i != v[1].second) s += '0';
        else s += '1';

    for (int i = 2; i <= m; ++i) {
        string t = s;
        t[v[i].second - 1] = '1';
        cout << "? " << t << endl;
        int val; cin >> val;
        if (val - la != v[i].first) ;
        else la = val, s = t, sum += v[i].first;
    }

    cout << "! " << la << endl;

    return 0;
}