P7211

xht · 2023-04-18 22:29:07 · 题解

对于两个点 x,y，如果我们按照如下方式建图：

• 若 x,y 颜色相同，则 x,y 之间连一条无向边，记为 x \leftrightarrow y。
• 若 x 喜欢 y，则连一条 x \to y 的有向边。

先不考虑询问的限制次数。

如果我们询问所有的点对 (x,y)，返回的结果要么为 1，要么为 2。

如果为 1，则只有以下三种情况：

容易发现，当答案为 1 时，x,y 之间一定有边；答案为 2 时，x,y 之间一定无边，除了 x \to y 且 y \to x 的情况。

进一步可以发现，每个点的度数都是 3，但是询问出来的度数可能为 1。

若询问出来 x 的度数为 1，则说明存在一个度数同样为 1 的点 y，符合 x \to y 且 y \to x 的情况，而询问出来的那条边，则是一条无向边 x \leftrightarrow z，这意味着 x,z 的颜色相同。

若询问出来 x 的度数为 3，设这 3 个点为 y,z,w。考虑到如果我们询问 (x,y,z),(x,y,w),(x,z,w)，其中有且仅有一组的答案为 1，其它两组的答案都为 2。

不妨设为 1 的询问为 (x,y,z)，则只可能是 x \leftrightarrow y 且 z \to x，或者 x \leftrightarrow z 且 y \to x。

尽管我们无法得知是哪种，但是我们可以以此确定 x \to w 这条边。

通过这种方法，我们可以确定所有的有向边，那么剩下的边就是无向边，即颜色相同的点。

这个做法的询问次数为 \mathcal O(n^2) 的，瓶颈在询问两两点对上。

考虑优化这个过程。

我们可以通过 \mathcal O(n) 次询问求出一个极大独立集。

方法为，从 1 \sim 2n 依次尝试加入当前的极大独立集 S，如果询问 (S,x) 的答案为 |S| + 1，则说明可以加入，否则说明有边。

找到极大独立集之后，对于独立集之外的点，在独立集中二分找到所有边。

此时还剩下独立集之外的点中的边没有找到，那么重复上述过程，直到所有剩下的点都是一个独立集。

由于每个点的度数最多为 3，因此每次独立集的大小 \ge 总点数的 \frac 14。这意味着每次我们可以将点的规模缩小到原来的 \frac 34，那么一共只需要最多重复 \mathcal O(\log n) 次就能找到所有边，因此求最大独立集部分的询问次数为 \mathcal O(n \log n)。

又由于每找到一条边需要一次二分，而边数是 \mathcal O(n) 的，所以二分部分也只有 \mathcal O(n \log n) 次询问。

这样我们就可以用 \mathcal O(n \log n) 次询问找到所有边，为了减小常数防止被卡，可以先对点进行 random_shuffle。

inline int get(int x, vi p) {
    int l = 0, r = p.size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        vi q(1, x);
        for (int i = l; i <= mid; i++) q.pb(p[i]);
        if (Query(q) != (int)q.size()) r = mid;
        else l = mid + 1;
    }
    return p[l];
}

inline int ask(int x, int y, int z) {
    vi p(3);
    p[0] = x, p[1] = y, p[2] = z;
    return Query(p);
}

void Solve(int n) {
    srand(time(0));
    vi A, B;
    for (int i = 1; i <= (n << 1); i++) B.pb(i);
    random_shuffle(B.begin(), B.end());
    vector<vi> e(n << 1 | 1);
    while (B.size()) {
        vi S = B, v(n << 1 | 1);
        A.clear(), B.clear();
        for (int x : S) {
            A.pb(x);
            if (Query(A) != (int)A.size()) A.pop_back(), B.pb(x);
            else v[x] = 1;
        }
        for (int i : B) {
            vi p = A;
            p.pb(i);
            do {
                p.pop_back();
                int k = get(i, p);
                e[k].pb(i), e[i].pb(k);
                for (int &x : p)
                    if (x == k) swap(x, p.back());
                p.pop_back();
                p.pb(i);
            } while (Query(p) != (int)p.size());
        }
    }
    vi v(n << 1 | 1);
    vector<map<int, bool>> f(n << 1 | 1);
    for (int x = 1; x <= (n << 1); x++)
        if (e[x].size() == 3u) {
            int y = e[x][0], z = e[x][1], w = e[x][2];
            if (ask(x, y, w) == 1) swap(z, w);
            else if (ask(x, z, w) == 1) swap(y, w);
            f[x][w] = f[w][x] = 1;
        }
    for (int x = 1; x <= (n << 1); x++)
        if (!v[x])
            for (int y : e[x])
                if (!f[x][y]) v[x] = v[y] = 1, Answer(x, y);
}