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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1304】【Cqoi2009】【中位数图】  

2014-04-11 20:58:06|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:给出一个1~n的排列,求连续子串中以b为中位数的方案数。
    0.0 O(n^3)的算法显然暴力,但是有O(n)的方法,根据中位数的性质,咱们先找到b,(由于1~n的排列的保证,所以只有一个),然后咱们可发现..由于是中位数,咱们只关心每一个数与它的大小之比,所以可以把大于b的数看做1,然后小于b的数看做-1,然后问题转化成了求和为0的包含b的连续子串...这个只需要以b为前缀和后缀处理出前缀和和后缀和即可。
============================

program cqoi2009a;
var n,b:longint;
    a:array[0..100010]of longint;
    l,r:array[-100010..100010]of int64;
    ans:int64;

procedure init;
var i,pos,now:longint;
begin
  read(n,b);
  for i:=1 to n do
   begin
    read(a[i]);
    if a[i]=b then pos:=i;
   end;
  ans:=0;
  fillchar(l,sizeof(l),0);
  fillchar(r,sizeof(r),0);
  now:=0;l[0]:=1;
  for i:=pos+1 to n do
   begin
     now:=now+ord(a[i]>a[pos])-ord(a[i]<a[pos]);
     inc(l[now]);
   end;
  now:=0;r[0]:=1;
  for i:=pos-1 downto 1 do
   begin
     now:=now+ord(a[i]>a[pos])-ord(a[i]<a[pos]);
     inc(r[now]);
   end;
  for i:=-n to n do
   ans:=ans+l[i]*r[-i];
  write(ans);
end;

begin
  init;
end.


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

历史上的今天

评论

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

页脚

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