博弈论学习笔记【未完】_洛谷6872

博弈论

参考过的文章：

Link 好文要顶

0x00. 初始定义

0x01. 公平游戏的定义

公平游戏的定义：

1. 两个玩家交替行动。
2. 其中不能进行移动的玩家就赢了/输了。
3. 在游戏进行的时候，可以执行的操作和当前是哪一个玩家无关。

0x02. 必胜必败状态的定义

必胜状态的定义：如果这个状态对方无论怎么走都必败，就是一个对于你的必胜状态。

必败状态的定义；如果这个状态对方无论怎么走都必胜，就是一个对于你的必败状态。

0x03. mex运算的定义

mex ⁡ { a 1 , a 2 , a 3 , ⋯   , a k } \operatorname{mex}\{a_1,a_2,a_3,\cdots,a_k\} mex{a1​,a2​,a3​,⋯,ak​} 为在 $a$ 数组中最小的没有出现过的自然数。自然数是指 $\ge 0$ 的整数。

0x04. SG定理 / SG函数

如果一个状态 $x$ 可以转移到 $a_1,a_2,a_3,\cdots ,a_k$ 这些状态，那这个状态的值就是 mex ⁡ { a 1 , a 2 , a 3 , ⋯   , a k } \operatorname{mex}\{a_1,a_2,a_3,\cdots,a_k\} mex{a1​,a2​,a3​,⋯,ak​}，其中终止状态的 SG 值为 $0$。

如果一个状态的 SG 值为 $0$ 就是必败状态，否则就是必胜状态。

0x05. SJ定理

对于任意一个 Anti-SG 游戏，如果我们规定：当局面中所有的单一游戏的 SG 值为 $0$ 时，游戏结束，则先手必胜当且仅当满足下列条件：

1. 游戏的 SG 函数值不为 $0$ 且游戏中某个单一游戏的 SG 函数值大于 $1$。
2. 游戏的 SG 函数值为 $0$ 且游戏中没有任意一个单一游戏的 SG 函数值大于 $1$。

0x10. Bash 游戏

人Win LK 和 6872 玩游戏。

有 $1$ 堆石子，一共有 $n$ 个石子，每一个人一次可以取 $1\sim k$ 个石子，问谁可以获胜。

这不是小学奥数题吗

进行分类讨论。

• 如果 $n\mathrm{mod}(k+1)=0$，那么先手拿 $a$ 个，后手拿 $k+1-a$ 个一定可以拿到最后一个。先手必败。
• 否则，先手可以先拿 $n\mathrm{mod}(k+1)$ 个，然后后手变成先手，状态变成第一种情况，先手必胜。

bool check(int n, int k)
{ return n % (k + 1); }
1
2

0x20. Nim 游戏

0x21. 普通 Nim

Link

人win LK 和 6872 玩游戏。

nim 游戏的规则是这样的：地上有 $n$ 堆石子（每堆石子数量小于 $10^4$ ），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如 人Win LK 是先手，且告诉你这 $n$ 堆石子的数量，他想知道是否存在先手必胜的策略。

结论：如果每一堆石子的值都异或起来，答案为 $0$，那么 6872 必胜，否则 LK 必胜。

证明：

如果轮到某一个人走，却没有办法走，对于他的对手就是必胜状态，那么这种情况所有的石子一定全部都是 $0$，也就是每一堆都没有石子，那么异或和也为 $0$。

否则，如果异或和不为 $0$，一定存在某一种方式拿走一些石子让异或和为 $0$；同理，如果异或和为 $0$，那么一定存在某一种方式拿走一些石子让异或和不为 $0$。（不会证明这个鬼玩意）

代码：

#include <bits/stdc++.h>

using namespace std;

signed main()
{
  int T;
  cin >> T;
  while (T --)
  {
    int n, xr = 0;
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
      int x;
      cin >> x;
      xr ^= x;
    }
    if (xr) cout << "Yes\n";
    else cout << "No\n";
  }
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

AC Link

0x22. 阶梯 Nim

人win LK 和 6872 玩游戏。

有一个 $n$ 阶的台阶，每一个台阶都有一些石子，现在人Win LK 和 6872 轮流将石子从上一级台阶移动到下一级台阶，如果没有台阶上有石子就败，人Win LK 想知道他没有必胜策略。

容易发现，如果一个人将偶数级台阶移到了奇数级台阶，那么可以用同样的操作将奇数级台阶移动到偶数级台阶。所以说只要将奇数台阶上的所有石子的异或和异或起来即可。

代码：

#include <bits/stdc++.h>

