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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2728][HNOI2012]与非  

2015-03-20 17:55:55|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2728: [HNOI2012]与非

比较厉害的题

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
typedef long long ll;
const int LOGN = 66;
const int N = 1100;
ll n,m,base[LOGN],two[100],tmp,data[N];
short v[LOGN];
int bn;
ll solve(ll x){
if(x==-1)return -1;
ll re=0,now=0;
for(int i=1;i<=bn;i++)
if((now|base[i])<=x)
now|=base[i],re+=two[bn-i];
return re;
}
int main(){
int i,j;ll L,R;
cin >>n>>m>>L>>R;
for(i=1;i<=n;i++)cin>>data[i];
for(two[0]=i=1;i<=60;i++)two[i]=two[i-1]*2;
tmp = two[m]-1;
for(j=m-1;j>=0;j--)
if(!v[j]){
ll now=tmp;
for(i=1;i<=n;i++)
if(data[i]&two[j])now&=data[i];
else now&=~data[i];
base[++bn]=now;
for(i=0;i<=j;i++)
if(now&two[i])v[i]=1;
}
cout << solve(R)-solve(L-1) << endl;
return 0;
}

首先NAND操作可以合成其它一切位运算
然后我们把完全相同的位放到一起
这样就得到了一堆线性基
筛一下答案(相当于求出了二进制的上界壳)
  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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