BZOJ4245: [ONTAK2015]OR-XOR 贪心
题解：
从高到低按位贪心，预处理前缀异或和，若想这一位为0的话则必须选择的终点位置前缀和这一位均为0。
如果可以令这一位为0，则处理一下可选集合就行了。
时间复杂度$O(nlogn)$。
代码：
#include<cstdio>
#include<cctype>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 500010
ll a[N];
bool del[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("tt.in","r",stdin);
#endif
int n,m,i,j;
cin>>n>>m;
for(i=1;i<=n;++i)
scanf("%lld",&a[i]),a[i]^=a[i-1];
ll ans=0;
bool ok;
int cnt;
for(i=59;i>=0;--i){
ok=1;
if((a[n]>>i)&1)
ok=0;
else{
for(cnt=0,j=1;j<n;++j)
if(!del[j]&&(((a[j]>>i)&1)==0))
++cnt;
if(cnt<m-1)
ok=0;
}
if(ok){
for(j=1;j<n;++j)
if((a[j]>>i)&1)
del[j]=1;
}
else
ans|=(1ll<<i);
}
cout<<ans<<endl;
return 0;
}
评论 (0)