XCPC wiki - 博弈论

博弈论

• 是经济学的一个分支；
• 主要研究具有竞争或对抗性质的对象在一定规则下的行为；
• 考虑个体中的预测行为和实际行为，并研究其优化策略；
• 通俗地讲，主要研究的是在一个游戏中进行游戏的多位玩家的策略。

公平组合游戏（ICG）

• 二人参与，轮流决策，每次可以在有限的合法决策集合中选择一种进行操作，双方均知道游戏的完整信息；
• 在某一确定状态做出的决策集合只与状态有关，与玩家、之前的操作等任何因素都无关；
• 如果轮到某位玩家的回合时合法决策集合为空（即无法进行操作），该名玩家负。游戏一定会在有限步数之后以非平局结束；
• 大部分棋类游戏都是非公平组合游戏：国际象棋，五子棋等，因为双方都无法使用对方的棋子。

博弈图

• 给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
• 任何一个 ICG 游戏都可以转化为有向图游戏：把每个状态视为一个节点，向它的后继状态连边，转化为有向图游戏，也称绘制了它的博弈状态图（简称博弈图或者游戏图）。

先手必胜和先手必败

• 先手必胜状态（$N$-position，其中$N$ 代表 Next）：先手行动以后，可以让剩余的状态变成必败状态留给对手（下一步是对手（后手）的局面）；
• 先手必败状态（$P$-position，其中$P$ 代表 Previous ）：不管怎么操作都达不到必败状态，换句话说，如果无论怎么行动都只能达到一个先手必胜状态留给对手，那么对手（后手）必胜，先手必败；
• 简化一下：$N$ 可以到达$P$，$P$ 只能到达$N$（必胜可以到达必败，必败只能到达必胜）。

更严谨的定义

1. 无法进行任何移动的局面（也就是 terminal position）是$P$-position；
2. 可以移动到$P$-position 的局面是$N$-position；（玩家可以通过操作移动到$P$，此时对手必败，即己方必胜）
3. 所有移动都导致$N$-position 的局面是$P$-position。（对手无论如何都必胜，即己方必败）。

按照以上定义，我们就可以在绘出博弈图的情况下进行拓扑排序，很明显有递归的算法按照定义判断出所有状态的性质。

SG函数

