移棋子游戏

题目

https://vjudge.csgrandeur.cn/problem/LibreOJ-10243

给定一个有 N 个节点的有向无环图，图中某些节点上有棋子，两名玩家交替移动棋子。

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

对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。

输入格式

第一行，三个整数 N , M, K ， N 表示图中节点总数， M 表示图中边的条数， K 表示棋子的个数。

接下来 M 行，每行两个整数 X, Y 表示有一条边从 X 出发指向 Y 。

接下来一行， K 个空格间隔的整数，表示初始时，棋子所在的节点编号。

输出格式

若先手胜，输出 win，否则输出 lose。

输入样例

输出样例

win

数据范围与提示

对于全部数据， $\le 2000, M \le 6000, 1 \le K \le N$ 。

思路

$m e x$ 运算： $mes(S)=min\{x\}(x\in N,x \notin S)$ ，即x为不属于集合S的最小非负整数

SG函数：设状态 $x$ 有 $k$ 个后继状态 $y_1,y_2...y_k$ ,则 $SG(x)=mex(\{ SG(y_1),SG(y_2)...SG(y_k) \})$

SG定理：由n个有向图游戏组成的组合游戏，设起点分别为 $s_1,s_2...s_n$ ，当 $\land SG(s2)... \land SG(s_n)!=0$

时，先手必胜，否则，先手必败

SG图如下：

在本题中，每个棋子都是孤立的，k个棋子可以拆分成k个有向图游戏，利用SG定理判断即可。

代码

#include <bits/stdc++.h>#define int long long
using namespace std;const int N = 2e3 + 10;vector<int> e[N];
int f[N];int dfs(int x) {if (f[x] != -1) return f[x];set<int> s;for (auto y: e[x]) {s.insert(dfs(y));}for (int i = 0;; i++) {if (!s.count(i)) return f[x] = i;}}signed main() {
#ifndef ONLINE_JUDGEfreopen("test.in", "r", stdin);freopen("test.out", "w", stdout);
#endifint n, m, k;cin >> n >> m >> k;for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;e[x].push_back(y);}memset(f, -1, sizeof f);int res = 0;while (k--) {int x;cin >> x;res ^= dfs(x);}if (res) cout << "win"; else cout << "lose";return 0;
}

集合-Nim游戏

题目

https://www.acwing.com/problem/content/895/

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

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

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

输入格式

第一行包含整数 $k$ ，表示数字集合 $S$ 中数字的个数。

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

第三行包含整数 $n$ 。

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

输出格式

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

否则，输出 No。

数据范围

$\le n, k \le 100$ ,
$\le s_i,h_i \le 10000$

输入样例：

输出样例：

Yes

思路

和上一题类似，这里当前点x可以到达的状态为 $x - a [i] (x - a [i] >= 0)$ ,

因此记忆化搜索的时候搜这些点

代码

#include <bits/stdc++.h>#define int long long
using namespace std;const int N = 110,M=10010;
int a[N];
int n, k, h[M];
int f[M];int dfs(int x) {if (f[x] != -1) return f[x];set<int> s;for (int i = 1; i <= k; i++) {if (x - a[i] >= 0) s.insert(dfs(x - a[i]));}for (int i = 0;; i++) {if (!s.count(i)) return f[x] = i;}
}signed main() {
#ifndef ONLINE_JUDGEfreopen("test.in", "r", stdin);freopen("test.out", "w", stdout);
#endifcin >> k;for (int i = 1; i <= k; i++) cin >> a[i];cin >> n;for (int i = 1; i <= n; i++) cin >> h[i];memset(f, -1, sizeof f);int res = 0;for (int i = 1; i <= n; i++) {res ^= dfs(h[i]);}if (res) cout << "Yes";else cout << "No";return 0;
}

剪纸游戏

题目

https://www.acwing.com/problem/content/221/

给定一张 $\times M$ 的矩形网格纸，两名玩家轮流行动。

在每一次行动中，可以任选一张矩形网格纸，沿着某一行或某一列的格线，把它剪成两部分。

首先剪出 $\times 1$ 的格纸的玩家获胜。

两名玩家都采取最优策略行动，求先手是否能获胜。

提示：开始时只有一张纸可以进行裁剪，随着游戏进行，纸张被裁剪成 $2, 3, \dots$ 更多张，可选择进行裁剪的纸张就会越来越多。

输入格式

输入包含多组测试数据，每组数据占一行。

每组数据包括两个整数 $N$ 和 $M$ ，表示初始网格纸的尺寸。

输出格式

每组测试数据输出一个结果，结果占一行。

如果先手方必胜，则输出 WIN；

如果先手方必输，则输出 LOSE。

数据范围

$\le N,M \le 200$

输入样例：

2 2
3 2
4 2

输出样例：

LOSE
LOSE
WIN

思路

因为最后的1*1是一个必胜态，但是我们平时做的sg函数的结果异或和为0得到的是一个必败态。因此可以先把本题转化为必败态来做：

代码

#include <bits/stdc++.h>#define int long long
using namespace std;const int N = 210;
int n, m;
int f[N][N];int dfs(int a, int b) {if (f[a][b] != -1) return f[a][b];set<int> s;for (int i = 2; i <= a - 2; i++) {s.insert(dfs(i, b) ^ dfs(a - i, b));}for (int i = 2; i <= b - 2; i++) {s.insert(dfs(a, i) ^ dfs(a, b - i));}for (int i = 0;; i++) {if (!s.count(i)) return f[a][b] = f[b][a] = i;}
}signed main() {
#ifndef ONLINE_JUDGEfreopen("test.in", "r", stdin);freopen("test.out", "w", stdout);
#endifmemset(f, -1, sizeof f);while (cin >> n >> m) cout << (dfs(n, m) ? "WIN" : "LOSE") << endl;return 0;
}