P9384 [THUPC 2023 决赛] 着色

P9384 [THUPC 2023 决赛] 着色

思维题+构造

三元环还可以，五元环有点抽象，考虑将其全归为奇环，那么题目就变成：求一种设边权的方案，使得只用边权 \(i\) 无法构成奇环。

那么这个限制等价于只保留边权为 \(i\) 的边的图是二分图，那么一条边的两个端点得是不同属性。考虑怎么构造二分图，看到 \(0∼9\) 的边权和 \(n\) 的范围，考虑将其对应到二进制上每个位。构造方式：两点 \(i\) 和 \(j\) 之间连边权为 \(ctz(i\oplus j)\)。

证明这样连边的合法性，边权 \(i\) 连接的两个端点二进制上第 \(i\) 位一定不同，就将点分为了两类（第 \(i\) 位为 \(1\) 或为 \(0\)），此时如果保留边权为 \(i\) 的边，一定为二分图。

复杂度 \(O(n^2)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mk std::make_pair
#define fi first
#define se second
#define pb push_back

using i64 = long long;
using ull = unsigned long long;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;

int n;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	std::cin >> n;

	for (int i = 1; i < n; i++) {
		for (int j = 1; i + j <= n; j++) {
			std::cout << __builtin_ctz(i ^ (i + j)); 
		}
		std::cout << "\n";
	}	

	return 0;
}