博弈论 | ShanTianQi's Blog

nim游戏

Nim游戏是博弈论中最经典的模型（之一），它又有着十分简单的规则和无比优美的结论 Nim游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称ICG）。

例题：

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

输入格式
第一行包含整数 n。

第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。

输出格式
如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围
1≤n≤10^5^
1≤每堆石子数≤10^9^

输入样例：
2
2 3
输出样例：
Yes

import java.util.Scanner;

public class Main {
    static int N = (int)1e5 + 10;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int res = 0;

        while (n -- > 0){
            int x = sc.nextInt();
            res ^= x;
        }

        if (res == 1) System.out.println("Yes");
        else System.out.println("No");

        sc.close();
    }
}

台阶-Nim游戏

现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 ii 级台阶上有 ai 个石子(i≥1)。

两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

输入格式
第一行包含整数 n。

第二行包含 n 个整数，其中第 i 个整数表示第 i 级台阶上的石子数 ai。

输出格式
如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围
1≤n≤10^5^
1≤ai≤10^9^

输入样例：
3
2 1 3
输出样例：
Yes

import java.util.Scanner;

public class Main {
    static int n, res;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            int v = sc.nextInt();

            if ((i & 1) == 1) res ^= v;
        }

        if (res == 1) System.out.println("Yes");
        else System.out.println("No");

        sc.close();
    }
}

集合-Nim游戏

给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。

现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

输入格式
第一行包含整数 k，表示数字集合 SS 中数字的个数。

第二行包含 k 个整数，其中第 i 个整数表示数字集合 S 中的第 i 个数 si。

第三行包含整数 n。

第四行包含 n 个整数，其中第 i 个整数表示第 i 堆石子的数量 hi。

输出格式
如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围
1≤n,k≤100
1≤si,hi≤10000

输入样例：
2
2 5
3
2 4 7
输出样例：
Yes

Mex运算和SG函数

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    static int M = 110;
    static int N = (int)1e4 + 10;
    static int k;
    static int s[] = new int[M];//存放集合中的元素
    static int sg[] = new int[N];//存放某个数的SG函数的值

    public static void main(String[] args) {
        Arrays.fill(sg, - 1);
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();

        for (int i = 0; i < k; i++) {
            s[i] = sc.nextInt();
        }

        int n = sc.nextInt();
        int res = 0;

        while (n -- > 0){
            int x = sc.nextInt();
            res ^= sg(x);//直接异或sg函数的和 进行判断
        }

        System.out.println(res != 0 ? "Yes" : "No");

        sc.close();
    }

    private static int sg(int x){//递归
        if (sg[x] != -1) return sg[x];//若sg存在直接返回
        
        HashSet set = new HashSet<>();//每次递归重新创建一个set集合

        for (int i = 0; i < k; i++) {//枚举集合中每一个数 进行比较
            if (x >= s[i]) set.add(sg(x - s[i]));//递归往set集合中添加sg函数
        }

        for (int i = 0; i <= N; i++) {//在集合中找，最小的不存在的值
            if (!set.contains(i)) return sg[x] = i;//找到，保存，返回
        }

        return 0;
    }

}