acwing算法提高之数学知识--博弈论

本文主要是介绍acwing算法提高之数学知识--博弈论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 介绍

本博客用来记录博弈论相关的题目。

2 训练

题目1：1319移棋子游戏

C++代码如下，

#include <cstdio>
#include <cstring>
#include <set>using namespace std;const int N = 2010, M = 6010;int n, m, k;
int h[N], e[M], ne[M], idx;
int f[N];void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}int sg(int u) {if (f[u] != -1) return f[u];set<int> S;for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];S.insert(sg(j));}for (int i = 0; ; i++) {if (S.count(i) == 0) {f[u] = i;break;}}return f[u];
}int main() {scanf("%d%d%d", &n, &m, &k);memset(h, -1, sizeof h);for (int i = 0; i < m; ++i) {int a, b;scanf("%d%d", &a, &b);add(a, b);}memset(f, -1, sizeof f);int res = 0;for (int i = 0; i < k; ++i) {int u;scanf("%d", &u);res ^= sg(u);}if (res) puts("win");else puts("lose");return 0;
}

题目2：1321取石子

C++代码如下，

#include <cstdio>
#include <cstring>using namespace std;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);if (a && !dp(a-1,b)) return v = 1;if (b && !dp(a,b-1)) return v = 1;if (a >= 2 && !dp(a-2, b + (b ? 3 : 2))) return v = 1;if (a && b && !dp(a - 1, b + 1)) return v = 1;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");}return 0;
}

题目3：1322取石子游戏

C++代码如下，

#include <cstdio>using namespace std;const int N = 1010;int n;
int a[N];
int 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 > L) 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;
}