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 only_xxp at 2011-10-27 12:31:06 on Problem 1143
题目中给出的是残局, 比如2 2 5, 就是还剩2个数--- 2和5. 其它的数都已经被划掉了。 现在如果选2, 就可以划掉2, 然后2和3配合可以划掉5, 下个人就没数可选了, 故2是win move。 选5的话就输了。 所以2 2 5的结果是2
同理, 2 2 3 , 是没结果的, 选2 或3 都是输


dfs的思路是, 从残局中选一个没有被划去的数, 根据这个数进行划去操作。然后对新形成的残局dfs, 如果还有可赢步骤,则这个数为输。反之同理
dfs的时候,用数组来存和计算会tle, 需要用位来优化一下
1)存储的时候, 比如2, 就用00000010来存, 3就用00000100来存, 就是用位来表示某一个数, 这样用一个数的位就可以存储某一个残局。比如 2 2 5就是 00010010
2)另外, 用一个数组来存放残局的结果, 相当于dp了。 因为对于初始的残局, 不同的取法会有共同的中间残局。 dfs开始的时候判断一下是否已经求过些残局, 求过就直接返回, 否则就计算之后再存起来

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