Atcoder ZEP F题

题意

\(\;\)
给定\(n,m\)，其中\(n=2^k\)，再给一个长度为\(m\)的数组\(A\)
点\(i,j\)间可以连边当且仅当\(i\;xor\;j \notin A\)
问是否有一种方案，使得这\(n\)个点构成一棵树，构造出这种方案
否则输出-1
\(k\leq 18\)
\(\;\)

Solution

\(\;\)
先考虑是否有解。
我们取出\(A\)的补集\(B\)。
你会发现，往外连边实际上就是不断异或上\(B\)中的元素。
如果有解，当且仅当\(b_1,b_2,\cdots,b_{n-m}\)中某些数的异或和能够表示出\(0\)到\(n-1\)的所有数
所以，我们可以构造出\(B\)的线性基，判断线性基大小是否为\(k\)即可。
\(\;\)
怎么构造方案呢？
因为线性基中的每个元素实际上都可以表示为：成功插入线性基的一部分\(b_i\)的异或和
所以我们只需要管那些成功插入到线性基中的\(b_i\)就可以了，而这样的数最多有\(log\; n\)个
\(\;\)
然后我们就从0到\(n-1\)进行枚举，只使用这\(k\)个\(b_i\)，能往外连边就贪心地连，再用并查集维护一下连通性即可。
\(\;\)

Code

#include <bits/stdc++.h>
 
const int N = 500010;
 
int n, m, k, d[20], st[N], cnt, tmp[20], fa[N];
 
void ins(int x) {
	int X = x;
	for (int i = k; ~i; i --) {
		if (!(x >> i & 1)) continue;
		if (d[i]) x ^= d[i];
		else {
			d[i] = x; tmp[i] = X;
			cnt ++;
			return;
		}
	}
}
 
int find(int x) {
	if (fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}
int main() {
	scanf("%d%d", &n, &m);
	k = (int) log2(n);
	for (int i = 1; i <= m; i ++) {
		int x; 
		scanf("%d", &x); st[x] = 1;
	}
	for (int i = 0; i < n; i ++) {
		if (!st[i]) ins(i);
	}
	if (cnt < k) {
		puts("-1");
		return 0;
	}
	for (int i = 0; i < n; i ++) fa[i] = i;
	for (int i = 0; i < n; i ++) {
		for (int j = 0; j <= k; j ++) {
			if (find(i) != find(i ^ tmp[j])) {
				fa[find(i)] = find(i ^ tmp[j]);
				printf("%d %d\n", i, i ^ tmp[j]);
			}
		}
	}
	return 0;
} 

Atcoder ZEP F题

原文：https://www.cnblogs.com/czyty114/p/14725759.html