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 |
题意 与 学习别人的一个思路 (牛人勿进)题目中给出的是残局, 比如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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator