BZOJ4245 : [ONTAK2015]OR-XOR

按位考虑,逐步确定答案。

设当前是第i位,求出第i位的前缀异或和。

若存在m个0且所有数字异或和为0,那么答案的这一位可以为0,并把所有1的位置给标记为不可选。

否则答案的这一位只能是1。

时间复杂度$O(nlog n)$。

#include<cstdio>
#define N 500010
int n,m,i,j,t,b[N],f[N];long long a[N],ans;
inline void read(long long&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
int main(){
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;i++)read(a[i]),f[i]=1;
  for(i=59;~i;i--){
    for(t=0,j=1;j<=n;j++){
      b[j]=b[j-1]^(a[j]>>i&1);
      if(!b[j]&&f[j])t++;
    }
    if(t>=m&&!b[n]){for(j=1;j<n;j++)if(b[j]&&f[j])f[j]=0;}else ans|=1LL<<i;
  }
  return printf("%lld",ans),0;
}

  

原文地址:https://www.cnblogs.com/clrs97/p/4742894.html