Basic game theory problems of competitive programming

2020/08/18

引入: NIM 博弈

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

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

输入格式:

第一行包含整数 \(n\)。

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

输出格式:

如果先手方必胜,则输出 \(“Yes”\)。否则,输出 \(“No”\)。

数据范围:

\(1≤ n ≤10^5\),

\(1 ≤\) 每堆石子数 \(≤ 10^9\)

输入样例:

2
2 3

输出样例:

Yes

这是最基础的 Nim 游戏,也是博弈论的入门问题,接下来会引出许多 Nim 游戏的变种以及拓展。

代码:

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int n;

int main() {
    cin >> n;
    int x;
    ll res = 0;
    while (n--) {
        cin >> x;
        res ^= x;
    }
    if (res == 0) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}

台阶 NIM 游戏:

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

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

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

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

输入格式:

第一行包含整数 \(n\)。第二行包含 \(n\) 个整数,其中第 \(i\) 个整数表示第 \(i\) 级台阶上的石子数\(a_i\)。

输出格式:

如果先手方必胜,则输出 \(“Yes”\)。否则,输出\(“No”\)。

数据范围

\(1 ≤ n ≤ 10^5\),

\(1 ≤ a_i ≤ 10^9\)

输入样例:

3
2 1 3

输出样例:

Yes

此时我们需要将奇数台阶看做一个经典的 Nim 游戏,如果先手时奇数台阶上的值的异或值为 \(0\) ,则先手必败,反之必胜。

证明:

先手时,如果奇数台阶异或非 \(0\) ,根据经典 \(Nim\) 游戏,先手总有一种方式使奇数台阶异或为 \(0\),于是先手留了技术台阶异或为 \(0\) 的状态给后手 于是轮到后手:

①当后手移动偶数台阶上的石子时,先手只需将对手移动的石子继续移到下一个台阶,这样奇数台阶的石子相当于没变,于是留给后手的又是奇数台阶异或为 \(0\) 的状态。

②当后手移动奇数台阶上的石子时,留给先手的奇数台阶异或非 \(0\),根据经典 \(Nim\) 游戏,先手总能找出一种方案使奇数台阶异或为 \(0\)。

因此无论后手如何移动,先手总能通过操作把奇数异或为 \(0\) 的情况留给后手,当奇数台阶全为 \(0\) 时,只留下偶数台阶上有石子。 (核心就是:先手总是把奇数台阶异或为 \(0\) 的状态留给对面,即总是将必败态交给对面)

因为偶数台阶上的石子要想移动到地面,必然需要经过偶数次移动,又因为奇数台阶全 \(0\) 的情况是留给后手的,因此先手总是可以将石子移动到地面, 当将最后一个(堆)石子移动到地面时,后手无法操作,即后手失败。

因此如果先手时奇数台阶上的值的异或值为非 \(0\),则先手必胜,反之必败。

代码:

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int n;

int main() {
    cin >> n;
    int x;
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        if (i & 1) res ^= x;
    }
    if (res == 0) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}

集合 NIM 游戏:

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

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

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

输入格式:

第一行包含整数 \(k\),表示数字集合 \(S\) 中数字的个数。

第二行包含 \(k\) 个整数,其中第 \(i\) 个整数表示数字集合 \(S\) 中的第 \(i\)个数 \(s_i\)。第三行包含整数 \(n\)。

第四行包含 \(n\) 个整数,其中第 \(i\) 个整数表示第 \(i\) 堆石子的数量 \(h_i\)。

输出格式:

如果先手方必胜,则输出 \(“Yes”\)。否则,输出 \(“No”\)。

数据范围

\(1 ≤ n,k ≤ 100\),

\(1 ≤ s_i, h_i ≤ 10000\)

输入样例:

2
2 5
3
2 4 7

输出样例:

Yes

思路:

每一堆石子都可以看为一个有向图,然后求初始节点的 \(SG\) 函数, 每一个节点的出边对应能取的所有状态。

代码:

#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <cstring>
using namespace std;
const int N = 110, M = 10010;

int n, m;
int s[N], f[M];  //s表示集合的元素 ,f 是sg函数值

int sg(int x) {
    if (f[x] != -1) return f[x]; //记忆化 被算过就直接返回
    unordered_set<int> S; //储存所有可以到达的局面
    for (int i = 0; i < m; i++) {
        int sum = s[i];
        if (x >= sum) S.insert(sg(x - sum));
    }

    for (int i = 0; ; i++) // 求当前节点的mex函数值 最小的不包含的非负整数
        if (!S.count(i))
            return f[x] = i;
}

int main() {
    cin >> m;
    for (int i = 0; i < m; i++) cin >> s[i];
    cin >> n;
    memset(f, -1, sizeof f);
    int res = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        res ^= sg(x);  //求出每一个有向图的sg函数 然后全部异或
    }
    if (res == 0) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}

拆分 NIM 游戏:

给定 \(n\) 堆石子,两位玩家轮流操作,每次操作可以取走其中的一堆石子,然后放入两堆规模更小的石子(新堆规模可以为\(0\),且两个新堆的石子总数可以大于取走的那堆石子数),最后无法进行操作的人视为失败。

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

输入格式:

第一行包含整数 \(n\)。

第二行包含 \(n\) 个整数,其中第 \(i\) 个整数表示第 \(i\) 堆石子的数量 \(a_i\)。

输出格式:

如果先手方必胜,则输出 \(“Yes”\)。否则,输出 \(“No”\)。

数据范围:

\(1 ≤ n, a_i ≤ 100\)

输入样例:

2
2 3

输出样例:

Yes

思路:

石子堆的最大值在减小,所以博弈一定会结束,每堆石子看作有向图 然后全部求 \(SG\) 函数。

代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
using namespace std;

const int N = 110;
int f[N];

int sg(int x) {
    if (f[x] != -1) return f[x];

    unordered_set<int> S;

    //枚举可以到达的状态
    for (int i = 0; i < x; i++) //第一堆
        for (int j = 0; j <= i; j++) //第二堆
            S.insert(sg(i) ^ sg(j));
    //mex 函数
    for (int i = 0; ; i++)
        if (!S.count(i))
            return f[x] = i;

}

int main() {
    int n;
    cin >> n;
    int res = 0;
    memset(f, -1, sizeof f);
    while (n --) {
        int x;
        cin >> x;
        res ^= sg(x);
    }
    if (res == 0) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}

拓展:博弈论与 DP

题目描述:

\(Alice\) 和 \(Bob\) 两个好朋友又开始玩取石子了。

游戏开始时,有 \(N\) 堆石子排成一排,然后他们轮流操作(\(Alice\) 先手),每次操作时从下面的规则中任选一个:

1.从某堆石子中取走一个;

2.合并任意两堆石子。

不能操作的人输。

\(Alice\) 想知道,她是否能有必胜策略。

输入格式:

第一行输入 \(T\),表示数据组数。

对于每组测试数据,第一行读入 \(N\);

接下来 \(N\) 个正整数 \(a_1,a_2,⋯,a_N\) ,表示每堆石子的数量。

输出格式:

对于每组测试数据,输出一行。

输出 \(YES\) 表示 \(Alice\) 有必胜策略,输出 \(NO\) 表示 \(Alice\) 没有必胜策略。

数据范围:

\(1 ≤ T ≤ 100\),

\(1 ≤ N ≤ 50\),

\(1 ≤ a_i ≤ 1000\)

输入样例:

3
3
1 1 2
2
3 4
3
2 3 5

输出样例:

YES
NO
NO

代码以及思路:

#include <bits/stdc++.h>
using namespace std;

//f[a][b]为状态 a表示一个石子独立成堆的数量
// b表示大于一个石子的堆数+这些石子的总数 - 1
//b中不包含单个成堆的石子

const int N = 55, M = 50050;
int f[N][M];

int dp(int a, int b) {
    int &v = f[a][b];
    if (v != -1)  return v;
    if (!a) return v = b % 2; //所有堆都大于一个石子 判断奇偶性即可

    if (b == 1) return dp(a + 1, 0); //此时b只有一个独立石子 那就直接归到a中

    if (a && !dp(a - 1, b)) return v = 1;  //a中取一个
    if (b && !dp(a, b - 1)) return v = 1; //b中取一个 或者合并b中2个 能到这一个if说明b中至少2个石子
    if (a >= 2 && !dp(a - 2, b + (b ? 3 : 2))) return v = 1; //合并a中的2个
    if (a && b && !dp(a - 1, b + 1)) return v = 1; //合并a中的一个和b中的一个

    return v = 0;
}

int main() {
    memset(f, -1, sizeof f);
    int T;
    scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        int a = 0, b = 0;
        for (int i = 0; i < n; i++) {
            int x;
            scanf("%d", &x);
            if (x == 1) a ++;
            else b += b ? x + 1 : x;
        }
        if (dp(a, b)) puts("YES");
        else puts("NO");
    }
}

ZJOI2009《取石子》 区间 DP

题目描述:

在研究过 \(Nim\) 游戏及各种变种之后,\(Orez\) 又发现了一种全新的取石子游戏,这个游戏是这样的:

有 \(n\) 堆石子,将这 \(n\) 堆石子摆成一排。

游戏由两个人进行,两人轮流操作,每次操作者都可以从最左或最右的一堆中取出若干颗石子,可以将那一堆全部取掉,但不能不取,不能操作的人就输了。

\(Orez\) 问:对于任意给出的一个初始局面,是否存在先手必胜策略。

输入格式:

第一行为一个整数 \(T\),表示有 \(T\) 组测试数据。

对于每组测试数据,第一行为一个整数 \(n\),表示有 \(n\) 堆石子,第二行为 \(n\) 个整数 \(a_i\) ,依次表示每堆石子的数目。

输出格式:

对于每组测试数据仅输出一个整数 \(0\) 或 \(1\),占一行。

其中 \(1\) 表示有先手必胜策略,\(0\) 表示没有。

数据范围:

\(1 ≤ T ≤ 10\),

\(1 ≤ n ≤ 1000\),

\(1 ≤ a_i ≤ 10^9\)

输入样例:

1
4
3 1 9 4

输出样例:

0

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int n;
int a[N], l[N][N], r[N][N];

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        for (int len = 1; len <= n; len ++) //区间长度
            for (int i = 1; i + len - 1 <= n; i++) { //左端点
                int j = i + len - 1;
                if (len == 1) l[i][j] = r[i][j] = a[i];
                else {
                    int L = l[i][j - 1], R = r[i][j - 1], X = a[j];
                    if (R == X) l[i][j] = 0;
                    else if (X < L && X < R ||  X > L && X > R) l[i][j] = X;
                    else if (L > R) l[i][j] = X - 1;
                    else l[i][j] = X + 1;

                    L = l[i + 1][j], R = r[i + 1][j], X = a[i];
                    if (L == X) r[i][j] = 0;
                    else if (X < L && X < R || X > L && X > R) r[i][j] = X;
                    else if (R > X) r[i][j] = X - 1;
                    else r[i][j] = X + 1;
                }
            }
        if (n == 1) puts("1");
        else printf("%d\n", l[2][n] != a[1]);
    }
    return 0;
}