• $\operatorname{mex}$ 运算：设$S$表示一个非负整数集合。定义为求出不属于集合$S$的最小非负整数的运算；
• 定义游戏终点的 SG 函数值为 0；
• 对于给定的博弈图，定义每个点的 SG 函数为：
  $SG(x) = \operatorname{mex} \lbrace SG(x') \mid x \neq a \wedge a \in G \wedge t \in M \wedge x' \in T \rbrace$

Nim Game

• 桌子上有$N$ 堆石子$a_i$，游戏者轮流取石子。每次只能从一堆中取出任意数目的石子，但不能不取。取走最后一个石子者获胜。
• 结论：
  • 定义 Nim 和为$a_0 \oplus a_1 \oplus a_2 \oplus ... \oplus a_m$，
  • 当且仅当 Nim 和为 0 的时候该状态为先手必败。

证明：

1.没有后继状态的状态为必败状态

• 没有后继状态的状态（P-position）只有一个，即全 0 局面，此时 Nim 和为 0。

2.对于 Nim 和不为 0的局面，一定存在某种移动使得 Nim 和为 0（必胜状态能到达一个必败状态）

• 假设 Nim 和不为 0，若进行一次操作取走第$i$ 堆石子使得$a_i$ 变为$a_i'$ 时 Nim 和为 0，则显然$a_i' = a_i \oplus k$。
• 证明一定存在这种操作即可：
  • 设$k$ 在二进制下最高位的 1 在第$x$ 位，则一定有奇数个$a_i$ 的二进制下在$x$ 位为 1；
  • 因此$a_i \oplus k = a_i' < a_i$。我们可以在这堆$a_i$ 中拿走石子使它变为$a_i'$；
  • 剩下的 Nim 和为$a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_i' \oplus a_{i+1} \oplus \ldots \oplus a_n = 0$。

3.对于 Nim 和为 0的场面，一定不存在某种移动使得 Nim 和为 0（必败状态不能到达任何一个必败状态）

• 当前状态 Nim 和为 0，我们仅需证明不管怎么拿 Nim 和都不会为 0然后证明一定存在这种操作即可，使用反证法：
  • 假设我们从$a_i$ 拿走若干石子变为$a_i'$ 使得 Nim 和变为 0；
  • 则说明存在$a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_i' \oplus a_{i+1} \oplus \ldots \oplus a_n = 0$；
  • 但我们知道当前状态下$a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_i \oplus a_{i+1} \oplus \ldots \oplus a_n = 0$；
  • 两式异或起来得出$a_i = a_i'$ 显然是一个不合法的移动，不存在这种走法。

结论：

• 故 Nim 和不为 0 是先手必胜状态，Nim 和为 0 是先手必败状态。

回到SG函数

• 特别地，整个图$G$ 的 SG 函数值被定义为起点$s$ 的 SG 函数值。
• 仔细回忆必胜态和必败态之间的转移：当一个状态的后继状态全都是必胜态时，这个状态就是必败态，如果后继状态至少有一个必败态，那么这个状态就是必胜态。
• 在SG 函数中这也得到了很好的体现：当一个状态的后继状态的SG函数值中至少有一个 0时，这个状态的SG函数值肯定不为 0，如果没有 0，那么这个状态的 SG 函数值肯定为 0。
• 似乎只需要用一个bool数组来记录必胜与必败局面就可以了……？

SG定理

• 一个游戏的 SG 函数值等于其子游戏的 SG 函数值的 Nim 和

Nim游戏拓展-Anti-Nim game

• 有两个绝顶聪明的人玩取石子游戏，假设有$n$ 堆石子，每个人可以轮流选择某一堆然后从中拿走任意数量的石子（不能为0），取走最后一颗石子的一方失败，先手还是后手胜利？
• 注意：输赢判断反过来，但是结论并不是直接反过来就可以套用的。
• 结论：先手必胜只有两种情况：
  1. 所有堆的石子数都为$0$ 并且所有堆石子数异或和为 0
  2. 存在一堆石子数大于$0$ 并且所有堆石子数异或和不为 0

Nim游戏拓展-Nim-k

• 有两个绝顶聪明的人玩取石子游戏，假设有$m$ 堆石子，每个人可以轮流在不超过$k$ 堆石子中拿走任意数量的石子（不能为0），无法拿石子的一方失败，问先手还是后手胜利？
• 结论：当且仅当所有堆石子数在二进制下的各位上的$0$ 的数目都满足是$k + 1$ 的倍数的时候是必败局面。

证明：

1.石子数为 0 的时候是必败局面

• 且各位上的 1 的数目均为 0，满足为$k + 1$ 的倍数。

2.当各位上 1 的数目都是$k + 1$ 的倍数且存在至少一位上 1 的数目不为 0 的时候

• 由于只能改变$k$ 堆的石子数，故同一位上最多增加或减少$k$ 个 1，
• 故任意合法操作都必将使得至少一位上的 1 的个数不为$k + 1$ 的倍数，也就是必败局面必将转向必胜局面。

3.当存在一位上的 1 的数目不是$k + 1$ 的倍数的时候

• 一定存在合法操作使得各位上的 1 的数目都是$k + 1$ 的倍数。下面我们将构造出这种合法的操作。

构造合法操作：

• 假设我们现在考虑到第$i$ 位，而对于更高的位都已经满足 1 的个数是$k + 1$ 倍数的条件，并且已经合法更改了$m$ 个堆的石子数的值，
• 而在除去这$m$ 堆以外的剩余堆里面在第$i$ 位上有$x$ 个 1，令$r = x \% (k + 1)$。

情况 1：

• 如果$r \leq k - m$，我们可以将第$m$ 堆和$r$ 堆中的所有石子数的第$i$ 位置为 0。

情况 2：

• 如果$r > k - m$，我们可以在$m$ 堆中选择$k + 1 - r$ 堆在第$i$ 位置为 1，
• 而其他堆在第$i$ 位置为 0，由于$k + 1 - r < k + 1 - (k - m) < 1 + m \Rightarrow k + 1 - r \leq m$，因此一定能够在$m$ 堆中选择$k + 1 - r$ 堆。

总结：

• 由于对于任意$i$ 都能找到合法的操作满足条件，故一定存在合法的操作使得必胜局面转化为必败局面。
• 综上所述，给出的结论是正确的。

Nim游戏拓展-Nim-m

• 有两个绝顶聪明的人玩取石子游戏，假设有$n$ 堆石子，每个人可以轮流在任意一堆石子中拿走不超过$k$ 个石子（不能为0），无法拿石子的一方失败，问先手还是后手胜利？
• 结论：当且仅当所有堆石子数模$k + 1$ 的异或和为 0 的时候为必败局面。
• 证明基本同上。

Bash Game

• 有 1 堆石子，总个数是$m$，两名玩家轮流在石子堆中拿石子，每次至少取 1 个，至多取$m$ 个。取走最后一个石子的玩家为胜者。
• 结论：若$m + 1$ 整除$m$ 则先手必败，否则先手必胜。

证明：

1. 当$m \leq m$ 时显然先手获胜；
2. 当$m = m + 1$ 时无论先手取走多少个，后手都能一次性取完，后手获胜；
3. 若$m + 1$ 整除$m$，无论先手取走多少个后手都能保证接下来的石头数剩下$m + 1$ 的倍数，即情况 2，后手获胜；
4. 否则先手可以取走余数个数的石头转换为情况 3，先手获胜。

Wythoff Game

• 有两堆石子，石子数可以不同。两人轮流取石子，每次可以在一堆中取，或者从两堆中取走相同个数的石子，数量不限，取走最后一个石头的人获胜。
• 提示：打个表看看呢？
• 没有思路的话可以试试搜索 beatty 定理

VJwin14C - Game with Marbles (Hard Version)

题意 两人各有$n$ 堆石子，分别编号$1\sim n$。两人轮流选择石子，选择其中一个编号，自己弃这个编号的石子堆的其中一颗石子，对方弃这个编号的石子堆的所有石子。最终得分为甲和乙的石子总数之差，甲希望得分最大化，乙希望得分最小化。求两人的获胜策略，并给出最终得分。

思路 记每方的得分为他最终剩下的石子，实际双方都希望自己得分儘可能大。

设某一堆石子甲有$a$ 颗，乙有$b$ 颗，如果甲选择了，它的得分会增加$a-1$，否则甲不选，乙的得分增加$b-1$。

对于两堆石子$a_1,b_1$ 和$a_2,b_2$，如果甲先选择编号为$1$ 的，乙就只能选择编号为$2$ 的，最终得分为$W_1=(a_1-1)-(b_2-1)=a_1-b_2$，如果甲先选择编号为$2$ 的，最终得分为$W_2=(a_2-1)-(b_1-1)=a_2-b_1$，注意到$W_1-W_2>0\iff a_1+b_1>a_2+b_2$，这表明，甲需要先选择$a+b$ 较大的编号，乙也是同理，这即是获胜策略，得分易算得。

代码 结构体和排序：

struct node {
    ll a, b, sum;
} a[maxN];
bool cmp(node a, node b) { return a.sum > b.sum; }

主函数：

// 输入略
for (int i = 0; i < n; ++i) a[i].sum = a[i].a + a[i].b;
std::sort(a, a + n, cmp);
ll ans = 0;
for (int i = 0; i < n / 2; ++i) ans += a[2*i].a - a[2*i+1].b;
if (n & 1) ans += a[n-1].a - 1;
printf("%lld\n", ans);

变式：

VJwin15G - 国王游戏

题意 每个人有两个数$a_i,b_i$，求这些人所有排列中$\max\limits_{1\leqslant i\leqslant n}\{\frac{1}{b_i}a_0a_1\dots a_{i-1}\}$ 的最小值。

思路 按$a_i\cdot b_i$ 的值升序排列。bool cmp(node a, node b) { return a.prod < b.prod; }

代码

scanf("%d", &n);
for (int i = 0; i <= n; ++i) {
    scanf("%lld %lld", &a[i].a, &a[i].b);
    a[i].prod = a[i].a * a[i].b;
}
std::sort(a + 1, a + n + 1, cmp);
ll prod = a[0].a, ans;
for (int i = 1; i <= n; ++i) {
    ans = max(ans, prod / a[i].b);
    prod *= a[i].a;
}
print(ans);

VJwin14D - 三国游戏

题意 两人轮流选择武将，每两个武将有默契值，最终所选择的武将之间的最大默契值较大的获胜。已知对方的策略是：选择我方已经选择的所有武将的最大默契值对应的那名武将。求获胜策略，并给出我方最终的最大默契值。

思路 对于每一名武将，如果我方将其选走，那么对方会选择最大默契值，于是这个最大默契值两个人都拿不到，可以推出，每个武将的最大默契值两个人都拿不到。因此我们将视线转向次大默契值，在对方选择后，我方可以继续选择次大默契值，这个次大默契值就归我方所有。为了获胜，我们首先选择次大默契值最大的那名武将，选择它，对方会选择最大默契值对应的那名武将，我方接着次大默契值对应的那名武将。由于最大默契值两个人都拿不到，而我方抢走了最大的次大默契值，因此我方必胜。我方最终的最大默契值即是最大的次大默契值。

代码

scanf("%d", &n);
for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
    scanf("%d", &a[i][j]);
    a[j][i] = a[i][j];
}
int ans = 0;
for (int i = 0; i < n; ++i) {
    std::sort(a[i], a[i] + n);
    ans = max(ans, a[i][n - 2]);
}
printf("1\n%d\n", ans);

