题解

21 条题解

  • 1
    @ 2019-08-11 09:39:00

    %%% ljf czy fthl

  • 0
    @ 2014-07-17 20:26:14

    ###克鲁斯卡尔+*qsort*能A吧

  • 0
    @ 2013-11-01 10:30:20

    终于用克鲁斯卡尔A掉了...虽然提交了N次....
    关键在于多删边...如果有 (x1,y1)(x1,y2)(x2,y3)的话,若有(y1<y2<y3),教主证了(x1,y1)(x2,y3)可以不连边,然后加了这个优化之后就真的A了....ORZ....

  • 0
    @ 2010-03-12 18:47:30

    Orz 教主。。太硬了

  • 0
    @ 2009-11-06 20:05:54

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    Accepted 有效得分:100

    有效耗时:684ms

    orz教主的题都很不错啊,orz tky

  • 0
    @ 2009-11-06 08:59:21

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    总算过了

  • 0
    @ 2009-08-17 00:21:17

    可以用prim过掉,优化的思路就是根据教主的题解中的一些结论推广来的。

    写的第一个程序算法没问题,但是暴空间了。所以只好把链表都删掉,重新写了一半的代码。

    prim的复杂度可以降到O(nlogn)。而且常数是4。

    最后的时间:

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    如果用extended不用double第9个点会207错误,

  • 0
    @ 2009-07-29 18:35:46

    3次AC!!!要想搞清楚那个动规真是很难!!!!!解题报告里的f[i][j][0]是不连通的,f[i][j][1]是连通的,它正好写反了!!!!!(不过懂了这个DP就能很容易地看出来了)

    附上微缩DP代码(可读性很差):

    j:=1;

    for i:=1 to n do begin

    if i=1 then d:=sqrt(sqr(extended(x1-x2))+sqr(extended(y1[1]-y2[1])))

    else begin

    a:=c+y1[i]-y1;

    if f

  • 0
    @ 2010-03-16 22:57:50

    看了半天题解,终于AC了,原来不是Kruskal,是DP!

    后来我用Prim+配对堆也AC了……优化了半天常数……

  • 0
    @ 2008-10-31 23:26:50

    kruskal+并查集过不了,数据太强大了

  • 0
    @ 2008-10-29 18:15:58

    使用教主的KRUSKAL被卡住了。。

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    Unaccepted 有效得分:70 有效耗时:731ms

  • 0
    @ 2008-10-28 21:01:11

    我是大SB,每次都被师父的题虐死。

  • 0
    @ 2008-10-25 09:24:01

    我便的KRUSKAL为什么不能ac?

  • 0
    @ 2008-10-20 21:38:08

    我只是不知道有没可以AC的Kruskal

    毕竟nlogn和n的差距很小

    而且我也没太卡常数

    我60W卡的就是Kruskal

  • 0
    @ 2008-10-20 20:19:00

    克鲁斯卡尔,每一个点只需存与他上方的点的边,和他对面的两个点(如果Y轴有相同的只需要存一个)

  • 0
    @ 2008-10-20 17:37:45

    编了个Kruskal,限时2S过了,交这里才20....

  • 0
    @ 2008-10-20 14:36:29

    ……数据也太大了吧……

  • 0
    @ 2008-10-20 11:40:10

    教主的标程好强大...

  • 0
    @ 2008-10-19 16:53:57
    • -||不行了.
      裸Kruskal..无法用..

    教主我ORZ..

  • 0
    @ 2008-10-19 16:01:58

    ……………………dp

信息

ID
1466
难度
7
分类
动态规划 | 单调性DP 点击显示
标签
递交数
345
已通过
61
通过率
18%
上传者