Codeforces 1163E 高斯消元 + dfs

题意：给你一个集合，让你构造一个长度尽量长的排列，使得排列中任意相邻两个位置的数XOR后是集合中的数。

思路：我们考虑枚举i, 然后判断集合中所有小于1 << i的数是否可以构成一组异或空间的基，如果可以就可以通过深搜构造出来。判断的方法是通过高斯消元。找到最大的i，我们通过深搜的方式构造答案，深搜的时候通过枚举作为基的集合中的数来确定，这样相邻两个数之间的异或值一定是集合中的数。

标程中的找异或空间的算法有点奇特，先记录一下：

维护一个集合basis，是已经找到的基，加入一个新的数(x)时，在basis中从大到小，执行x = min(x, x ^ v) (v是basis中的元素），如果最后x不是0，那么x就是一个基底，插入basis。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 200010;

const int maxm = 2000010;

vector<int> ans, vec;

set<int> basis;

set<int> ::iterator it;

int ed;

bool v[maxm];

int a[maxn];

void add(int x) {//高斯消元

	int tmp = x;

	if(basis.size()) {

		for (it = --basis.end();; it--) {

			tmp = min(tmp, tmp ^ (*it));

			if(it == basis.begin()) break;

		}

	}

	if(!tmp) return;

	basis.insert(tmp);

	vec.push_back(x);

}

void dfs(int x, int deep = 1) {

	v[x] = 1;

	ans.push_back(x);

	if(deep == (1 << ed)) return;

	for (int i = 0; i < vec.size(); i++) {

		if(!v[x ^ vec[i]]) {

			dfs(x ^ vec[i], deep + 1);

			return;

		}

	}

}

int main() {

	int n;

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {

		scanf("%d", &a[i]);

	}

	sort(a + 1, a + 1 + n);

	int pos = 1;

	ed = 0;

	for (int i = 1; i < 20; i++) {

		for (; pos <= n && a[pos] < (1 << i); pos++)

			add(a[pos]);

		if(basis.size() == i) {

			ed = i;

		}

	}

	basis.clear();

	vec.clear();

	for (int i = 1; i <= n && a[i] < (1 << ed); i++)

		add(a[i]);

	dfs(0);

	printf("%d\n", ed);

	for (int i = 0; i < ans.size(); i++)

		printf("%d ", ans[i]);

}

巴特西

Codeforces 1163E 高斯消元 + dfs

最新文章

热门文章