题目大意

给出一个长度为 \(n\) 的数组，选出一些数异或之和为 \(s1\)，其余数异或之和为 \(s2\)，求 \(s1+s2\) 最大时 \(s1\) 的最小值。

思路

你发现如果你设 \(s\) 为所有数的异或和，那么如果 \(s\) 某一位为 \(0\) 就可以拆成\(1\oplus 1\)，不同就只能拆成 \(0\oplus 1\)，所以我们应该多拆 \(0\) ，这个用线性基实现即可。

\(\texttt{Code}\)

#include <bits/stdc++.h>

using namespace std;

#define Int register int

#define ll long long

#define MAXN 100005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}

template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}

template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,tot,b[63];

ll s,s2,a[MAXN],p[63];

void ins (ll x){

	for (Int i = 1;i <= tot;++ i)

		if (x & (1ll << b[i])){

			if (!p[i]){p[i] = x;break;}

			else x ^= p[i];

		}

}

signed main(){

	read (n);

	for (Int i = 1;i <= n;++ i) read (a[i]),s ^= a[i];

	for (Int i = 62;~i;-- i) if (!(s >> i & 1)) b[++ tot] = i;

	for (Int i = 62;~i;-- i) if (s >> i & 1) b[++ tot] = i;

	for (Int i = 1;i <= n;++ i) ins (a[i]);

	for (Int i = 1;i <= tot;++ i) if (!(s2 & (1ll << b[i]))) s2 ^= p[i];

	write (s ^ s2),putchar ('\n');

	return 0;

}

巴特西

题解「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set

题目大意

思路

\(\texttt{Code}\)

最新文章

热门文章