评注 操作问题一直是组合数学中的难点，我学不会的那种难（儘管组合数学的每个part都很难）

Codeforces Round 941C. Everything Nim

题意$n$ 堆石子，每次选择从每堆中拿走相同数目，不能拿时败。

思路 拿到第一个“空缺”的主动权。

代码

int n = read();
vector v(n+1, 0);
for (int i = 1; i <= n; ++i) v[i] = read();
sort(v.begin(), v.end());
bool op = 0;
for (int i = 1; i <= n; ++i) {
    if (v[i] - v[i-1] > 0) op ^= 1;
    if (v[i] - v[i-1] > 1) break;
}
printf("%s\n", op ? "Alice" : "Bob");

倒着写：

bool op = 0;
for (int i = n; i >= 1; i--) {
    if (v[i] - v[i-1] > 0) {
        if (op == 0) op = 1;
        else if (v[i] - v[i-1] == 1) op = 0;
    }
}
printf("%s\n", op ? "Alice" : "Bob");

CF919B. Summation Game

题意 对于正整数数组，每人执行一次操作：甲至多删除$k$ 个数，乙至多将$x$ 个数变为相反数。甲的目标是使所有数之和最大，而乙的目标是使其最小。求最终所有数之和。

思路 枚举。可以确定的是，乙一定将最大的$x$ 个数变为相反数，甲删的数量不一定，但一定是删最大的一些数，因此按甲的操作数量枚举，寻出最终之和的最大值。（对应于下面的第 7 行）

