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

我觉得解题报告说的算法都是O(n^2lgn)的，包括用hash的

Posted by frkstyc at 2006-03-27 12:48:13 on Problem 2780
In Reply To:n^2的算法居然算成了2000多MS Posted by:anotherh at 2006-03-27 11:08:38

Followed by:

我觉得理论上是n2的不过我写得很烦每次都要比较答案，然后每次其实都有个O（n）的清零，还有求gcd (64) xiaxia 2006-03-27 14:07:38
- 求gcd已经需要O(lgn)时间，你怎么O(n^2) (70) frkstyc 2006-03-27 14:16:16
  - 哦对了我把gcd忽略了 (0) xiaxia 2006-03-27 14:19:55
  - gcd不是本质上的，可以用乘法代替判相等。 (0) achilles 2006-03-27 15:48:22
    - 但这个lgn的因子你怎么免掉？ (0) frkstyc 2006-03-27 15:49:19
      - hash平均情况下是常数时间。这个logn是哪里来的？ (0) achilles 2006-03-27 16:08:40
        你的做法不是解题报告的做法了 (31) frkstyc 2006-03-27 16:23:06
        报告的做法明显分析错了复杂度。gcd的复杂度被忽略了。对于大量的运算来说，gcd很费时间的 (33) achilles 2006-03-27 16:43:34
        果然...按照1118的方法做，算个gcd就tle了 (0) qiqilrq 2007-11-12 07:53:44
    - 怎么乘法判相等阿，斜率分子乘分母，但是怎么计数阿？ (0) xiaxia 2006-03-27 16:48:08
    - 分母乘上一个大于N的数加上分母。不过这样似乎还是要gcd啊~？ (0) palmtenor 2006-03-27 18:04:58
      - 拿分子除分母然后乘上一个数取整当hash code (0) frkstyc 2006-03-27 18:10:02

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