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

这个题这样做都超时了，我就有点纳闷了。。。。。

Posted by faen at 2005-05-20 15:12:12 on Problem 2104

就是用标准的partion，分治法。对于每一组数据，是O（logn）的。
我记得算法书上证明过，这是最快的方法了阿？？
那些过了的大牛，把你们的算法说说呗

Followed by:

可能java输入太慢了，用c++试试看 (87) hawk 2005-05-20 15:15:52
- 或者先改为jdk1.4的输入方法，好像比scanner快一点 (0) hawk 2005-05-20 15:19:40
这样做是真的不行，和java没有关系，这种D&C是期望是O(n)的，不是O(logn)的 (87) frkstyc 2005-05-20 15:30:58
一种非常BT的方法就是线段树嵌套平衡树，这样一次操作是(logn)^2的。。。 (87) js05 2005-05-20 16:04:36
- 这个题也拿去折腾别人吧？ (0) frkstyc 2005-05-20 16:08:03
  - 我还没有AC，怎么好意思搞别人呢。。。我搞了一个数学公式编辑器的题，呵呵。。。 (0) js05 2005-05-20 16:35:23
    - 而且DISCUSS里说的那个比这个题还变态的题，就是我们省的ZZY搞的。。。 (0) js05 2005-05-20 16:36:34
      - zhuzeyuan? (0) frkstyc 2005-05-20 16:40:39
        对了。。。 (0) js05 2005-05-20 16:41:38
    - 暴烦的题目，现在我看见做表达式的就没心情做了 (0) frkstyc 2005-05-20 16:41:44
      - 哈哈，我的标程写了25K。。。 (0) js05 2005-05-20 16:46:36
        有1000+行。。。 (0) js05 2005-05-20 16:47:06
        FT，OI怎么会搞这么委琐的题呢。。。 (0) js05 2005-05-20 16:48:24
        等比赛完了，一定要让HAWK放到题库里面。。。 (0) js05 2005-05-20 16:54:17
        我也正要出一道题呢，一个课的作业 (0) frkstyc 2005-05-20 19:39:31
        作业就是出题啊？表达式的题我见过最强的就是CTSC2004的math，当时国家集训队所有人得分加起来还是0。。。 (0) js05 2005-05-20 19:48:11
        搞复杂了都不会做就没意义了，要不下回干脆要他们现场写操作系统算了 (0) frkstyc 2005-05-20 19:51:52
        应该给足够的时间都能AC的。。。 (62) js05 2005-05-20 19:55:54
        哪有原题，看一下什么叫bt (70) frkstyc 2005-05-20 19:56:52
        搞给邮箱，偶发给你。。。 (0) js05 2005-05-20 19:59:00
        what's"搞给"? (0) frkstyc 2005-05-20 20:00:54
        FT，你的邮箱是什么，我发到你邮箱里好了，顺便把测试数据也发给你。。。 (0) js05 2005-05-20 20:02:22
        ft,我的info里面不是写着么 (0) frkstyc 2005-05-20 20:03:39
        请查收。。。 (0) js05 2005-05-20 20:08:50
        got it, thx! (0) frkstyc 2005-05-20 20:09:22
        CTSC2004的题都很BT (91) js05 2005-05-20 20:22:34
- 好象还要乘一个log(maxlongint)，要想办法不要TLE了。。。 (0) js05 2005-05-20 19:39:55
- 这个题的值是固定的,所以只要预处理排好序,就没必要用平衡树了. (0) Jet407 2005-07-31 16:34:29
呵呵，没想到这么多大牛关注。。。 (87) faen 2005-05-20 17:47:31
- 话题早就跑了 (0) frkstyc 2005-05-20 19:37:09
  - 这题您是怎么搞掉的？ (0) js05 2005-05-20 19:41:01
    - 做index，对index排序，O(n)的统计，总共O(mn) (0) frkstyc 2005-05-20 19:42:49
      - Re:做index，对index排序，O(n)的统计，总共O(mn) (25) Birdsong 2005-07-25 16:41:48
        10s左右 (29) frkstyc 2005-07-25 16:43:32
        Re:10s左右 (10) Birdsong 2005-07-25 16:44:19
        我TLE了还告诉你时间干嘛 (14) frkstyc 2005-07-25 16:44:51
        要是 (0) frkstyc 2005-07-25 16:44:57
        Re:我TLE了还告诉你时间干嘛 (36) Birdsong 2005-07-25 16:45:45
        老早就不会写qsort了 (42) frkstyc 2005-07-25 16:46:43
        Re:老早就不会写qsort了 (13) Birdsong 2005-07-25 16:47:17
      - 我按你的算法写的，c++case超时，g++11s过。再提交，case超时。再提交，又过。汗。 (0) tengshengbo 2005-08-07 11:02:18
        疑似硬搞。。。 (0) sunmoonstar_love 2005-08-07 11:48:15
        有好方法么？ (0) sunmoonstar_love 2005-08-07 11:48:28
        当时我看了某人的程序也是这样一下AC一下TLE，他的排序是关键字的index一起排的，难道你试？ (0) frkstyc 2005-08-07 11:50:11
        暴力+优化，当数组长度小于 200， qsort（）比较慢，而且在qsort() (0) sunmoonstar_love 2005-08-07 11:58:22
        时也加优化 (0) sunmoonstar_love 2005-08-07 11:58:40
        自省排序，够快么？ (0) sunmoonstar_love 2005-08-07 12:00:16
        排序的时候只对index排，关键字就不要动了，数据移动需要时间的 (0) frkstyc 2005-08-07 12:00:03
        Re:排序的时候只对index排，关键字就不要动了，数据移动需要时间的 (19) DS0600548075 2006-11-18 10:40:04

Post your reply here:

Home Page Go Back To top