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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[ICPCCamp2015]Or Max  

2015-03-14 18:05:20|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Or max

题意:

    给你一个序列,ans[k] = max{长度为k的区间的 or + max},求数组ans

调不出来就重构

这题还有一种用单调栈的做法,可能有代码有空去看看……

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
int n,m,dui[2][N],tmp[2][N],data[N];
int list[N][2][50],ans[N];
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
int i,j,k,t,kk;
n = scan();
for(i=1;i<=n;i++){
data[i]=scan();
}
t=0;
for(i=1;i<=n;i++){
for(j=1;j<=t;j++){
tmp[0][j] = (dui[0][j] | data[i]);
tmp[1][j] = dui[1][j];
}
kk=0;
tmp[0][++t] = data[i];
tmp[1][t] = i;
for(j=1;j<=t;j++)
if(j==1 || tmp[0][j] != tmp[0][j-1]){
kk++;
dui[0][kk] = tmp[0][j];
dui[1][kk] = tmp[1][j];
list[i][0][kk] = tmp[0][j];
list[i][1][kk] = tmp[1][j];
}t = list[i][0][0] = kk;
list[i][1][kk+1] = i+1;
}
t=0;
for(i=n;i;i--){
for(j=1;j<=t;j++){
tmp[0][j] = (dui[0][j] | data[i]);
tmp[1][j] = dui[1][j];
}
kk=0;
tmp[0][++t] = data[i];
tmp[1][t] = i;
for(j=1;j<=t;j++)
if(j==1 || tmp[0][j] != tmp[0][j-1]){
kk++;
dui[0][kk] = tmp[0][j];
dui[1][kk] = tmp[1][j];
}t = kk;
dui[1][kk+1] = i-1;
for(j=1;j<=t;j++)
for(k=1;k<=list[i][0][0];k++){
int d = (dui[1][j+1]+1) - (list[i][1][k+1]-1) + 1;
ans[d] = max(ans[d],data[i] + (dui[0][j]|list[i][0][k]));
}
}

//ans
int tmp=0;
for(i=1;i<=n;i++){
tmp = max(tmp,ans[i]);
printf("%d\n",tmp);
}
return 0;
}

题解:
    第一个奇怪的方法:
    对于当前区间先处理max,类似点分治,找到当前的max然后处理所有经过它的区间[l,r],从这个点把区间断掉,递归下去。
    问题是怎么处理or,可以注意到如果固定了一边,枚举另一边,那么可能的取值只有logn种,所以2*nlogn处理出每个点到左右所有点的or,然后每次以这个点为max的时候log^2n枚举两边的取值,然后更新ans.
    由于如果i < j那么一定有ans[i] <= ans[j]所以要保存最小的区间,每次单点修改,最后输出前缀max(因为修改是后缀更新)
    现在可以注意到由于要求答案的特殊性,我们的第一步完全没有必要,直接把所有点作为总区间的max即可
  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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