BZOJ3895 取石子

这题思路不错。

首先考虑对于一个 >1 的堆,如果合并他对先手有利,那么这堆石子在取完之前一定会被先手合并。同理如果对后手有利也是。

既然合并这个动作要不就是对先手有利要么就是对后手有利,那肯定这堆石子最后会被合并。

并且在取完之前,合并这个动作无论在何时发生,都等同于在对这堆石子操作时的前两步内发生。

那么我们就可以把充裕堆 ( 大小 >1 的堆 ) 先提前合并了,然后在 DAG 游戏图上记搜 \mathrm{SG} 值。

操作分为几种:

  • 拿走一个孤单堆
  • 拿走充裕堆的一个石子
  • 把一个孤单堆合并到充裕堆内
  • 把两个孤单堆合并,成为充裕堆的一部分

然后就写个代码就好了。复杂度大概是 O(T \cdot \sum{a_i}) 的。

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据