题解 POJ 2505 A multiplication game 组合游戏

题目链接
题意: 有一个数p=1,甲乙两人轮流操作,每次可以把p乘2-9中的一个数,给定一个n,当一个人操作后p>=n,那么这个人赢,问先手是否必胜。

  • 必胜状态:存在一种走法走到一个必败状态。
  • 必败状态:后继状态都为必胜状态。

我们可以知道>=n的数都为必败状态,可以转移到>=n的最小的数为n/9(上取整),所以 n/9~n-1都为必胜态,同理n/9/2(都为上取整)为最小的必须转移到n/9-n-1(必胜状态)的状态,所以n/9/2~n/9-1为必败态,于是就可以这样推到1,看一下1是必胜态还是必败态输出即可。

ps. a/b(上取整)可以写为 (a-1)/b+1(整除)。方便运算。

代码:https://gist.github.com/zrt/858e1f5558e93ca20d1d

评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框