注意

• 正整数数组；
• $\mathbf{WA}$：自动识别$2\cdot10^5$ 为$10^5$，致 maxN 错误；
• $\mathbf{WA}$：测试用输出符号未删除。

代码

scanf("%d %d %d", &n, &k, &x);
for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); }
std::sort(a + 1, a + n + 1, cmp); // 从大到小排序
for (int i = 1; i <= n; ++i) { s[i] = s[i - 1] + a[i]; } // 前缀和
ans = -1e9;
for (int i = 0; i <= k; ++i) {
    ans = max(ans, s[n] + s[i] - 2 * s[min(n, i + x)]); // min(n, i + x) 避免越界
}
printf("%d\n", ans);

CF925E. Anna and the Valentine’s Day Gift

题意$n$ 个数，小 A 每次选择一个数倒过来并删掉前导零，小 B 每次将一个数拼到另一个数上。如果最后剩下的数$\ge10^m$，则小 B 赢，否则小 A 赢。

思路 小 B 最终的目标其实是所有数的数位和$>m$，所以他要确保删去的前导零最少，小 A 则要删去的最多。将一个数拼到另一个数的高位，就相当于保护了这些前导零不被删掉。设$c_i$ 为$a_i$ 后导零的个数，$s$ 为所有数的位数之和，那么问题变为： 小 A 每次可以选一个数拿走，小 B 也可以。如果最后小 A 拿走的数之和$\le s-m$，那么小 B 赢，否则小 A 赢。 那么两人的最优策略都是拿走当前最大的一个，直接模拟即可。

代码

int n = read(), m = read();
ll sum = 0;
for (int i = 1; i <= n; ++i) {
    int x = read();
    a[i] = 0;
    while (x % 10 == 0) x /= 10, ++a[i], ++sum;
    while (x) x /= 10, ++sum;
}
std::sort(a + 1, a + n + 1, greater<int>());
for (int i = 1; i <= n; i += 2) {
    sum -= a[i];
}
printf("%s\n", sum <= m ? "Anna" : "Sasha");

VJspr2D - Roy&October之取石子 - UPSOLVE

