Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

frkstyc 讲的 “按key排序，在树的最右路经上找到合适的位置插入” 会TLE

Posted by windbells at 2006-03-08 22:32:41 on Problem 2201
In Reply To:怎么讲？ Posted by:sunmoonstar at 2006-03-08 22:31:15

Followed by:

我ac了…… (0) frkstyc 2006-03-08 22:37:13
- ac 也可能有问题 (0) sunmoonstar 2006-03-08 22:38:26
  - 不过我属于没有能力ac的 (0) sunmoonstar 2006-03-08 22:39:00
- 我说的是如果加一组 k == -a的数据，则会TLE (0) windbells 2006-03-08 22:38:34
  - 按TReap做是一种退化，这是另一种类似的退化 (0) windbells 2006-03-08 22:39:51
    - 但是这个构造算法是不存在退化情况的…… (0) frkstyc 2006-03-08 22:43:01
      - 可能没有完全理解那句话，但我AC的程序在 k == -a这样的数据下肯定会TLE的 (0) windbells 2006-03-08 22:47:17
        不会吧，插入之后你要把原来的最右路经放到左边去的呵，这样最右路经短了一大截 (0) frkstyc 2006-03-08 23:02:38
        记录最右链最下面一个点，加点时接到这个点的右孩子指针上，如果不符合BST性质就左旋转 (0) zhougelin 2006-03-09 15:08:13
  - btw, 啥时候 world final? ^_^ (0) sunmoonstar 2006-03-08 22:41:13
    - Mar 9-13 (0) windbells 2006-03-08 22:47:48
      - sorry APR 9-13 (0) windbells 2006-03-08 22:48:20
        thx, 加油啊 (0) sunmoonstar 2006-03-08 22:51:23
这样的算法除了排序是O(n)的……可以用potential function证明的…… (0) frkstyc 2006-03-08 22:37:56

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator