题解：P8019 [ONTAK2015] OR-XOR

题意概述

题目清晰明了不做赘述。

思路分析

涉及区间的异或和，我们考虑维护前缀异或和。要总费用尽可能的小，就贪心的让分的每一段的高位尽可能为零，那就要考虑把每一位拆开进行处理。

Solution

从高位到地位枚举。

如果这一位的这个数的前缀异或和的零的个数少于 $m$ ，那么可以证明这一位不可能为零。
如果这一位的最后一个数的前缀疑惑和，那么不可能存在一种方案使得这一位为零。
因为低位要在符合高位为零的情况下为零，所以如果这一位的这个数为零但是这个数不能作为高位的隔断，那么这个零无法起到隔断作用，即这个零无效不统计在内。

Code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,m,a[N],maxv,s,ans;
bool vis[N];

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		maxv=max(maxv,a[i]);
		a[i]^=a[i-1];
	}
	for(;maxv;s++) maxv>>=1;
	for(int i=s-1;i>=0;i--)
	{
		int d=0;
		for(int j=1;j<=n;j++) d+=(!((a[j]>>i)&1)&&!vis[j]);//这个数的这一位为零且能作为之前高位的隔断才有效
		if(d<m||(a[n]>>i)&1)
		{
			ans+=1ll<<i;
			continue;
		}
		for(int j=1;j<=n;j++) vis[j]=((a[j]>>i)&1||vis[j]);//如果这一位为一那么就不能作为隔断
	}
	cout<<ans;
	return 0;
}

题解：P8019 [ONTAK2015] OR-XOR

文章操作

题意概述

思路分析

Solution

Code

相关推荐

评论

题解：P8019 [ONTAK2015] OR-XOR