CQOI2009中位数图

原来在vijos上做过,当时根本看不懂

现在看起来这么水……

x记录从b向左连续走比k大的有多少个

y记录从b向右连续走比k大的有多少个

最后根据乘法原理乘一下

不过要加上x[0]+y[0]+1

因为实际上满足条件的序列有四种情况:

一、只选b,即为1

二、只在b左边选,即为x[0]

三、只在b右边选,即为y[0]

四、在两边都选,即为x[i]*y[-i]

Q.E.D

代码:

 var i,n,k,tmp:longint;
sum,ans:int64;
x,y:array[-..] of longint;
a:array[..] of longint;
procedure init;
begin
readln(n,tmp);
for i:= to n do
begin
read(a[i]);
if a[i]=tmp then k:=i;
end;
end;
procedure main;
begin
fillchar(x,sizeof(x),);
fillchar(y,sizeof(y),);
for i:=k- downto do
if a[i]>tmp then a[i]:= else a[i]:=-;
sum:=;
for i:=k- downto do
begin
sum:=sum+a[i];
inc(x[sum]);
end;
for i:=k+ to n do
if a[i]>tmp then a[i]:= else a[i]:=-;
sum:=;
for i:=k+ to n do
begin
sum:=sum+a[i];
inc(y[sum]);
end;
ans:=;
for i:=-n to n do inc(ans,x[i]*y[-i]);
inc(ans,x[]);inc(ans,y[]);
writeln(ans+);
end;
begin
init;
main;
end.
上一篇:powershell如何查看以及设置环境变量


下一篇:rails 项目部署中 nginx 报错及解决方法