CH Round #45 能量释放

能量释放 CH Round #45 - alan有一些陷阱 III

题目描述

alan得到一块由个能量晶体构成的矿石,对于矿石中的每一个能量晶体,如果用化学物质刺激某一个能量晶体,就能使它释放能量。

它的能量释放强度与晶体本身的能量值以及能量晶体的位置有关。

为了方便研究,alan做了如下的定义。

能量集:一块矿石中的第个能量晶体到第个能量晶体(包含)构成的集合。

能量储存点:对于一块矿石中的能量晶体,若有,则称能量储存点。

能量释放点:在一个能量集中,若存在一个能量晶体,使得除它之外的所有能量晶体都是它的能量储存点,则称这个能量晶体是该能量集的能量释放点。

能量释放强度:对于一个能量集中的能量释放点来说,刺激这个能量晶体,该能量集中其余能量晶体会释放能量。该能量集的能量释放强度就等于该能量集中其余某个能量晶体的能量值与能量释放点的能量值的差的最大值。而第个能量晶体的能量释放强度则是所在的所有能量集的能量释放强度的最大值。

alan将给出矿石中能量晶体的个数,以及每个能量晶体的能量值,要求你求出每个能量晶体的能量释放强度。

输入格式

第一行1个整数,表示矿石中能量晶体的个数。

第二行个整数,第个整数表示第个能量晶体的能量值

输出格式

仅包含一行个整数,第个整数表示第个能量晶体的能量释放强度。

样例输入

5
3 2 1 2 3

样例输出

0 1 2 1 0

数据范围与约定

  • 对于20%的数据:
  • 对于60%的数据:
  • 对于100%的数据:
  • 温馨提醒:本题数据量较大,请尽量使用输入输出优化。

题解:
在考场上我写的是O(n)的单调队列(其实也相当于是单调栈。。。)+O(nlogn)的rmq
自己为能AC,结果只有一半
后来才知道如果数据规模达到百万以上,就一定得用O(n)的算法了,我还是太年轻啊。。。
今天准备做NOI2005瑰丽的华尔兹时,又用到了单调队列,忽然对这题有了想法,就又来做

这次我的算法,均摊应该是O(n)的吧。。。我想是这样。。。

其实考虑到a[i]左边的元素如果比a[j]小的话,那 j 管辖的范围 i 也也一定可以,(j 的初始值为 i-1)

所以我们直接跳到 j 管辖的范围的左边即可,即 j=l[j]-1 同时用 它来更新f[i]

最后跳不动的时候,j+1就是 l[i]

右边类似。。。

不知到复杂度是多少?怎么估计?求大神指教

自测稍有超时,后几个点都是1.2s左右的样子

代码:

1.考场 跑完所有数据需要 22s

 1 var  i,j,n,h,t:longint;
 2      f:array[0..2000000+10,0..20] of longint;
 3      a,q,l,r:array[0..2000000+10] of longint;
 4   procedure init;
 5    begin
 6      readln(n);
 7      for i:=1 to n do read(a[i]);
 8    end;
 9  procedure queue;
10    begin
11      a[0]:=-2100000000;a[n+1]:=a[0];
12      fillchar(q,sizeof(q),0);
13      h:=0;t:=0;
14      for i:=1 to n+1 do
15       begin
16         while (h<t) and (a[i]<a[q[t]]) do
17            begin
18              r[q[t]]:=i-1;
19              dec(t);
20            end;
21         inc(t);q[t]:=i;
22       end;
23      fillchar(q,sizeof(q),0);
24      h:=0;t:=0;
25      for i:=n downto 0 do
26        begin
27          while (h<t) and (a[i]<a[q[t]]) do
28            begin
29              l[q[t]]:=i+1;
30              dec(t);
31            end;
32          inc(t);q[t]:=i;
33        end;
34      end;
35 function max(x,y:longint):longint;
36  begin
37    if x>y then exit(x) else exit(y);
38  end;
39
40 procedure rmq;
41   begin
42     fillchar(f,sizeof(f),127);
43     for i:=1 to n do f[i,0]:=a[i];
44     for i:=1 to 22 do
45      begin
46        if (1<<i)>n then break;
47        for j:=1 to n-(1<<i)+1 do
48         f[j,i]:=max(f[j,i-1],f[j+1<<(i-1),i-1]);
49      end;
50   end;
51 function query(x,y:longint):int64;
52  var k:longint;
53  begin
54   k:=trunc(ln(y-x+1.0)/ln(2.0));
55   exit(max(f[x,k],f[y-(1<<k)+1,k]));
56  end;
57
58 procedure main;
59   begin
60     queue;
61     rmq;
62   //  for i:=1 to n do writeln(l[i],‘ ‘,r[i]);
63     for i:=1 to n do
64       write(query(l[i],r[i])-a[i],‘ ‘);
65   end;
66 begin
67   assign(input,‘input.txt‘);assign(output,‘output.txt‘);
68   reset(input);rewrite(output);
69   init;
70   main;
71   close(input);close(output);
72 end.
73                                    