题意 共有$n$ 个石子，两人每次都只能取$p^k$ 个（$p$ 为质数，$k$ 为自然数），取走最后一个石子者胜，问先手是否有必胜策略。

思路$6$ 是合数。

代码

char s[2][100] = { "October wins!", "Roy wins!" };
printf("%s\n", s[(read() % 6) == 0]);

A. 威佐夫的石子游戏 洛谷-P2252

很经典的威佐夫板子题，但是要注意sqrt返回的是double，精度会爆一个点，所以要手开一个long double

update:sqrtl也可以

（2016 ICPC大连同样有一道威佐夫板子但赛时为金牌的题目。数据开到了10的100次方，考察Java高精 + 手开根号（牛顿迭代/二分），感兴趣可以去瞅瞅。）

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

long double Sqrt(long double n)
{
    long double s = sqrt(n);
    for (int i = 1; i <= n; ++i)
        s = n / s;
    return s;
}

int main() {
    int n, m;
    cin >> n >> m;
    if (n < m)swap(n, m);
    int ans = (n - m) * (Sqrt(5.0) + 1.0) / 2.0;
    if (ans == m)cout << "0" << endl;
    else cout << "1" << endl;
    return 0;
}

B. 奶牛的数字游戏 洛谷-P2953

翻译题意：对待一个数字n双方轮流减去其最大数码或者最小数码，

很板子的博弈，说是$dp$ 也不是不行。

数字1-9都是必胜，后续分别判断减去最大数码和最小数码的两个状态中是否有必败态。

若有必败本状态必为必胜（会选择那个必败态让对手必败），否则因为对手必胜只能必败。

这里只需要计必胜必败态，所以不用sg函数，开bool数组就可以了。

离线打表，O(1)查询。

#include <algorithm>
#include <cstdio>
const int N = 1e6 + 8;
bool sg[N];

std::pair<int, int> get(int n) {
    int mx = 0, mn = 9;
    while (n) {
        int t = n % 10;
        n /= 10;
        if (t == 0) continue;
        mx = std::max(mx, t);
        mn = std::min(mn, t);
    }
    return {mx, mn};
}

int main() {
    for (int n = 1; n < N; ++n) {
        auto [mx, mn] = get(n);
        sg[n] = !sg[n - mx] | !sg[n - mn];
    }
    for (int t = read(); t--;) {
        int n = read();
        printf("%s\n", sg[n] ? "YES" : "NO");
    }
    return 0;
}

C. 高手们的石子游戏 洛谷-P2575

一眼就觉得很阶梯，每一行都是独立的不会互相影响，又一眼会觉得很 SG 函数，故写之。

把两个空格之间当作一堆石子，连续棋子当作石子数。

这里附上阶梯博弈参考:

阶梯博弈（另类尼姆博弈） - Yeader - 博客园 (cnblogs.com)

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
bool a[25];

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int ans = 0;
        while (n--) {
            int m;
            cin >> m;
            memset(a, 0, sizeof a);
            int cnt = 20 - m + 1, tot = 0, sg = 0;//阶梯总数，石子数，本行sg
            while (m--) {
                int tmp;
                cin >> tmp;
                a[tmp] = 1;
            }
            for (int i = 1; i <= 20; i++) {
                if (!a[i]) {
                    if ((--cnt) & 1) {//奇数台阶计入sg
                        sg ^= tot;
                    }
                    tot = 0;
                }
                else tot++;
            }
            ans ^= sg;
        }
        if (ans)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

附上两种写法的对拍：

int dfs1(int m, std::vector<int> v) {
    int sg = 0;
    int a[1000] = { 0 }, nim[1000] = { 0 };
    std::sort(v.begin(), v.end());
    for (int j = 1; j <= m; ++j) {
        a[j] = 20 - v[j];
    }
    int de = 0;
    memset(nim, 0, sizeof nim);
    for (int j = m; j >= 1; --j) {
        nim[a[j] - de] += 1;
        de += 1;
    }
    for (int j = 1; j <= 20; j += 2) {
        sg ^= nim[j];
    }

    return sg;
}

int dfs2(int m, std::vector<int> v) {
    int ans = 0;
    int aa[1000] = { 0 };
    int cnt = 20 - m + 1, tot = 0, sg = 0;//阶梯总数，石子数，本行sg
    for (int j = 1; j <= m; ++j) {
        aa[v[j]] = 1;
    }
    for (int i = 1; i <= 20; i++) {
        if (!aa[i]) {
            if ((--cnt) & 1) {//奇数台阶计入sg
                sg ^= tot;
            }
            tot = 0;
        }
        else tot++;
    }
    ans ^= sg;
    return ans;
}