using namespace std;

signed main()
{
  int n, xr = 0;
  cin >> n;
  for (int i = 1; i <= n; i ++)
  {
    int x;
    cin >> x;
    if (i & 1)
      xr ^= x;
  }
  if (xr) cout << "Yes\n";
  else cout << "No\n";
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

0x30. SG 类问题 / 选取集合类问题

0x31. 一堆石子的选取集合类问题

请看 0xa0。

0x32. 多堆石子的选取集合类问题

人Win LK 和 6872 玩游戏。

有 $n$ 堆石子，每一堆石子只要能拿就可以拿 $a_1,a_2,a_3,\cdots ,a_k$ 个石子，谁不能拿他的对手就赢了，人Win LK 想要知道他能不能赢。

实际上就是 0x04 SG 定理。使用 SG 定理可以通过这道题。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int f[N], a[N];
int n, m;

int sg(int x)
{
  if (f[x] != -1)
    return f[x];
  vector <int> arr;
  for (int i = 0; i < m; i ++)
    if (x >= a[i])
      arr.push_back(sg(x - a[i]));
  sort (arr.begin(), arr.end());
  arr.erase(unique(arr.begin(), arr.end()), arr.end());
  set <int> se;
  for (auto &u : arr)
    se.insert(u);
  for (int i = 0; ; i ++)
    if (!se.count(i))
      return f[x] = i;
  return -1;
}

signed main()
{
  memset (f, -1, sizeof f);
  cin >> m;
  for (int i = 0; i < m; i ++)
    cin >> a[i];
  cin >> n;
  int xr = 0;
  for (int i = 0; i < n; i ++)
  {
    int x;
    cin >> x;
    xr ^= sg(x);
  }
  if (xr)
    cout << "Yes\n";
  else
    cout << "No\n";
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

0x40. Anti-SG 类问题

0x41. Anti-Nim 问题

Link

人Win LK 经常和他的好朋友 6872 玩一个非常有趣的游戏：桌子上有 $n$ 堆石子，人Win LK 和他的好朋友 6872 轮流取石子，每个人取的时候，可以随意选择一堆石子，在这堆石子中取走任意多的石子，但不能一粒石子也不取，我们规定取到最后一粒石子的人算输。

人Win LK 相当固执，他坚持认为先取的人有很大的优势，所以他总是先取石子，而他的好朋友 6872 就聪明多了，他从来没有在游戏中犯过错误。人Win LK 一怒之前请你来做他的参谋。自然，你应该先写一个程序，预测一下谁将获得游戏的胜利。

结论：先手必胜需要满足所有堆的石子数都为 $1$ 且异或和为 $0$（也就是有偶数堆）或者有一个或者以上堆的石子数 $>1$ 且石子堆的异或和不为 $0$。

代码：

#include <bits/stdc++.h>

using namespace std;

int a[55];

signed main()
{
  int T;
  cin >> T;
  while (T --)
  {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++)
      cin >> a[i];
    if (n % 2 == 0)
    {
      bool flag = true;
      for (int i = 1; i <= n; i ++)
        if (a[i] != 1)
        {
          flag = false;
          break;
        }
      if (flag)
      {
        cout << "John\n";
        continue ;
      }
    }
    bool flag = false;
    for (int i = 1; i <= n; i ++)
      if (a[i] > 1)
      {
        flag = true;
        break;
      }
    if (!flag)
    {
      cout << "Brother\n";
      continue ;
    }
    int xr = 0;
    for (int i = 1; i <= n; i ++)
      xr ^= a[i];
    if (xr)
      cout << "John\n";
    else
      cout << "Brother\n";
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

AC Link

0x50. 黄金比博弈 / 威佐夫博弈

0x60. 图 / 树上的博弈论问题

0x61. 有向无环图上的单游戏博弈

题意：给定一个有 $N$ 个节点的有向无环图，图中有一个节点有棋子，人Win LK 和 6872 交替移动棋子。

玩家每一步可将这个棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。

对于给定的图和棋子初始位置，人Win LK 和 6872 都会采取最优的行动，人Win LK 想要知道他是否有必胜策略。

实际上就是简单的图上 DP，直接暴力进行状态转移即可。

代码（你觉得这么简单的题还需要代码吗）

0x62. 有向无环图上的多游戏博弈

Link

题意：给定一个有 $N$ 个节点的有向无环图，图中某些节点上有棋子，人Win LK 和 6872 交替移动棋子。

玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。

对于给定的图和棋子初始位置，人Win LK 和 6872 都会采取最优的行动，人Win LK 想要知道他是否有必胜策略。

有向无环图（DAG）上的多游戏博弈问题：终点的 sg 函数值为 $0$，其他节点的 sg 值为他可以到达的所有点的 sg 值的 mex 值。

然后就可以在图上进行遍历求解 sg 函数的值了。

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
const int N = 2010;
vector <int> z[N];
int f[N];

int sg(int u)
{
  if (~f[u])
    return f[u];
  vector <int> arr;
  for (auto &i : z[u])
    arr.push_back(sg(i));
  sort (arr.begin(), arr.end());
  arr.erase(unique(arr.begin(), arr.end()), arr.end());
  set <int> se;
  for (auto &u : arr)
    se.insert(u);
  for (int i = 0; ; i ++)
    if (!se.count(i))
      return f[u] = i;
  return 114514;
}

int main()
{
  cin >> n >> m >> k;
  while (m --)
  {
    int a, b;
    cin >> a >> b;
    z[a].push_back(b);
  }
  memset (f, -1, sizeof f);
  int xr = 0;
  for (int i = 0; i < k; i ++)
  {
    int x;
    cin >> x;
    xr ^= sg(x);
  }
  if (xr)
    cout << "win\n";
  else
    cout << "lose\n";
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

AC Record

0x70. Every-SG 问题

题意：人Win LK 先走，每个游戏由两堆石子组成，每次可以从较多的那一堆中取走较小那堆的数量的倍数个石子。问人Win LK 赢还是 6872 赢。

如果 $x>y$ 就交换。

如果 $\lfloor \frac{y}{x}\rfloor =1$，那么直接计算答案即可。

否则，只需要考虑 $k=1$ 的后续状态即可。

#include <bits/stdc++.h>

using namespace std;

int f[1010][1010], g[1010][1010];

int sg(int x, int y)
{
  if (x > y)
    swap (x, y);
  if (~f[x][y])
    return f[x][y];
  if (x == 0 || y == 0)
    return f[x][y] = 0;
  int a = y % x, b = y / x;
  if (b == 1)
  {
    f[x][y] = sg(a, x) ^ 1;
    g[x][y] = g[a][x] + 1;
    return f[x][y];
  }
  else
  {
    g[x][y] = sg(a, x) + g[a][x] + 1;
    return f[x][y] = 1;
  }
}

signed main()
{
  memset (f, -1, sizeof f);
  int n;
  while (cin >> n)
  {
    int mx = 0, a, b;
    while (n --)
    {
      cin >> a >> b;
      sg(a, b);
      if (a > b)
        swap(a, b);
      mx = max(mx, g[a][b]);
    }
    if (mx & 1)
      cout << "MM\n";
    else
      cout << "GG\n";
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

0x80. Multi-SG 问题

0x81. 分割类博弈

人Win LK 和 6872 正在玩游戏。

人Win LK 先走，每一次拿走 $n$ 堆石子中的一堆，假设这一堆石子中有 $x$ 个，那么可以放入两堆石子，且放入满足石子的个数小于 $x$ 个，不过可以为 $0$。如果 $x=0$ 那么不能分割。不能拿的人的对手就赢了，人Win LK 想要知道他有没有必胜策略。

容易发现，$x$ 状态可以分裂成 $(a,b)$ （$0\le a,b<x$）。

然后引入 SG 定理：$sg(a,b)=sg(a)\mathrm{xor}sg(b)$。然后只需要枚举 $a$ 和 $b$ 即可。

代码：

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>

using namespace std;

const int N = 210;
int f[N], n;

int sg(int x)
{
  if (~f[x])
    return f[x];
  set <int> se;
  for (int i = 0; i < x; i ++)
    for (int j = 0; j <= i; j ++)
      if (!se.count(sg(i) ^ sg(j)))
        se.insert(sg(i) ^ sg(j));
  for (int i = 0; ; i ++)
    if (!se.count(i))
      return f[x] = i;
  return 114514;
}

signed main()
{
  memset (f, -1, sizeof f);
  cin >> n;
  int res = 0;
  for (int i = 1; i <= n; i ++)
  {
    int x;
    cin >> x;
    res ^= sg(x);
  }
  if (res)
    cout << "Yes\n";
  else
    cout << "No\n";
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

0x90. 斐波那契博弈

0xa0. 其他博弈论

0xa1. DP 类博弈论

没有题目，比如说每一次可以拿 2 3 6 数量的棋子，那么直接 DP 转移。

0xa2. 其他类博弈论

请翻我的博客。

0xb0. 总结

$我太菜了！$