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

看来这题有 k == a的数据，但没有 k == -a的数据，如果加一组这样的数据不知又有多少程序要由AC->TLE

Posted by windbells at 2006-03-08 22:29:39 on Problem 2201

Followed by:

怎么讲？ (0) sunmoonstar 2006-03-08 22:31:15
- frkstyc 讲的 “按key排序，在树的最右路经上找到合适的位置插入” 会TLE (0) windbells 2006-03-08 22:32:41
  - 我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
不好意思，这算法没问题，我自已搞错了 (0) windbells 2006-03-09 11:59:24

Post your reply here:

Home Page Go Back To top