int main() {
    for (int x = 0; x < (1ll << 20); ++x) {
        std::vector<int> v;
        v.push_back(-1);
        for (int i = 0; i < 20; ++i) {
            if (x & (1ll << i)) {
                v.push_back(i + 1);
            }
        }
        if (v.size() == 0) continue;
        int ans1 = dfs1(v.size() - 1, v);
        int ans2 = dfs2(v.size() - 1, v);
        if (ans1 != ans2) {
            printf("%d\n%d %d\n", v.size(), ans1, ans2);
            for (auto& i : v) {
                printf("%d ", i);
            }
        }
    }

    for (int t = read(); t--;) {
        int n = read();
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int m = read();
            std::vector<int> v;
            v.push_back(-1);
            for (int j = 1; j <= m; ++j) {
                v.push_back(read());
            }
            ans ^= dfs1(m, v);
        }
        printf("%s\n", ans ? "YES" : "NO");
    }

    return 0;
}

D. 经典签到游戏 HDU-2897

打表找规律的Bash game。

通过SG打表可以很快看出规律 ， 在1~p之间时为必胜状态 ， p~p+q时为必败状态，之后也不断重复 ， 故取余即可.

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1000;
int sg[maxn], flag[maxn];
void getsg(int n, int p, int q){
    memset(sg, 0, sizeof(sg));
    for (int i = p + 1; i <= n; i++){
        memset(flag, 0, sizeof(flag));
        for (int j = p; j <= q; j++){
            flag[sg[i - j]] = 1;
        }
        for (int j = 0; ; j++){
            if (flag[j] == 0)
            {
                sg[i] = j;
                break;
            }
        }
    }
    for (int i = 0; i <= n; i++){
        cout << "sg_" << i << ":" << sg[i] << endl;
    }

}
int main() {
    int n, p, q;
    while (cin >> n >> p >> q) {
        //getsg(n, p, q);
        int mod = n % (p + q);
        if (mod >= 1 && mod <= p)cout << "LOST" << endl;
        else cout << "WIN" << endl;
    }
    return 0;
}

E. 真正的签到游戏 HDU-1730

显然可以看出必败态为所有黑白棋子之间的距离为0。

最终态为黑白棋子距离为0，而中间若先手打破该状态，后手必有操作可以恢复到该状态，如此反复。

故只需要看最初状态，若Nim和大于0则为必胜，等于0为必败。

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

int main() {
    int n, m, a, b, ans;
    while (cin >> n >> m) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a >> b;
            int d = abs(a - b) - 1;
            ans ^= d;
        }
        if (ans) cout << "I WIN!" << endl;
        else cout << "BAD LUCK!" << endl;
    }
    return 0;
}

F. 海盗的金币游戏 HDU-1538

经典中的经典题，模拟即可。

题意：一群绝顶聪明的海盗分金币，按顺序提出方案，包括提出者在内的所有海盗都进行投票。若有 50% 及以上海盗赞成即通过，否则会把提议者扔进海里换下一个海盗继续提议。

海盗们的策略是保命 > 更多的钱 > 杀人。

你的任务是预测给定的海盗会得到多少金币。

如果分100枚金币的话，脑内迅速打个表：

• 1： 100
• 2： 0 100
• 3： 1 0 99
• 4： 0 1 0 99
• 5：1 0 1 0 98

不难看出只要给与自己编号奇偶相同的海盗各一枚金币即可，但是这种情况仅仅适用于金币够分的时候。

当海盗人数大于200人时：

• 201：所有奇数位各一枚，自己不能拿就可以活
• 202：所有偶数位各一枚，自己不能拿就可以活
• 203：至少需要102票，贿赂100人+自己只有101票，死
• 204：自己死了203必死，故会得到102票，活
• 205：拿不到203和204的票，死
• 206：得到205支持，但102 < 103，死
• 207：得到205和206支持，103 < 104，死
• 208：得到205，206，207支持，刚好够104票，活

不难看出数量大于$2\times100$ 时，1，2，4，8……刚好能活。

