bzoj 4245 OR-XOR

Posted on | Views:

贪心.

因为答案的形式是每一段的权值 $\text {or}$ 起来,从高位到低位考虑,贪心地让高位尽可能为 $0$ .

尝试让答案的第 $i$ 位为 $0$ ,就要求选出的 $m$ 个权值的第 $i$ 位都为 $0$ .

因为这 $m$ 段是连续的,所以就等价于选出 $m$ 个右端点,且最后一个必须选 $n$ .

求出原数列的前缀异或和,容易发现这 $m$ 个右端点处的前缀异或和第 $i$ 位都必须为 $0$ .

于是从高位往低位做,若当前位有至少 $m$ 个可选的位置(必须包含 $n$ ),则这一位对答案的贡献为 $0$, 否则为 $1$ .

每次贡献为 $0$ 时,将前缀异或和这一位为 $1$ 的位置标记出来,表示以后都不能再选了,否则会使得这一位为 $1$ .

注意要用 $\text{1LL}$ 参与位运算.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=5e5+10;
int n,m;
ll sum[MAXN];
bool vis[MAXN];
bool check(int k)
{
	if((sum[n]>>k)&1LL)
		return false;
	int cnt=0;
	for(int i=1;i<=n;++i)
		if(!((sum[i]>>k)&1LL) && !vis[i])
			++cnt;
	return cnt>=m;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		sum[i]=sum[i-1]^read();
	ll ans=0;
	for(int k=62;k>=0;--k)
	{
		if(check(k))
		{
			for(int i=1;i<=n;++i)
				if((sum[i]>>k)&1LL)
					vis[i]=true;
		}
		else
			ans|=(1LL<<k);				
	}
	printf("%lld\n",ans);
	return 0;
}