CF1991E Coloring Game

原题链接：E. Coloring Game

Tag：交互、图论

题目描述

这是一个交互题。

给定一个 \(n\) 个结点和 \(m\) 条边的无向图， 每个结点可以使用 \(1,2,3\) 其中的一个颜色进行染色。

\(Alice\) 和 \(Bob\) 在图上进行一个 \(n\) 轮的游戏：

首先 \(Alice\) 选择两种不同的颜色，之后 \(Bob\) 选择一个没有被染色的点， 使用 \(Alice\) 给出的两种颜色之一对这个点进行染色。

最后如果图上存在一条边链接了两个颜色相同的点的话，\(Alice\) 获胜。 否则 \(Bob\) 获胜。

图是给定的，我们选择一个必胜的玩家并且交互出策略。

分析

我们先考虑一下 \(Alice\)， 如果颜色只有两种，我们显然可以对图进行类似二分图染色的染色方案。 如果最后我们发现这个图不是一个二分图，也就是染色之后出现一条边链接了两个相同的颜色， 那么我们直接选 \(Alice\) 就可以了，只要每次给出相同的颜色就可以了。

如果图是一个二分图我们直接选择 \(Bob\)， 直接把图变成二分图来考虑， 假设分成左右两个部分，左面这部分我们让它是染 \(1\) 的， 右面这部分是染色 \(2\) 的。

每一轮中，由于 \(Alice\) 一定会给出 \(1,2\) 中的一个颜色， 如果出现了 \(1\)，我们就从左边选一个没染色的点进行染色， 如果出现了 \(2\)，我们就从右边选一个没染色的店进行染色。 这样一来，左边和右边的点一定有一边要先被染色完。 之后我们只需要用和已经被染色完成的那一边的颜色不同的颜色去染另一边的点就可以了。

代码实现

void NeverSayNever() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> color(n + 1,0);
    vector<bool> vis(n + 1,false);
    auto dfs = [&](auto &&self, int cur, int fa)->void {
        color[cur] = color[fa] ^ 1;
        vis[cur] = 1;
        for (auto &nxt: adj[cur]) {
            if (vis[nxt] == true) continue;
            self(self, nxt, cur);
        }
    };
    dfs(dfs, 1, 0);
    bool flag = true;
    for (int cur = 1; cur <= n; cur++) {
        for (auto &nxt: adj[cur]) {
            if (color[cur] == color[nxt]) {
                flag = false;
                break;
            }
        }
    }
    auto Alice = [&](){
        int x, y;
        cout << "Alice" << endl;
        for (int i = 0; i < n; i++) {
            cout << 1 << ' ' << 2 << endl;
            cin >> x >> y;
        }
    };
    auto Bob = [&]() {
        deque<int> color1, color2;
        for (int i = 0; i < n; i++) {
            if (color[i + 1] == 1) {
                color1.push_back(i + 1);
            } else {
                color2.push_back(i + 1);
            }
        }
        cout << "Bob" << endl;
        for (int i = 0; i < n; i++) {
            int tmp1, tmp2;
            int x, y;
            cin >> tmp1 >> tmp2;
            x = min(tmp1, tmp2);
            y = max(tmp1, tmp2);
            if ((x == 2 || y == 2) && color2.size() != 0) {
                cout << color2.front() << ' ' << 2 << endl;
                color2.pop_front();
                continue;
            } else if (x == 1 && color1.size() != 0) {
                cout << color1.front() << ' ' << 1 << endl;
                color1.pop_front();
                continue;
            }
            if (color1.size() == 0) {
                cout << color2.front() << ' ' << y << endl;
                color2.pop_front();
                continue;
            }
            if (color2.size() == 0) {
                if (x == 2) {
                    cout << color1.front() << ' ' << y << endl;
                } else {
                    cout << color1.front() << ' ' << x << endl;
                }
                color1.pop_front();
                continue;
            }
        }
    };
    if (flag) {
        Bob();
    } else {
        Alice();
    }
}

额外思考

赛时这个题爆了很多格式错误，太不应该了。

感觉这个题比较好的一个切入点是先考虑 \(Alice\) 以及如何从二分图角度去看待这个图。 如果想到了判断图是否是二分图，那么后面的做法应该是水到渠成的。

日志

本页面创建于 2024/7/30 02:38