注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[ICPCCamp2015]XOr  

2015-03-16 17:44:07|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

XOr

题意:
给你一个数列a[ ]要求你化成恰好连续的m份,代价是每份分别xor的值再or起来,求最小代价。
一个非常傻逼的地方搞了好久……

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2E5+100;
int n,m,data[N],tmp[N],list[N],cpy[N],two[50];
short v[N];
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
int i,j,k;
n = scan();m = scan();
for(two[0]=i=1;i<=30;i++)two[i]=two[i-1]*2;
for(i=1;i<=n;i++){
data[i] = scan();
tmp[i]=i;
if(data[i]>data[0])data[0]=data[i];
}tmp[i]=i;
tmp[0]=n;
j=0;while(two[j+1]<=data[0])j++;
int ans = 0;
for(;j>=0;j--){
int cot=list[0]=0;
for(i=1;i<=n;i++){
if(data[i]&two[j]){
cot++;
list[++list[0]]=i;
}
v[i]=0;
}
if(cot&1){ans+=two[j];continue;}
k=1;cpy[0]=0;
short type=0;
for(i=1;i<=list[0];i++){
if(!v[k])v[k]=type+1;
while(k <= tmp[0] && tmp[k+1] <= list[i]){
if(v[k]<2)cpy[++cpy[0]] = tmp[k];
if(!v[++k])v[k]=type+1;
}

type^=1;
}
for(;k<=tmp[0];k++)
if(v[k]<2)cpy[++cpy[0]]=tmp[k];
if(cpy[0] < m){ans+=two[j];continue;}
for(i=1;i<=cpy[0];i++)tmp[i]=cpy[i];tmp[0]=cpy[0];
// for(i=1;i<=list[0];i++)printf("%d ",list[i]);printf("\n");
// for(i=1;i<=tmp[0];i++)printf("%d ",tmp[i]);printf("\n");
tmp[tmp[0]+1] = n+1;
}
printf("%d\n",ans);
return 0;
}

题解:
因为是xor最后or起来,所以和直接xor是类似的,贪心选择,尽可能使得最大的最小。
现在我们只取某一位上的值,于是变成了01序列,如果1的个数是奇数,那么这一位一定要被加到方案里。
如果是偶数,那么必然是从前向后,第2*i-1和第2*i个1必须要在一个区间里,我们把这些区间先并起来。
然后每次做的时候都把必须并的区间并一下,如果发现并完之后<m就说明这一位无论如何也要选。
这样从大到小做log次就得到了答案
  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017