2.20140806 跑完所有数据需要 6s

 1 {$inline on}
 2 const maxn=2000000+100;
 3 var l,r,a,f:array[0..maxn] of longint;
 4     i,n,j:longint;
 5     function max(x,y:longint):longint;inline;
 6      begin
 7        if x>y then exit(x) else exit(y);
 8      end;
 9
10 procedure init;
11  begin
12    readln(n);
13    for i:=1 to n do begin read(a[i]);f[i]:=a[i];end;
14  end;
15 procedure main;
16  begin
17    a[0]:=-maxlongint;a[n+1]:=-maxlongint;
18    l[1]:=1;
19    for i:=2 to n do
20     begin
21     j:=i-1;
22     while a[i]<=a[j] do
23      begin
24      if f[j]>f[i] then f[i]:=f[j];
25      j:=l[j]-1;
26      end;
27     l[i]:=j+1;
28     end;
29    r[n]:=n;
30    for i:=n-1 downto 1 do
31     begin
32     j:=i+1;
33     while a[i]<=a[j] do
34      begin
35      if f[j]>f[i] then f[i]:=f[j];
36      j:=r[j]+1;
37      end;
38     r[i]:=j-1;
39     end;
40    for i:=1 to n-1 do write(f[i]-a[i],‘ ‘);writeln(f[n]-a[n]);
41   end;
42 begin
43   assign(input,‘input.txt‘);assign(output,‘output.txt‘);
44   reset(input);rewrite(output);
45   init;
46   main;
47   close(input);close(output);
48 end.    

CH Round #45 能量释放

时间: 08-06

CH Round #45 能量释放的相关文章

从lca到树链剖分 bestcoder round#45 1003

bestcoder round#45 1003 题,给定两个点,要我们求这两个点的树上路径所经过的点的权值是否出现过奇数次.如果是一般人,那么就是用lca求树上路径,然后判断是否出现过奇数次(用异或),高手就不这么做了,直接树链剖分.为什么不能用lca,因为如果有树退化成链,那么每次询问的复杂度是O(n), 那么q次询问的时间复杂度是O(qn) 什么是树链剖分呢? 就是把树的边分成轻链和重链 http://blogsina.com.cn/s/blog_6974c8b20100zc61.htmlh

CH Round #17 舞动的夜晚

舞动的夜晚 CH Round #17 描述 L公司和H公司举办了一次联谊晚会.晚会上,L公司的N位员工和H公司的M位员工打算进行一场交际舞.在这些领导中,一些L公司的员工和H公司的员工之间是互相认识的,这样的认识关系一共有T对.舞会上,每位员工会尝试选择一名Ta认识的对方公司的员工作为舞伴,并且每位员工至多跳一支舞.完成的交际舞的数量越多,晚会的气氛就越热烈.顾及到晚会的气氛,员工们希望知道,哪些员工之间如果进行了交际舞,就会使整场晚会能够完成的交际舞的最大数量减小. 输入格式 第一行三个整数N

CH Round #52 还教室[线段树 方差]

