【BZOJ】4245: [ONTAK2015]OR-XOR

题意

给定一个长度为(n(1 le n le 500000))的序列(a_i(0 le a_i le 10^{18}))，将它划分为(m(1 le m le n))段连续的区间，设第(i)段的费用(c_i)为该段内所有数字的异或和，则总费用为(c_1 or c_2 or ... or c_m)。请求出总费用的最小值。

分析

这种题就考虑每一位。

题解

首先求出前缀和(s_i)
贪心地从大位扫向小位，我们只需要判断当前位(i)能否为(0)即可。
如果当前位能为0，则表示所有未删除的前缀和至少有(m)个第(i)位为0，而且(s_n)第(i)位必须是0，然后删除所有这一位不是1的前缀和。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll getint() {
	ll x=0;
	char c=getchar();
	for(; c<'0'||c>'9'; c=getchar());
	for(; c>='0'&&c<='9'; x=x*10+c-'0', c=getchar());
	return x;
}
ll a[500005];
int main() {
	int n=getint(), m=getint();
	for(int i=1; i<=n; ++i) {
		a[i]=getint();
		a[i]^=a[i-1];
	}
	ll ans=0;
	for(int j=63; ~j; --j) {
		if((a[n]>>j)&1) {
			ans|=1ll<<j;
			continue;
		}
		int cnt=0;
		for(int i=1; i<=n; ++i) {
			if(a[i]>=0 && !((a[i]>>j)&1)) {
				++cnt;
			}
		}
		if(cnt>=m) {
			for(int i=1; i<=n; ++i) {
				if(a[i]>=0 && ((a[i]>>j)&1)) {
					a[i]=-a[i];
				}
			}
		}
		else {
			ans|=1ll<<j;
		}
	}
	printf("%lld
", ans);
	return 0;
}