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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3521][Poi2014]Salad Bar  

2015-07-13 20:29:31|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3521: [Poi2014]Salad Bar

感觉线性做法不太容易想
我的代码是nlogn的
感谢qmqmqm讲解
题解在代码下方

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1E6+10;
int MK[N*2],*mk = MK+int(1e6);
int n,m,left[N],right[N],data[N];
void set(int val){
for(int i=-n;i<=n;i++)mk[i] = val;
}
int st[28][N],two[100],Log2[N];
inline int ask(int l,int r){
int k = Log2[r-l+1];
return max(st[k][l],st[k][r-two[k]+1]);
}
int main(){
//freopen("in.txt","r",stdin);
int i,j;
scanf("%d",&n);
for(two[0]=i=1;i<=30;i++)two[i] = two[i-1]*2;
for(i=1;i<=n;i++){
char cc=' ';while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='p')data[i]=1;
else data[i]=-1;
Log2[i] = log2(i);
}
int now = 0;
//set();
for(i=1;i<=n;i++){
now += data[i];
if(data[i] > 0){
left[i] = mk[now+1]+1;
}else{
left[i] = i+1;
}
mk[now-data[i]] = i;
}
set(n+1);
now=0;
for(i=n;i;i--){
now += data[i];
if(data[i] > 0){
right[i] = mk[now+1]-1;
}else{
right[i] = i-1;
}
mk[now-data[i]] = i;
}

//for(i=1;i<=n;i++)printf("%d ",left[i]);printf("\n");
//for(i=1;i<=n;i++)printf("%d ",right[i]);printf("\n");
for(i=1;i<=n;i++)st[0][i] = right[i];
int lgn = Log2[n]+1;
for(j=1;j<=lgn;j++)
for(i=1;i+two[j-1]<=n;i++)
st[j][i] = max(st[j-1][i],st[j-1][i+two[j-1]]);
int ans = 0;
for(i=1;i<=n;i++)
if(data[i]>0){
int l = left[i],r=i;
while(l<r){
int mid = (l+r)/2;
if(ask(left[i],mid)>=i)r=mid;
else l = mid+1;
}
ans = max(ans,i-l+1);
}
printf("%d\n",ans);
return 0;
}

题解:
O(NlogN):
从左向右枚举i,同时记录一个前缀和,考虑从这个点向左选,那么一定是选到一个位置j满足sum[i]-sum[j]=-1,所以拿个表记录下来每个前缀和的最后位置,这样就能处理出每个点最多向左选多少(记为left[i])。
同理反过来能处理出每个点最多向右选多少(right[ ])。
然后枚举右端点i,问题就变成了求最小的j∈[left[i],i]且right[j]大于等于i
然后就st表+二分 / 线段树
O(N):
先搞出前缀和sum[]
然后从右往左枚举左端点i,它的right[i]就是最左边的位置j满足sum[j]<sum[i-1](也就是sum[j]=sum[i-1]-1),这样又靠右sum又大的就没用了。我们注意到最大的右端点一定是max{ (sum[j],j) }
我们维护一个单调栈,里面每个元素j记录的是[j,right[j]]的max(也就是j作为左端点的答案)。然后当枚举到i的时候,我们把所有sum[j]>=sum[i-1]的点都弹掉,并且顺势把这些j存的答案取max,这样就得到了[i,right[i]]的答案。
伪代码:

for i from n to 1
{
ans[i] = (sum[i],i)
whlie(!stack.empty() && sum[stack.top] >= sum[i-1])
{
ans[i] = max(ans[i],ans[stack.top])
stack.pop()
}
stack.push( (sum[i],i) )
update Ans
}


  评论这张
 
阅读(146)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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