AFO

题解 P7211 【[JOISC2020] カメレオンの恋】

2021-01-31 16:58:10


先考虑知道性别的情况。

设 $S$ 是另一侧的某个集合,考虑询问 $\{u\}\cup S$ 可能出现的结果。如果 $S$ 中有喜欢 $u$ 的 / $u$ 喜欢的 / 与 $u$ 同色的变色龙,那么结果为 $\lvert S\rvert$。这样子就可以通过至多 $3$ 次二分找到和 $u$ 有特殊关系的点。

显然 $u$ 有特殊关系的点只可能有 $1$ 个或 $3$ 个。如果为 $1$ 个,那一定是同色的;否则我们可以每次询问其中的两个和 $u$ 来找到 $u$ 喜欢的那一只。

在确定所有喜欢的关系后,剩下的就是同色的了。

现在考虑不知道性别的情况,此时的主要问题在于分离二分图两侧的点集。

但事实上我们并不需要分离两侧的点集,我们只需要让 $S$ 内部没有特殊关系即可。于是我们把之前已经确定的特殊关系拿出来二分图染色,对两侧的点分别跑一遍即可。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#include "chameleon.h"
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

const int N = 1000 + 10;

int Query(vector<int> vec, int u) { vec.emplace_back(u); return Query(vec); }

int vis[N], col[N];
vector<int> E[N], G[N];

void dfs(int u, int c) {
    vis[u] = 1, col[u] = c;
    for (int v : E[u]) if (!vis[v]) dfs(v, c ^ 1);
}

void find(int u, vector<int> vec) {
    for (int v : E[u]) {
        auto it = find(vec.begin(), vec.end(), v);
        if (it != vec.end()) vec.erase(it);
    }
    while (Query(vec, u) != vec.size() + 1) {
        vector<int> res = vec;
        while (res.size() != 1) {
            vector<int> l, r;
            for (int i = 0; i < res.size(); ++i) {
                if (i & 1) l.emplace_back(res[i]);
                else r.emplace_back(res[i]);
            }
            if (Query(l, u) == l.size() + 1) res = r;
            else res = l;
        }
        int v = res.back();
        E[u].emplace_back(v), E[v].emplace_back(u);
        auto it = find(vec.begin(), vec.end(), v);
        if (it != vec.end()) vec.erase(it);
    }
}

void Solve(int n) {
    for (int i = 1; i <= n << 1; ++i) {
        memset(vis, 0, sizeof(vis));
        for (int j = 1; j < i; ++j)
            if (!vis[j]) dfs(j, 0);
        vector<int> vec;
        for (int j = 1; j < i; ++j)
            if (col[j]) vec.emplace_back(j);
        if (!vec.empty()) find(i, vec);
        vec.clear();
        for (int j = 1; j < i; ++j)
            if (!col[j]) vec.emplace_back(j);
        if (!vec.empty()) find(i, vec);
    }
    for (int u = 1; u <= n << 1; ++u) {
        if (E[u].size() != 3) continue;
        int v;
        if (Query({u, E[u][0], E[u][1]}) == 1) v = E[u][2];
        else if (Query({u, E[u][0], E[u][2]}) == 1) v = E[u][1];
        else v = E[u][0];
        G[u].emplace_back(v), G[v].emplace_back(u);
    }
    memset(vis, 0, sizeof(vis));
    for (int u = 1; u <= n << 1; ++u) {
        if (vis[u]) continue;
        for (int v : G[u]) {
            auto it = find(E[u].begin(), E[u].end(), v);
            if (it != E[u].end()) E[u].erase(it);
        }
        int v = E[u].back();
        Answer(u, v), vis[u] = vis[v] = 1;
    }
}