题解

75 条题解

  • 0
    @ 2010-03-15 14:37:22

    直接裸奔……

    编译通过...

    ├ 测试数据 01:运行超时...

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 41ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 25ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:运行超时...

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:运行超时...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:60 有效耗时:66ms

    看题解…队列维护+二分+边界注意…

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    -.-

  • 0
    @ 2009-11-11 20:24:54

    NlgN导弹拦截

    (队列,二分)

  • 0
    @ 2009-11-09 08:24:53

    为什么我没有秒杀!!!!!

  • 0
    @ 2009-10-29 16:46:13

    哈哈 第一次编对二分查找了!!!!

    庆祝一下!!!

    另:只用单调队列优化会超时!!!!

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    ---|---|---|---|---|---|---|晒程序啊---|---|---|---|---|---|-

    var

    a,s:array[0..300001] of longint;

    f:array[0..300001] of boolean;

    n,k,i,j,t:longint;

    function find(l,r,x:longint):longint;

    var y:longint;

    begin

    if r-l=1 then exit(l);

    y:=(l+r) div 2;

    if x=s[y] then exit(y);

    if x>s[y] then find:=find(y,r,x)

    else find:=find(l,y,x);

    end;

    begin

    readln(n,k);

    for i:=1 to n do

    read(a[i]);

    for i:=1 to k-1 do

    if a[i]

  • 0
    @ 2009-10-27 21:13:01

    一般化方法:

    在第k个前面且大于第k个数字的设为-inf,

    在第k个后面且小于第k个数字的设为+inf.

    注意要用大于int 类型。

  • 0
    @ 2009-10-15 17:01:03

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 9ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:9ms

  • 0
    @ 2009-10-10 15:06:28

    编译通过...

    ├ 测试数据 01:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 9ms

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:90 有效耗时:9ms

    不明真相...cheat

  • 0
    @ 2009-10-08 10:06:52

    60 70分的看过来

    如果二分是 l+1《r的

    注意更新队列是1的特殊性 还有一定不能 r=mid-1 要r=mid 因为r=mid-1有可能变成0

    不明白的用这组数据看看 不要看答案 看队列的更新 我在这里挂了1个小时

    14 3

    0 0 0 6 8 4 5 6 7 9 8 9 5

    在第6个地方 注意队列的第一位更新情况

  • 0
    @ 2009-08-18 21:38:32

    找了一篇讲 LIS的文章,看了好久才懂....

    关于二分查找怎么写的问题:这个写的不错 最后的 p 是 接上去之后的长度;

    for(int i = 1;i

  • 0
    @ 2009-04-26 11:28:33

    这是教主出的题,该题就是最长上升序列的优化版,分前后两段考虑前一段的最大值不能大于a[k],后一段的最小值不能小于a[k],动归:b[i]为长度为i的最长上升序列的最后一个数的最小值,用二分查找,可以达到nlogn的复杂度。

    注意!!最后要打的东西是长度,不是序列!!!!

  • 0
    @ 2009-04-11 22:39:40

    左右分开处理

    左边加上一个条件即可:

    if(l>0 || i==k)

    s[l+1]=max(s[l+1],x[i]);

  • 0
    @ 2009-03-17 18:39:16

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    写了 个极猥琐 的 二分 , 结果竟然 秒杀 了……

    function xx(x:longint):longint;

    var

    i,j:longint;

    begin

    if x>b[num] then

    begin

    inc(num);

    b[num]:=x;

    exit(num);

    end;

    i:=1;j:=num;

    repeat

    while (b[(i+j)shr 1]=x)and(j(i+j)shr 1) do

    j:=(i+j)shr 1;

    until i+1>=j;

    if b[i]>=x then begin b[i]:=x;exit(i);end

    else begin b:=x;exit(i+1);end;

    end;

    f[i]:=xx(a[i]);

  • 0
    @ 2009-03-11 17:00:47

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 25ms

    program haoshui;

    var

    a,b,c,d,e,f,g:longint;

    m,n,k:longint;

    arr,brr,crr:array[0..300000] of longint;

    function main(a,n:longint):longint;

    var

    i,x,l,r,mid:longint;

    begin

    if a>n then exit(0);

    m:=1;

    crr[1]:=brr[a];

    for i:=a+1 to n do begin

    x:=brr[i];

    if x>crr[m] then begin inc(m); crr[m]:=x; end;

    l:=1; r:=m;

    while l

  • 0
    @ 2009-01-17 20:58:09

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    --------------------------------------

    var

    i,j,k,n,m:longint;

    a,f,g:array[0..300000]of longint;

    procedure li(x,l,r:longint);

    var

    i,j,mid:longint;

    begin

    if a[x]g[mid]

    then run(x,mid,r)

    else run(x,l,mid);

    end;

    begin

    read(n,m);

    for i:=1 to n do

    read(a[i]);

    f[0]:=a[m];

    k:=0;

    for i:=m downto 1 do

    if a[i]g[0]

    then run(i,0,k);

    write(k+j+1);

    end.

    就是以m为起点 分别做一次m downto 1 的最长递减,与m to n 的最长上升.

    注意点m为起点不可更新,判断一下即可AC.

  • 0
    @ 2009-01-17 19:38:09

    90分,干了见降rp的事,cheat了~~~~

    我的方法是把k前面小于k的放到另一数组,k后面大于k的也放过去,然后LIS,但为什么第一个点标准输出事601,而我的是603,我的算法错了么?

  • 0
    @ 2008-11-30 23:01:26

    首先数据范围肯定得用O(nlogn)算法

    在1~k时候常规做法

    在k+1~n的时候把前面的数组清零,并把b[0]设为a[k]

    而且必须要mid!=0时才更新,这样后面就是第一项是a[k]的最长上升子序列长度

    最后在d[k+1]~d[n]找出最大的,输出max+d[k]即可

    虽然没全0不过一共72ms~~很有成就感的说

  • 0
    @ 2008-11-11 15:44:09

    program p1369;

    var i,j,k,mid,l,r,n:longint;

    max,js:int64;

    a,d:array [0..300010] of longint;

    begin

    read(n,k);

    for i:=1 to n do begin read(a[i]);d[i]:=maxlongint;end;

    for i:=1 to k-1 do

    begin

    if a[i]1 do

    begin

    mid:=(r+l)div 2;

    if d[mid]>a[i] then r:=mid else l:=mid;

    end;

    if d[r]a[k] then

    begin

    l:=0;r:=max;

    while r-l>1 do

    begin

    mid:=(r+l)div 2;

    if a[i]

  • 0
    @ 2009-11-06 17:38:57

    编译通过...

    ├ 测试数据 01:运行超时...

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 88ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 41ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:运行超时...

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:运行超时...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:100有效耗时:129ms

  • 0
    @ 2008-11-11 10:34:22

    编译通过...

    ├ 测试数据 01:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 02:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案错误...程序输出比正确答案长

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案错误... ├ 标准行输出

     ├ 错误行输出

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:50 有效耗时:0ms

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2008-11-08 15:27:06

    难得一次A

信息

ID
1369
难度
7
分类
动态规划 | LIS 点击显示
标签
递交数
3264
已通过
542
通过率
17%
被复制
3
上传者