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

题后小结

Posted by cmonkey at 2012-01-26 20:25:36 on Problem 3349
求是否有同构序列
两种做法
1.对一个序列将其拆成12个同构序列,再存到hash表里
2.只存这一个序列,判重时再考虑同构

方法1会将数据扩大12倍,每加入一个序列要经过hash,判重等过程
方法2对hash函数要求同构的序列hash值相同
反正我方法1写TLE了,用的对v[i]*i依次异或,最后模100007,估计是加序列的过程消耗太大
方法2000MS+才过...用的对v[i]依次异或,最后模100007
(val[0] + val[2] + val[4]) & (val[1] + val[3] + val[5])这种确实很巧啊,满足同构的能相同
但在我的程序里跑了还慢100MS...
不知道哪里写慢了...

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