题解：P9384 [THUPC 2023 决赛] 着色

· · 题解

思路分析

题目要求将完全图 K_n 的每条边染 0\sim 9 十种颜色之一，使得没有任何一种颜色的边构成三角形或五元环（即同色奇环）。

二分图没有奇环，所以如果每种颜色的边集都是二分图，则条件自动满足。 于是问题转化为：能否将 K_n 的边划分成 10 个二分图？

我们可以用二进制编码的方法构造：

给每个顶点分配一个 10 位的二进制数，且所有顶点的编码互不相同。

第 c 种颜色对应一个顶点二划分：编码第 c 位为 0 的顶点在一部，为 1 的在另一部。

对于边 (u,v)，若 u,v 的编码在第 c 位不同，则可将该边染成颜色 c（若有多个不同位，任选一个，比如最低不同位）。

这样，每种颜色的边都只连接两部之间，因此该颜色的子图是二分图，不含奇环。

因为 10 位二进制数共有 2^{10}=1024 种不同编码，而 n\le 1000，所以总可以给每个顶点分配互不相同的编码。因此对于所有 n\le 1000，方案一定存在。

本题只需按上述方法构造，并输出任意一种合法染色即可。

AC代码：


#include <bits/stdc++.h>
using namespace std;
int n,id[1005];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) id[i] = i - 1;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= n - i; j++) {
            int u = i;
            int v = i + j;
            int diff = id[u] ^ id[v];
            int c = 0;
            while (!(diff & (1 << c))) c++;
            cout << c;
        }
        cout << endl;
    }
    return 0;
}