当前位置: 代码迷 >> 综合 >> CodeForces658 Sequential Nim(博弈论)
  详细解决方案

CodeForces658 Sequential Nim(博弈论)

热度:57   发布时间:2024-01-18 18:31:01.0

 

题目大意:

 选石堆的时候面临一下状况:

1.当前石堆只有一个石子,那么必须选择抓完,此时,交换先后手。

2.当前石堆的石子数大于一个,那么采取的策略是拿到只剩下一个,强制对方拿走剩下的一个,先后手顺序不变。

由于是1号先拿,

因此,当其按次序遇到石堆的时候,如果当前石堆只有1个,那必须会交换先后手。

而面对大于1的石堆的时候,既可以选择先手顺序也可以选择后手顺序,这个非常重要!因为可以随意选择先后手顺序即表示包括了所有的可能次序(即必赢态)。

 

题目解决:

在遇到第一个大于1的A[i]前,记录遇到的1的次数ANS

根据1的个数即可判断输赢。

当ANS为奇数且ANS!=N的情况下由于第一次碰到大于1的数字是2号选择,因此是2

当ANS为奇数且ANS==N的情况下由于最后的数字是1号先手进行选择,因此是1

其他两种情况对应判断即可。

 

 

  相关解决方案