记$n = 2 m+2 ^ k$ 为稳定状态。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
const int N = 2e7 + 8;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, p;
        cin >> n >> m >> p;
        if (n <= 2 * m + 2) {//够分
            if (n % 2) {//奇数时
                if (p != n) {//不是分的
                    cout << (p % 2) << endl;//p奇数输出1，p偶数输出0
                }
                else {//是分的
                    cout << m - (n - 1) / 2 << endl;//分走一半，剩下的私吞
                }
            }
            else {//偶数时
                if (p != n) {
                    cout << (1 - (p % 2)) << endl;
                }
                else {
                    cout << m - (n - 1) / 2 << endl;
                }
            }
        }
        else {
            n -= (2 * m);
            p -= (2 * m);
            //cout << "n===" << n << endl;
            //cout << "m===" << m << endl;
            int ans = 1;
            while((ans * 2) <= n) {
                ans *= 2;
            }
            //cout << "ans===" << ans << endl;
            if (p <= ans) {
                cout << "0" << endl;
            }
            else {
                cout << "Thrown" << endl;
            }
        }
    }
    return 0;
}

G. 签到硬币游戏 POJ-2484

题意描述：有一个n个硬币摆成的环，Alice和Bob每次可将一枚硬币翻面，或者将相邻的两个翻面，最后谁无法翻面谁输。

只要存在 2 个以上的硬币 后手赢，因为后手可以将环分成两个相等的对称段，然后重复先手的动作，使两边的段一直保持相等的状态，所以后手会拿到最后的硬币。

#include <iostream>
using namespace std;

int main() {
    int n;
    while (cin >> n && n) {
        if (n > 2) cout << "Bob" << endl;
        else cout << "Alice" << endl;
    }
    return 0;
}

变式：相邻的$[1,k]$ 个：

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        if (n == k || (n & 1) && (k == 1)) cout << "A";
        else cout << "B";
    }
    return 0;
}

H. 字符串游戏 51Nod-1490

建一棵 Trie，将所有字符串插入树中，然后进行类似于树形DP的操作，和一般的博弈不同，因为要进行k轮，并且失败者下一轮会变成先手，所以先手要保证自己最终必赢的情况下，当前轮他可能采取必赢策略也可能采取必输的策略（有可能他要故意输掉前k-1轮，赢下最后一轮），故进行树形DP的时候要分别按照先手必赢、先手必输、可输可赢、无法控制四种状态DP即可。

