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 |
哈希+快排3秒多点过了先构造一个好点的哈希函数, 我用的伪随机算法写的。 算出每个字符串的Hash值,保证他在100000以内,且重复的可能性比较小。 用100000的数组去累积吧~~ 最后按字典序快排一次。 要用简单的Hash函数好处是不用最后排序, 缺点是没有那么大的空间,30位的话用那种不重复的Hash函数肯定不行, 所以我用随机算法保证可以均匀分布。(小概率) 堆积的话即用开放地址的方法解决。 最后按字典序快排一次即可出解, 我交了2次,(换了种子) 最好一次是3347MS,比最快的也就大一个数量级。 应该还可以优化,但既然过了,,我也就懒一下哈哈。 提供一种思路,供大家参考。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator