CF1991D Prime XOR Coloring

原题链接：D. Prime XOR Coloring

Tag：思维

题目描述

给定一个无向图， 图中有编号从 \(1\) 到 \(n\) 的 \(n\) 个顶点， 当 \(u \oplus v\) 为一个质数的时候，\(u\) 和 \(v\) 之间存在一条边。

现在要用最少的颜色给图中的所有点染色， 要求没有一条边链接两个颜色相同的点。

输出颜色使用数量以及具体染色方案。

分析

先考虑一下 \(n \leq 5\) 的时候，其实并不用考虑， 因为样例已经为我们列好了。

我们从 \(6\) 开始考虑， 首先答案一定是 \(\geq 4\) 的， 因为 \(1,3,4,6\) 四个数字异或之后都是质数， 所以至少需要四个颜色。

我们考虑一下对于第 \(i\) 个点将其染色为 \(i \bmod 4 + 1\)。 那么在这个情况下，如果存在 \(u\) 和 \(v\) 是同色的， 也就是说 \(u\) 和 \(v\) 的关系满足 \(u = v (\bmod 4)\)。 既然在模 \(4\) 意义下是相等的，那么后两位一定是一样的， 我们把这两个数字做了异或，不可能是一个质数。

因此我们小范围抄样例，大范围按照上述方法构造就可以了。

代码实现

void NeverSayNever() {
    int n; cin >> n;
    vector<int> ans;
    if (n == 1) {
        cout << 1 << endl;
        cout << 1 << endl;
        return;
    }
    if (n == 2) {
        cout << 2 << endl;
        cout << 1 << ' ' << 2 << endl;
        return;
    }
    if (n == 3) {
        cout << 2 << endl;
        cout << 1 << ' ' << 2 << ' ' << 2 << endl;
        return;
    }
    if (n == 4) {
        cout << 3 << endl;
        cout << 1 << ' ' << 2 << ' ' << 2 << ' ' << 3 << endl;
        return;
    }
    if (n == 5) {
        cout << 3 << endl;
        cout << 1 << ' ' << 2 << ' ' << 2 << ' ' << 3 << ' ' << 3 << endl;
        return;
    }
    cout << 4 << endl;
    for (int i = 1; i <= n; ++i) {
        ans.push_back((i - 1) % 4);
    }
    for (auto &x: ans) cout << x + 1 << ' ';
    cout << endl;
}

额外思考

讲不通道理的，直接猜吧。

日志

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