[[…/图论/树/树习题集05 - 树形 DP#字符串游戏 51Nod-1490]]

#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e6 + 8;
int trie[N][26];
int pcnt = 0;

void insert(string& s){
    int p = 0;
    for(auto c: s){
        if (trie[p][c - 'a'] == -1) trie[p][c - 'a'] = ++pcnt;
        p = trie[p][c - 'a'];
    }
}

int dfs(int n){
    int sum = 0;
    int ans = 0;
    for (int i = 0; i < 26; i++){
        if (trie[n][i] == -1) continue;
        else{
            sum++;
            int res = dfs(trie[n][i]);
            ans |= res ^ 3;
        }
    }
    if (sum == 0) return 2;//叶子节点
    else
        return ans;
}

//ans = 1 win
//ans = 2 lost
//ans = 3 win or lost
//ans = 0 do not know


int main(){
    int n,k;
    string s;
    cin >> n >> k;
    memset(trie, -1, sizeof trie);
    for (int i = 1; i <= n; i++){
        cin >> s;
        insert(s);
    }
    int ans = dfs(0);
    if(ans == 1){
        if (k & 1) cout << "First" << endl;
        else
            cout << "Second" << endl;
    }
    else if(ans == 2 || ans == 0){
        cout << "Second" << endl;
    }
    else
        cout << "First" << endl;
    return 0;
}

I. 巧克力游戏-HDU 3544

[HDU3544] Alice’s Game(网上有些讲解是错的)_q - alice’s game hdu - 3544-CSDN博客

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    int T;
    cin >> T;
    for (int Ti = 1; Ti <= T; Ti++) {
        int n;
        cin >> n;
        ll a = 0, b = 0;
        while (n--) {
            int x, y;
            cin >> x >> y;
            while (x > 1 && y > 1) {
                x >>= 1;
                y >>= 1;
            }
            if (y == 1) a += x - 1;
            if (x == 1) b += y - 1;
        }
        printf("Case %d: %s\n", Ti, a > b ? "Alice" : "Bob");
    }
    return 0;
}

J. 树和博弈 CF-1404B

[[…/图论 - 树/树习题集#树和博弈 CF-1404B]]

题意 树上博弈。两人从起始点$a,b$ 轮流跳，每次跳跃上界为$d_{a},d_{b}$。若 A 和 B 重合，则 A 胜，否则在足够长的时间内都不能重合，则 B 胜。判断胜负。（[[…/数学/博弈论#J. 树和博弈 CF-1404B]]）

写法 1 利用树形 DP 和和 LCA 求树直径和两点间距离。时间复杂度$\Theta(n)$，空间$\Theta(30n)$。

constexpr int N = 1e5 + 8;
vector<int> E[N];
int d, dp1[N], dp2[N];
int pa[30][N], dep[N], Log2[N];

void dfs(int u, int p = 0) {
    dep[u] = dep[p] + 1;
    pa[0][u] = p;
    for (int i = 1; i <= Log2[dep[u]]; ++i) pa[i][u] = pa[i - 1][pa[i - 1][u]];
    dp1[u] = dp2[u] = 0;

    for (auto &v : E[u]) {
        if (v == p) continue;
        dfs(v, u);
        int t = dp1[v] + 1;
        if (t > dp1[u]) dp2[u] = dp1[u], dp1[u] = t;
        else if (t > dp2[u]) dp2[u] = t;
    }
    d = max(d, dp1[u] + dp2[u]);
}

int getlca(int u, int v) {
    if (dep[u] > dep[v]) swap(u, v);
    while (dep[u] != dep[v]) v = pa[Log2[dep[v] - dep[u]]][v];
    if (u == v) return u;
    for (int bit = Log2[dep[u]]; bit >= 0; --bit) {
        if (pa[bit][u] != pa[bit][v]) u = pa[bit][u], v = pa[bit]
    }
    return pa[0][u];
}

int getd(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[getlca(u, v)];
}

void eachT() {
    int n = read(), a = read(), b = read(), da = read(), db = read();
    for (int i = 2; i <= n; ++i) {
        int u = read(), v = read();
        E[u].push_back(v), E[v].push_back(u);
    }

    // DP求树直径
    dfs(1);

    // 计算答案
    bool ans;
    if (getd(a, b) <= da) ans = 1;          // 一步就死
    else if (da >= db) ans = 1;             // A 的跳远更牛
    else if (d <= 2 * da) ans = 1;          // A 全覆盖
    else if (db >= 2 * da + 1) ans = 0;     // B 来回跳跃
    else ans = 1;
    printf("%s\n", ans ? "Alice" : "Bob");

    // 初始化
    d = 0;
    for (int u = 1; u <= n; ++u) {
        for (int i = 0; i < 33; ++i) pa[i][u] = 0;
        dp1[u] = dp2[u] = dep[u] = 0;
        E[u].clear();
    }
}

int main() {
    for (int i = 2; i < N; ++i) Log2[i] = Log2[i / 2] + 1;
    for (int t = read(); t--;) eachT();
    return 0;
}

写法 2 两次 DFS 求树直径，再一次 DFS 求两点间距离。时间复杂度$\Theta(n)$，空间$\Theta(n)$。

constexpr int N = 1e5 + 8;
vector<int> E[N];
int dep[N];

void dfs(int u, int p = 0) {
    dep[u] = dep[p] + 1;
    for (auto &v : E[u]) if (v != p) dfs(v, u);
}

void eachT() {
    int n = read(), a = read(), b = read(), da = read(), db = read();
    for (int i = 2; i <= n; ++i) {
        int u = read(), v = read();
        E[u].push_back(v), E[v].push_back(u);
    }

    // 两次DFS求树直径
    dfs(1);
    int c = 0;
    for (int i = 1; i <= n; ++i) {
        if (dep[c] < dep[i]) c = i;
    }
    dfs(c);
    c = 0;
    for (int i = 1; i <= n; ++i) {
        if (dep[c] < dep[i]) c = i;
    }
    int d = dep[c] - 1;

    dfs(a);

    // 计算答案
    bool ans;
    if (dep[b] - 1 <= da) ans = 1;          // 一步就死
    else if (da >= db) ans = 1;             // A 的跳远更牛
    else if (d <= 2 * da) ans = 1;          // A 全覆盖
    else if (db >= 2 * da + 1) ans = 0;     // B 来回跳跃
    else ans = 1;
    printf("%s\n", ans ? "Alice" : "Bob");

    // 初始化
    d = 0;
    for (int u = 1; u <= n; ++u) {
        E[u].clear();
    }
}