用博弈论的思想玩游戏（洛谷P3150题题解，Java语言描述）

前言

博弈论，博大精深啊~~ 这里就是一个简单博弈论的算法题，典型的入门级别，值得学习。

题目要求

P3150题目链接

分析

我们模拟一下胜负情况：

m=1时： pb不能分割，所以zs赢了。

m=2时： pb分割成1+1，对方拿走一份，必定是1。对于剩下的1，zs不能分割，pb赢了。

m=3时： pb分割成2+1，对方为了续命，只能剩下2，zs对2进行1+1的分割，此时情况回到逆向的m=2，所以zs赢了。

m=4时： pb有两种选择，3+1或者2+2。 3+1时，zs为了续命，只能剩下3，这是反向的m=3，pb赢了。 2+2时，zs只能剩下2，这是反向的m=2，zs就赢了。 但是pb先手，而且用最优策略，自然会选择3+1方案，就赢了。

m=5时： pb有两种选择，3+2或者4+1。 3+2时，zs选3就会输，选2就会赢。 4+1时，zs选1就输了，只能选4，然后他会为了胜利进行3+1方案，堵死pb获胜的可能。 所以pb不论作何选择，zs都有将其100%堵死的策略，zs必胜。

m=6时： pb有三种可能，3+3或者4+2或者5+1。 3+3时，zs只能选3，就是逆向的m=3，pb赢。 4+2时，zs选2就肯定赢，选4的话就能选3+1方案，封死pb获胜可能，这种情况下zs肯定能赢。 5+1时，zs不可能选1，因为会输，必然选5，选5的话，那就反过来了，pb肯定能赢。 所以，pb选择3+3或者5+1方案，避开4+2方案，即可战胜zs，pb有选择权，所以pb赢。

……

越往下分析越复杂，但是我们能发觉规律： 如果m为偶数, 那么先手赢(即pb), 如果m为奇数, 那么后手赢(即zs)。

继续分析： 我们不管先手怎么走，为了所谓“胜利的目标”也好，为了“续命的事实”也好， 只要他手里是奇数，为了胜利，都不得不拆成奇数+偶数。那么后手只要选择偶数，他就可以把这个数化成m = (m-1) + 1(后手的最优策略)，把奇数转移给先手。这样经过若干次转移之后, 后手手里一定会是2，然后2 = 1 + 1，后手就赢了。

所以，其实手里是奇数的人是没有胜算的，所以这个状态是必败态。而手里是偶数的人是有必胜的可能的，只有他才有最优策略而且只要他按照最优策略走，他一定会赢，因此这个状态是必胜态。这里我们认为每个人一定能作出对自己当前和全局最有利的决策，所以其实在一开始给出数值的一瞬间，胜负已定。

而理解这个博弈论问题的关键，就是拥有偶数的策略：控制偶数的一方每次减一，给对方两个奇数的选项，因而不论对方怎么切割这个奇数，最终一定会切成奇数+偶数，原先控制偶数的人再选偶数，就可以再次将偶数态(必胜态)转移过来，就一定能一步一步走向胜利。

有位dalao这样总结的这个问题： 其实这里的必败态（不能控制偶数的一方）从来没有最佳策略，博弈也不是双方的博弈，而是处在必胜态的那方和自己博弈。而这场博弈，由于绝顶聪明的前提，是必胜的，而我们要做的，只是找出谁有跟自己博弈的机会。

我觉得这位大佬说的特别对，理解很Nice，OrzOrz……

那代码就很简单啦，这里我简单的用了一下x&1，表示x%2，判断奇偶数用的。

AC代码（Java语言描述）

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        List list = new ArrayList();
        for (int i = 0; i