Maximize-XOR

ACM 题解 DFS 位运算

发布时间 : 2026-04-01 10:07

C(n,k) <= 1e6
考虑爆搜

但是之间搜会T qwq

转换一下转换Cn_k = Cn_n-k

变为不选n-k个的最大值
根据异或两次等于没有异或的性质，先求所有的异或和再爆搜即可

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
ll ans = 0;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k;
	cin >> n >> k;
	vector<ll> a(n+1);
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum ^= a[i];
	}
	k = n - k;
	auto dfs = [&] (auto&& self,int cur,int step, int v) -> void {
		if (step == k) {
			ans = max(ans,v);
			return;
		}
		if (cur > n) {
			return;
		}
		self(self,cur+1,step+1,v^a[cur]);
		self(self,cur + 1, step, v);
	};
	if (k > n - k) {
		sum = 0;
		k = n - k;
	}
	dfs(dfs,1,0,sum);
	cout << ans;
	return 0;
}