hdu 2999 Stone Game, Why are you always there? (sg函数,线性串取石子)

hdu2999题目链接

题意:有一串石子,给定一个集合S,每次只能拿连续x个石子,石子必须是在集合S中的数,问先手是否有必赢策略。需要注意石子的位置是不能变化的,也就是说如果一串连续的石子因为中间有石子被取走,那么这段石子就变成不连续的了,也就不能一次取走。

思路:一开始没有读懂题。需要特别强调的是。石子的位置是不能合并的。。

举个例子,如果我有5个石子,S={2},那么我取完一次剩下的情况是 {3,4,5}或者{1},{4,5}或者{1,2},{5}或者{1,2,3} 一共四种。

题意搞清楚以后就好做了。。类似于bomb game那道题。。我们仍然可以把取一次的操作拆分两个子过程,也就是两个区间。我们不关心区间具体的情况,只关心区间的长度。以及,取完只有一个区间的情况不需要特殊考虑,认为是长度为0就可以了,因为sg[0]为0,不影响答案。

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz