IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    BZOJ4245: [ONTAK2015]OR-XOR 贪心

    wyfcyx发表于 2015-09-04 15:34:59
    love 0

    题解:

    从高到低按位贪心,预处理前缀异或和,若想这一位为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;
    }


沪ICP备19023445号-2号
友情链接