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

大家有什么好办法，我只想出N平方的，跑了500多MS，不满意

Posted by yesiam at 2005-02-06 11:39:04 on Problem 2182

Followed by:

某些人的30Ms是怎么干出来的 (0) yesiam 2005-02-07 22:36:57
- 大家不吝赐教啊 (0) yesiam 2005-02-09 13:51:29
- 估计是有O(n)的办法 (0) sothink 2005-02-09 15:57:36
  - nlgn (0) hawk 2005-02-09 18:58:27
    - nlgn怎么做啊 (0) yesiam 2005-02-10 16:48:40
    - Re:nlgn (12) WZPWZPWZP 2005-05-09 22:39:59
没做过这个题目，看了一下，感觉线段树可以做到nlgn，可能还能简化一下 (0) hawk 2005-05-09 22:57:32
- 线段树是做数据用的吧？我想到一个用bst的，不过数据bt的话好像会退化到O(n^2) (0) frkstyc 2005-05-10 12:28:30
  - 也可以用吧，从后往前算 (17) hawk 2005-05-10 12:41:03
  - 果然退化，889ms (0) frkstyc 2005-05-10 12:50:34
    - 优化到尽头+gcc编译也只能砍去3/4的时间 (0) frkstyc 2005-05-10 14:19:40
- 刚刚写了一个线段树，确实30msAC...... (0) TN 2005-05-10 13:52:04
  - Re:刚刚写了一个线段树，确实30msAC...... (9) dxm 2005-05-10 14:15:09
    - 大概思路是这样的 (58) TN 2005-05-10 14:37:36
      - Re:大概思路是这样的 (93) frkstyc 2005-05-10 14:43:48
        出现多少和未出现多少是等价的阿，一个减法操作而以 (31) hawk 2005-05-10 14:52:23
        刚才没想清楚，找第Ai+1个的时候想到线性查找上去了 (0) frkstyc 2005-05-10 14:53:32
        我似乎就是线形查找的构造.......而且似乎我这样都没法用线段树.....里面有程序~ (369) palmtenor 2005-05-10 14:58:30
        ft......你怎么不上课？ (405) TN 2005-05-10 14:59:21
        本学期第一次去上计算机课~ (0) palmtenor 2005-05-10 15:00:27
        ft，这么简单，怪不得程序暴短 (405) frkstyc 2005-05-10 14:59:52
        我的和这个类似。233MS。 (0) ciciatc 2005-05-10 15:30:05
        和gcc编译的bst时间一样 (0) frkstyc 2005-05-10 15:32:12
        ft~我刚才太死心眼了，想出来线段树了 (405) palmtenor 2005-05-10 15:09:29
      - 哈，谢谢哈，我就是看了你这个思路用线段树A掉的哈 (66) BrainDeveloper 2009-09-13 21:22:32
  - segment tree is nice...15ms (0) frkstyc 2005-05-10 15:55:05
    - tn要多做一些peephole optimization才能快啊 (0) frkstyc 2005-05-10 15:58:55
      - ft，优化不是要搞到ce吧？ (0) frkstyc 2005-05-10 16:00:06
        还要wa+re？！ (0) frkstyc 2005-05-10 16:01:32
        ^_^ (0) TN 2005-05-10 16:02:55
      - peephole是什么东西？ (0) TN 2005-05-10 16:02:06
        我也不知道什么意思，从gcc的编译选项里面学来的词，peephole opt就是那些零星杂碎的优化 (0) frkstyc 2005-05-10 16:03:08
        比如Checker Chalenge,Shaping Region,Humble Number,Inflate我都是靠代码优化才适应了USACO的新时限~~~~ (0) palmtenor 2005-05-10 18:16:53
        Re:peephole是什么东西？ (0) ktmtwm 2008-07-23 16:55:15
      - 我再也不想干这种事情了~自从USACO把时间改到1s，我就干了无数这样的事情~~ (0) palmtenor 2005-05-10 18:15:52
Re:大家有什么好办法，我只想出N平方的，跑了500多MS，不满意 (27) denghongchao 2009-08-05 16:11:36
O(nlogn)树状数组可以0msAC...... (107) ylllxw08 2010-08-28 23:04:40

Post your reply here:

Home Page Go Back To top