题解

61 条题解

  • 4
    @ 2016-11-30 12:11:57
    评测结果
    编译成功
    
    测试数据 #0: Accepted, time = 0 ms, mem = 1020 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1020 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1020 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1020 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1020 KiB, score = 10
    测试数据 #5: Accepted, time = 46 ms, mem = 1020 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 1020 KiB, score = 10
    测试数据 #7: Accepted, time = 31 ms, mem = 1024 KiB, score = 10
    测试数据 #8: Accepted, time = 31 ms, mem = 1020 KiB, score = 10
    测试数据 #9: Accepted, time = 31 ms, mem = 1020 KiB, score = 10
    Accepted, time = 154 ms, mem = 1024 KiB, score = 100
    代码
    #include <algorithm>
    #include <cstdio>
    using namespace std;
    int a[65536],h[65536],i,n;
    inline void dfs(int k,int l,int r) {
      h[k] = a[l];
      if (k<<1 > n) return;
      dfs((k<<1)+1,l+1,(l+r+1)>>1);
      dfs(k<<1,((l+r+1)>>1)+1,r);
    }
    int main() {
      scanf("%d",&n);
      for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
      sort(a+1,a+n+1);
      dfs(1,1,n);
      for (int i = 1;i <= n;i++) printf("%d ",h[i]);
      return 0;
    }
    
  • 1
    @ 2008-10-20 17:27:54

    其实,这题本身不是很难(谁不会建小根堆呢),但是那个所谓字典序却让人很纠结。于是我们想到:能不能做一个最小字典序的小根堆呢?明显的,我们用快排\堆排得到了这个堆,如:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

    但是对于一个最大字典序小根堆来说,,我们应该尽量让左子树大于右子数,于是我们得到的堆是这样的:

    1

    9 2

    13 10 6 3

    15 14 12 11 8 7 5 4

    也就是说,“左子堆中的任意数大于右子堆中的任意数,且该堆是一个小根堆”该定理适用于最大字典序小根堆中的每一个子堆。

    由定义我们就可以写出把一个有序数列变成最大字典序小根堆的procedure(虽然写得很傻,但还是贴出来:

    procedure deal(x,y,k:longint);{从deal(1,n)开始}

    var

    l:longint;

    begin

    if k>q then exit else{q:=round(ln(n+1)/ln(2))}

    inc(r[k]);

    b[k,r[k]]:=a[x];

    l:=(x+y)div 2;

    deal(l+1,y,k+1);

    deal(x+1,l,k+1);

    end;

    {得到的b:

    1

    9 2

    13 10 6 3

    15 14 12 11 8 7 5 4

  • 0
    @ 2021-11-26 12:51:40
    #include<bits/stdc++.h>//比赛尽量的别用万能头
    using namespace std;
    int a[65536],h[65536],i,n;
    inline void dfs(int k,int l,int r) {
      h[k] = a[l];
      if (k<<1 > n) return;
      dfs((k<<1)+1,l+1,(l+r+1)>>1);
      dfs(k<<1,((l+r+1)>>1)+1,r);
    }
    int main() {
      scanf("%d",&n);
      for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
      sort(a+1,a+n+1);
      dfs(1,1,n);
      for (int i = 1;i <= n;i++) printf("%d ",h[i]);
      return 0;
    }
    
  • 0
    @ 2013-03-24 11:46:23

    var a,h:array[0..65536] of longint;
    i,n :longint;
    procedure sort(l,r :longint);
    var i,j,m:longint;
    begin
    i:=l; j:=r; m:=a[(l+r)>>1];
    repeat
    while a[i]<m do inc(i);
    while a[j]>m do dec(j);
    if i<=j then begin
    a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];
    inc(i); dec(j);
    end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
    end;
    procedure put(k,l,r:longint);
    begin
    h[k]:=a[l];
    if k<<1>n then exit;
    put(k<<1+1,l+1,(l+r+1)>>1);
    put(k<<1,(l+r+1)>>1+1,r);
    end;
    begin
    readln(n);
    for i:=1 to n do read(a[i]);
    sort(1,n); put(1,1,n);
    for i:=1 to n do write(h[i],' ');
    end.

    上海红茶馆 via libjudge
    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 1144 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 1144 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1144 KiB, score = 10
    测试数据 #3: Accepted, time = 30 ms, mem = 1144 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 1144 KiB, score = 10
    测试数据 #5: Accepted, time = 152 ms, mem = 1144 KiB, score = 10
    测试数据 #6: Accepted, time = 212 ms, mem = 1144 KiB, score = 10
    测试数据 #7: Accepted, time = 208 ms, mem = 1144 KiB, score = 10
    测试数据 #8: Accepted, time = 210 ms, mem = 1144 KiB, score = 10
    测试数据 #9: Accepted, time = 210 ms, mem = 1144 KiB, score = 10
    Summary: Accepted, time = 1067 ms, mem = 1144 KiB, score = 100

  • 0
    @ 2009-11-08 07:27:58

    强烈鄙视VJ评测机.......

    虽然你们难,我也知道,

    但是这太让人无语.....

    n

  • 0
    @ 2009-08-29 14:35:34

    先快排再分治。。

    procedure done(top,l,r:longint);

    begin

    a[top]:=n[l];

    inc(l);

    if 2 * top < k then

    begin

    done(2*top,(l+r) div 2+1,r);

    done(2*top+1,l,(l+r) div 2);

    end;

    end;

  • 0
    @ 2009-08-20 16:13:10

    编译通过...

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

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

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

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

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

    ├ 测试数据 06:运行超时|无输出...

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

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

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

    ├ 测试数据 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
    @ 2009-08-05 18:24:28

    如此水题:简单秒杀

    编译通过...├ 测试数据 01:答案正确... 0ms├ 测试数据 02:答案正确... 0ms├ 测试数据 03:答案正确... 0ms├ 测试数据 04:答案正确... 0ms├ 测试数据 05:答案正确... 0ms├ 测试数据 06:答案正确... 0ms├ 测试数据 07:答案正确... 0ms├ 测试数据 08:答案正确... 0ms├ 测试数据 09:答案正确... 0ms├ 测试数据 10:答案正确... 0ms-------------------------Accepted 有效得分:100 有效耗时:0ms

    附核心程序:鼠标拖动即可

    procedure work(k:longint);begin if k>n then exit; inc(j); w[k]:=a[j]; work(2*k+1); work(2*k);end;

  • 0
    @ 2009-05-03 14:20:36

    编译通过...

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

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

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

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

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

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

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

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

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

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

    qsort+后序构造 ((具体实现类似于线段树的那种递归))

  • 0
    @ 2009-04-04 22:09:26

    qsort+后序构造(贪心)

  • 0
    @ 2009-03-15 21:00:43

    当我思考怎样快速找到某结点左子结点的个数时得走头无路想用暴力判断法时,发现原题一句话:为了简化题目,数据保证n=2^k-1,即保证最后的堆是一棵满二叉树。

  • 0
    @ 2008-12-16 21:22:20

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    通过   400人

    提交   1403次

    本来应该 是 400、1400 的…… 由于 急着 提交…… 结果 连 挂3次…… 第四次 才 过…… 5555555555555…………

  • 0
    @ 2008-11-13 22:20:38

    Dolphin 第8组超时,其他都0ms。Puppy就全0msAC了。

  • 0
    @ 2008-11-13 19:13:57

    0MS

    此题是我的第200题!

    celebrate!

  • 0
    @ 2008-11-12 13:06:13

    编译通过...

    ├ 测试数据 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-10 10:36:28

    vivid puppy 好

  • 0
    @ 2008-11-08 10:07:11

    我恨Dolphin……

    桶排序,10^5的算法超时了……

  • 0
    @ 2008-11-02 16:33:45

    PROGRAM P1469_Orz;

    VAR

    a,b:array[0..200000] of longint;

    n,i,j:longint;

    PROCEDURE egg(k:longint);

    begin

    b[k]:=a[j];

    inc(j);

    if 2*k>n then exit;

    egg(2*k+1);

    egg(2*k);

    end;

    BEGIN

    readln(n);

    for i:=1 to n do

    read(a[i]);

    j:=1;

    qqsort(1,n);

    egg(1);

    for i:=1 to n-1 do

    write(b[i],' ');

    writeln(b[n]);

    END.

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    为什么...请教大牛了...

  • 0
    @ 2008-11-01 20:42:07

    编译通过...

    ├ 测试数据 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-10-29 18:59:47

    首先通过任意方法排好序(不降)

    a1 (a2 a3 .... ak) (ak+1 .... an)

    < < < ....

    然后每次按这样的方式划分,把第一个作为根节点,两个括号作为右左子树。

    这样建起一颗树(具体实现类似于线段树的那种递归)。

    最后按层顺次输出即可。

信息

ID
1469
难度
4
分类
其他 | 排序 点击显示
标签
递交数
522
已通过
214
通过率
41%
被复制
3
上传者