博弈论合集
1. 巴什博弈
1. 1 博弈规则
A、B取一堆石子（数量为n），每次可以取1，2，3个，无法操作的人失败。
1.2 博弈策略
牵制：保证每一轮A、B共取走4个，即如果先手取
x
x
x个则后手取
4
−
x
4-x
4−x个。 所以，如果n%4 = 0，则后手有必胜策略，否则先手有必胜策略（先手第一轮先取走n%4个石子即可）。
1.3 .扩展巴什博弈
1.3.1. 博弈规则
A、B取一堆石子（数量为n），每次可以取的个数是给定的集合P中的一个数，无法操作的人失败。
1.3.2.问题求解
SG函数：
s
g
x
sg_{x}
sgx = mex {
s
g
y
sg_{y}
sgy | x - y
∈
\isin
∈ P}。若
s
g
n
≠
0
sg_{n}\neq0
sgn=0则先手有必胜策略。
1.4. 多堆扩展巴什博弈
1.4.1.博弈规则
A、B取多堆石子，每次可以在某一堆取的个数是给定的集合P中的一个数，无法操作的人失败。
1.4.2.问题求解
每一堆的SG函数异或起来，如果异或和不为0，则先手有必胜策略。
2. NIM游戏
2.1NIM
2.1.1博弈规则
A、B取多堆石子，每次可以在某一堆取任意的一个数，无法操作的人失败。
2.1.2问题求解
每一堆的数异或起来，如果异或和不为0，则先手有必胜策略。
2.1.3典型题
[GZOI2017]取石子游戏
题意：从N堆中选出M堆，并指定第一次操作的堆，使得先手必败。 思路：枚举第一堆，选出的其他堆的异或值需要大于等于第一堆的数量，这样先手没有必胜策略。
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 310;
const int m = 300;
const LL mod = 1e9 + 7;
LL f[N], g[N];
int a[N];
int n;
LL get_ans(int x)
{
for(int i = 0; i <= m; i++)
f[i] = 0;
f[0] = 1;
for(int i = 1; i <= n; i++)
if(i != x)
{
for(int j = 0; j <= m; j++)
if((j ^ a[i]) <= m)
g[j ^ a[i]] = (g[j ^ a[i]] + f[j]) % mod;
for(int j = 0; j <= m; j++)
f[j] = (g[j] + f[j]) % mod, g[j] = 0;
}
LL now = 0;
for(int i = a[x]; i <= m; i++)
now = (now + f[i]) % mod;
return now;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
a[n + 1] = 0;
LL ans = 0;
for(int i = 1; i <= n; i ++)
ans = (ans + get_ans(i)) % mod;
cout< return 0; } 2.3.NIMK游戏 2.3.1.博弈规则 A、B取多堆石子，每次可以在最多k堆中每堆取任意数，无法操作的人失败。 2.3.2问题求解 必胜策略：所有数拆成二进制，存在某一位，所有二进制数中1的个数%（k+1）不为0。即存在t，使得 ( ∑ i = 1 n x i x o r 2 t − 1 ) % ( k + 1 ) ≠ 0 (\sum_{i = 1}^{n}{x_{i} xor 2^{t-1}})\%(k+1)\neq0 (∑i=1nxixor2t−1)%(k+1)=0。 2.4 Fibonacci Nim游戏 2.4.1.博弈规则 A、B取一堆石子，第一次不能把所有石子取完，从第二次开始，每次取的石子数量不超过前一次的两倍，无法操作的人失败。 2.4.2问题求解 必胜策略：n不是Fibonacci数时，先手必胜。 2.5 阶梯NIM 2.5.1.博弈规则 A、B取多堆石子，每次可以从第k堆石子中取出任意多放入第k-1堆中，也可以从第一堆中直接拿走任意多，无法操作的人失败。 2.5.2问题求解 必胜策略：如果奇数堆中的石子数异或和不为0则先手必胜。 如果先手在偶数堆k中操作，则后手在k-1堆中继续操作即可；如果先手在奇数堆中操作，则相当于普通NIM。 2.5.3典型题 [POI2009]KAM-Pebbles 题意：n堆取石子，要求任意时刻 a 1 ≤ a 2 ≤ … … a n a_{1}\leq a_{2} \leq……a_{n} a1≤a2≤……an。 思路：差分以后看出阶梯博弈。 const int N = 1010; int a[N], c[N]; int main() { int T,n; scanf("%d", &T); while(T) { T--; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++) c[i] = a[i] - a[i - 1]; int ans = 0; for(int i = n; i >= 1; i -= 2) ans ^= c[i]; if(ans) printf("TAK\n"); else printf("NIE\n"); } return 0; } 2.6分裂博弈 2.6.1典型例题 HNOI2007 分裂游戏 题意：n堆石子，每次操作选择 i < j ≤ k i < j \leq k i 只有石子数是奇数的堆是有用的 a) 如果某一堆的石子数量是偶数，那么后手可以模仿先手的操作，因此，对于这堆而言，先手无论如何也无法牵制后手。 b) 如果某一堆是奇数，那么先手有牵制后手的可能。 奇数堆的石子个数可以看成1 n+2枚石子可以转化成n枚石子的状态，因此奇数堆的看成1（偶数堆看成0） 对于每一堆，考虑其转移后的位置的状态，看是否有必胜策略 SG[i] = mex( SG[j]^SG[k]) SG[i]表示第i堆有一枚石子时的SG值。 枚举第一步，判断异或和，异或和为0，后手必胜 注意，为方便计算SG，应从后向前枚举，即SG[i]表示第n-i+1堆 #include #include #include #include #include #include using namespace std; const int N = 110; int vist[N], sg[N], a[N]; void init() { for(int i = 2;i <= 21; i++) { for(int j = 0; j <= 100; j++) vist[j] = 0; for(int j = 1; j <= i - 1;j++) for(int k = 1; k <= j; k++) vist[sg[j] ^ sg[k]] = 1; for(int j = 0; j <= 100 && vist[j]; j++) sg[i]++; } } int main() { init(); int T, n; scanf("%d", &T); while(T) { T--; scanf("%d", &n); int ans = 0; for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); if(a[i] & 1) ans = ans ^ sg[n - i + 1]; } int ansi, ansj, ansk; ansi = ansj = ansk = -1; int tot = 0; for(int i = n - 1; i > 0; i--) for(int j = n; j > i; j--) for(int k = n; k >= j; k--) { if((ans ^ sg[n - i + 1] ^ sg[n - j + 1] ^ sg[n - k + 1]) == 0) { tot++; ansi = i - 1; ansj = j - 1; ansk = k - 1; } } printf("%d %d %d\n%d\n", ansi, ansj, ansk, tot); } return 0; } 2.7 反NIM 2.7.1 博弈规则 A、B取多堆石子，每次可以在某一堆取任意的一个数，无法操作的人胜利。 2.7.2 问题求解 必胜策略： 所有数为1，且异或和为0至少有一堆大于1，且异或和不为0 3. Wythoff博弈 3.1.博弈规则 A、B取多两石子，每次可以在一堆中取任意多个，或者在两堆中取同样的任意多个，无法操作的人失败。 3.2问题求解 奇异局势（先手必败）：（0，0）、（1，2）、（3，5）、(4，7)…… ( a k ， b k ) (a_{k}，b_{k}) (ak，bk) 其中 a k a_{k} ak是之前未出现过的最小自然数， b k = a k + k b_{k} = a_{k}+k bk=ak+k 4.有向图博弈 4.1典型题目 [SBCOI2020] 时光的流逝 题意：给一个有向图，每次询问给定起点和终点，A、B轮流操纵棋子，每次可以走一步，走到终点后不能操作，没有出边时不能操作，不能操作的输，求先手是否有必胜策略。 思路：反向建图，把没有出边的点和终点的sg函数都赋值成-1，bfs，如果一个点的后继中有必败态，则该点是必胜态，入队；如果一个点的所有后继都是必胜态，则该点必败，入队。（类似拓扑） #include #include #include #include #include #include using namespace std; const int N = 1e5 + 10; const int M = 5e5 + 10; const int Q = 510; struct EDGE{ int nxt, to; }edge[M]; int t[N], in[N], cnt[N], f[N], q[N]; int tot, n; void addedge(int x, int y) { edge[++tot].nxt = t[x]; edge[tot].to = y; t[x] = tot; in[y]++; } int solve(int s, int e) { for(int i = 1 ;i <= n; i++) cnt[i] = in[i], f[i] = 0; int head = 0, tail = 0; for(int i = 1; i <= n; i++) if(!in[i]) { f[i] = -1; q[++tail] = i; } f[e] = -1; q[++tail] = e; while(head < tail) { head++; int x = q[head]; for(int p = t[x]; p; p = edge[p].nxt) { int y = edge[p].to; if(f[x] == -1 && f[y] == 0) { f[y] = 1; q[++tail] = y; } cnt[y]--; if(cnt[y] == 0 && f[y] == 0) { f[y] = -1; q[++tail] = y; } } } return f[s]; } int main() { int m, qq, x, y; scanf("%d%d%d", &n, &m, &qq); for(int i = 1; i <= m; i++) { scanf("%d%d", &x, &y); addedge(y, x); } for(int i = 1; i <= qq; i++) { scanf("%d%d", &x, &y); printf("%d\n", solve(x, y)); } return 0; } [CQOI2013]棋盘游戏 题意：A、B操控黑白两枚棋子，先吃到对方（位置重合）的获胜，求最终谁获胜，并求出操作步数。 思路：留坑 #include #include #include #include #include #include using namespace std; const int N = 25; const int inf = 1e9 + 7; struct NODE{ int x, y, xx, yy, opt; }q; int f[2][61][N][N][N][N]; int dx[8] = {0, 0, 1, -1, 0, 0, 2, -2}, dy[8] = {1, -1, 0, 0, 2, -2, 0, 0}; int n; int judge(int x, int y) { if(x <= 0 || y <= 0 || x > n || y > n) return 0; return 1; } int solve(int step, int x, int y, int xx, int yy) { if(step > 3 * n) return inf; if(f[step & 1][step][x][y][xx][yy]) return f[step & 1][step][x][y][xx][yy]; if(x == xx && y == yy) { if(step & 1) return inf; else return 0; } int ans; if(step & 1) { ans = inf; for(int i = 0; i < 8; i++) { int nowx = xx + dx[i]; int nowy = yy + dy[i]; if(!judge(nowx, nowy)) continue; ans = min(ans, solve(step + 1, x, y, nowx, nowy)); } } else { ans = 0; for(int i = 0; i < 4; i++) { int nowx = x + dx[i]; int nowy = y + dy[i]; if(!judge(nowx, nowy)) continue; ans = max(ans, solve(step + 1, nowx, nowy, xx, yy)); } } f[step & 1][step][x][y][xx][yy] = ++ans; return ans; } int main() { int sx, sy, ex, ey; scanf("%d%d%d%d%d", &n, &sx, &sy, &ex, &ey); if(abs(sx - ex) + abs(sy - ey) <= 1) { printf("WHITE 1\n"); return 0; } printf("BLACK %d\n", solve(0, sx, sy, ex, ey)); return 0; } 5. 翻硬币 5.1 1-2翻硬币 博弈规则 给一排硬币，一些硬币正面朝上，每次可以翻1，2枚硬币，且最右边的硬币在翻动之前必须朝上。 问题求解 结论： sg[i] = i（表示只有i朝上时的sg） 整个局势的状态为sg的异或和。 sg[1] = 1; 对于sg[i]，可以转移到比它小的每一个j，因此sg[i] = i。 对于普通nim游戏：如果sg的异或和不为0，设二进制的最高位为a，b堆包含这一位，那么就可以在b堆中取走x个使得异或和为0。 对于翻硬币游戏：如果sg的异或和不为0，设二进制的最高位为a，b堆包含这一位，那么就可以翻转b位置硬币，然后反转b-x的位置，使得异或和为0。 5.2 1-2-3翻硬币 博弈规则 给一排硬币，一些硬币正面朝上，每次可以翻1，2，3枚硬币，且最右边的硬币在翻动之前必须朝上。 问题求解 结论 编号从0开始 如果一个数的二进制数中1出现了奇数次，那么为odious，否则为evil。 sg[i]为所有odious数，2i是odi时，为sg[i] = 2i；否则sg[i] = 2i +1;（因为2i的末尾必然为0，所以+1以后必然时odi） 证明 归纳证明sg是下一个odi a) sg[0] = 1, sg[1] = 2, sg[2] = 3; b) evil^evil = odi^odi = evil，evil ^odi = odi，因此任意一个evil可以由前面某两个odi数异或得到，但是odi不能由两个odi异或得到，所以sg是下一个odi。 5.3 任意翻硬币（ruler游戏） 5.3.1 一维任意翻硬币 博弈规则 给一排硬币，一些硬币正面朝上，每次可以翻任意连续区间的硬币，且最右边的硬币在翻动之前必须朝上。 问题求解 SG[x] = mex(0, SG[x - 1], SG[x - 1] ^ SG[x - 2], ……, SG[x -1] ^ SG[x - 2] ……^SG[1]) x12345678910111213SG1214121812141 结论：SG[x] = lowbit(x) 5.3.2 二维任意翻硬币 博弈规则 给一个矩阵的硬币，一些硬币正面朝上，每次可以翻任意连续子矩阵的硬币，且右下角的硬币在翻动之前必须朝上。 问题求解 当i = 1或j = 1时， S G ( i , j ) = l o w b i t ( i + j − 1 ) SG(i,j) = lowbit(i + j - 1) SG(i,j)=lowbit(i+j−1) 否则 S G ( i , j ) = 2 i + j − 2 SG(i,j) =2^{i+j-2} SG(i,j)=2i+j−2