Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

哈希+快排3秒多点过了

Posted by alpc07 at 2008-01-27 14:15:22 on Problem 2418
先构造一个好点的哈希函数,
我用的伪随机算法写的。
算出每个字符串的Hash值,保证他在100000以内,且重复的可能性比较小。
用100000的数组去累积吧~~
最后按字典序快排一次。

要用简单的Hash函数好处是不用最后排序,
缺点是没有那么大的空间,30位的话用那种不重复的Hash函数肯定不行,
所以我用随机算法保证可以均匀分布。(小概率)
堆积的话即用开放地址的方法解决。
最后按字典序快排一次即可出解,
我交了2次,(换了种子)
最好一次是3347MS,比最快的也就大一个数量级。
应该还可以优化,但既然过了,,我也就懒一下哈哈。

提供一种思路,供大家参考。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


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