还教室 CH Round #52 - Thinking Bear #1 (NOIP模拟赛) [引子]还记得 NOIP 2012 提高组 Day2 中的借教室吗?时光飞逝,光阴荏苒,两年过去了,曾经借教室的同学们纷纷归还自己当初租借的教室.请你来解决类似于借教室的另一个问题.[问题描述]在接受借教室请求的 n 天中,第 i 天剩余的教室为 a i 个.作为大学借教室服务的负责人,你需要完成如下三种操作共 m 次:① 第 l 天到第 r 天,每天被归还 d 个教室.② 询问第 l 天到第 r 天教室

BestCoder Round #45 (1,2)

比赛链接:http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=604 Dylans loves numbers Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 94    Accepted Submission(s): 67 Problem Description Wh

CH Round #30 摆花[矩阵乘法]

摆花 CH Round #30 - 清明欢乐赛 背景及描述 艺术馆门前将摆出许多花,一共有n个位置排成一排,每个位置可以摆花也可以不摆花.有些花如果摆在相邻的位置(隔着一个空的位置不算相邻),就不好看了.假定每种花数量无限,求摆花的方案数. 输入格式 输入有1+m行,第一行有两个用空格隔开的正整数n.m,m表示花的种类数.接下来的m行,每行有m个字符1或0,若第i行第j列为1,则表示第i种花和第j种花不能排在相邻的位置,输入保证对称.(提示:同一种花可能不能排在相邻位置). 输出格式 输出只有一

CH Round #57 - Story of the OI Class 凯撒密码

很有意思的一道题目 考场上想的是HASH成一个整数,把末位asicc码值*1,依次乘*10,得到一个整数,然后利用等差性.唯一性快排Nlogn乱搞的 证明如下: 对于明文abcde 密文 bcdef 有(a-b)*10000+(b-c)*1000+(c-d)*100+(d-f)*10+(e-f)*1=一个常数 这个常数我们可以预处理出来,对于任意的f[a,b],a,b属于小写字母,我们都可以预处理出来其值 好吧就是这个考场上写挂了 预处理出来之后依次排序维护标号然后O(n)一遍过就好,哎傻了 C

【题解】CH Round #61 取数游戏

取数游戏 CH Round #61 - 「Adera 10」冬令营热身赛 描述 SJY和CYF在玩一个取数游戏.他们将1~n分别写在n张纸上,随机排成一排,约定SJY先取,只能取走最边上的两张纸之一,然后CYF取:以此循环下去,取到1的人获胜.假设SJY和CYF足够聪明,求SJY获胜的概率. 输入 一个整数n 输出 SJY获胜的概率,保留最简分数形式(若为1,则输出1/1:若为0,则输出0/1). 样例 样例输入1 2 样例输出1 1/1 样例输入2 3 样例输出2 2/3 数据范围与约定 40

CH Round #56 - 国庆节欢乐赛解题报告

最近CH上的比赛很多,在此会全部写出解题报告,与大家交流一下解题方法与技巧. T1 魔幻森林 描述 Cortana来到了一片魔幻森林,这片森林可以被视作一个N*M的矩阵,矩阵中的每个位置上都长着一棵树,其中一些树上结有能够产生能量的魔力水果.已知每个水果的位置(Xi,Yi)以及它能提供的能量Ci.然而,魔幻森林在某些时候会发生变化:(1) 有两行树交换了位置.(2) 有两列树交换了位置.当然,树上结有的水果也跟随着树一起移动.不过,只有当两行(列)包含的魔力水果数都大于0,或者两行(列)都没有魔

CH Round #54 - Streaming #5 (NOIP模拟赛Day1)解题报告

最近参加了很多CH上的比赛呢~Rating--了..题目各种跪烂.各种膜拜大神OTZZZ T1珠 描述 萌蛋有n颗珠子,每一颗珠子都写有一个数字.萌蛋把它们用线串成了环.我们称一个数字串是有趣的,当且仅当它的第1位是2,且除了第1位以外的每一位都是3.例如,2,233,2333333都是有趣的数字串.现在,你可以从这串珠子的任意一颗开始读,沿着顺时针或逆时针方向,到任意一颗珠子停止.这样,你就可以读出一个数字串来.萌蛋想知道,所有能读出的有趣的数字串当中,最长的是哪一个数字串.当然,你也可能读不