组合博弈入门

一、博弈论三条性质：

终结点为P点

P点只能到N点

N点至少有一种途径到P点

N：必胜态 P：必败态

1、引导题

1846 Brave Game

题目大意：n个石子两人轮流取1~m个，最后取空的胜利n：23 m：20：P//终结点1：N2：N3：P4：N5：N6：P结论： x % (m + 1) == 0 则为P点

#include <iostream>#include <cstdio>using namespace std;int main() {int t, n, m;cin >> t;while (t--) {cin >> n >> m;cout << (n % (m + 1) ? "first" : "second") << endl;}return 0;}

2、引导题

1847 Good Luck in CET-4 Everybody!

题目大意：n张纸牌两人轮流取2的幂次(1, 2, 4, 8, 16……),最后取空的胜利同理上一题取石子0 1 2 3 4 5 6 7 8 9 10 11 12 13P N N P N N P N N P N N P N结论： n % 3 == 0 则为P点

#include <iostream>#include <cstdio>using namespace std;int main() {int n;while (cin >> n) {cout << ((n % 3) ? "Kiki" : "Cici") << endl;}return 0;}

二、NIM博弈

定理：如果先手必胜，则有 A 1 x o r A 2 x o r . . . A n ≠ 0 A_1\ xor \ A_2\ xor\ ...\ A_n\ \ne\ 0 A1​xorA2​xor...An​=0

就是控0，所有堆都为空时异或为0。只要还剩石子，并且异或为0，那么至少还有两堆，或者说一次必取不完局面。就把这种局面一直扔给对手，使自己保证永远不败状态，此时无论对手怎么取，异或都不为0。

27: 11011 num[0] 8: 01000 num[1]20: 10100 num[2]13: 01101 num[3]---- ^10: 01010 sumnim[i] > (nim[i] ^ sum) 为可选方案 注意：运算符优先级nim[i] = nim[i] ^ sum 为具体调整方案

1、先手状态判定

1849 Rabbit and Grass

题目大意：n堆石子，两人轮流选一堆取走任意个，最后取空的胜利，问先手必赢还是必输解题思路：NIM博弈

#include <iostream>#include <cstdio>using namespace std;int main() {int n;while (cin >> n && n) {int Xor = 0, x;while (n--) {cin >> x;Xor ^= x;}cout << (Xor ? "Rabbit Win!" : "Grass Win!") << endl;}return 0;}

2、先手必胜第一手方案数

1850 Being a Good Boy in Spring Festival

题目大意：nim博弈如果先手必胜的话，那么输出第一步用多少种选择。反之先手必败输出0

#include <iostream>#include <cstdio>using namespace std;#define N 100int nim[N + 10];int main() {int n;while (scanf("%d", &n) && n) {int sum = 0, ans = 0;for (int i = 0; i < n; ++i) {scanf("%d", nim + i);sum ^= nim[i];}for (int i = 0; i < n; ++i) {if (nim[i] > (nim[i] ^ sum)) ++ans;//nim[i] = nim[i] ^ sum 为具体调整方案}printf("%d\n", ans);}return 0;}

三、SG函数

有向图游戏

​ 给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

​ **任何一个公平组合游戏都可以转化为有向图游戏。**具体方法是,把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

​ 设 S S S​​​ 表示一个非负整数集合。定义 M e x ( S ) Mex(S) Mex(S)​ 为求出不属于集合 S S S​ 的最小非负整数的运算。

SG函数

​ 在有向图游戏中，对于每个节点 x x x , 设从 x x x 出发共有 k k k 条有向边，分别到达节点 y 1 , y 2 , . . . , y k y_1,y_2,...,y_k y1​,y2​,...,yk​，定义 S G ( x ) SG(x) SG(x)为 x x x 的后继节点 y 1 , y 2 , . . . , y k y_1,y_2,...,y_k y1​,y2​,...,yk​ 的 S G SG SG函数值构成的集合再执行$Mex\ ​运算的结果，即 ​运算的结果，即 ​运算的结果，即SG(x)=Mex({SG(y_1),SG(y_2),…,SG(y_k)})$​

​ 特别的，整个有向图游戏 G G G​​​ 的 S G SG SG 函数值被定义为有向图游戏起点 s s s 的 S G SG SG 函数值，即 S G ( G ) = S G ( s ) SG(G) = SG(s) SG(G)=SG(s)​

​ 有向图游戏的和：设 G 1 , G 2 , . . . , G m G_1, G2, ... ,G_m G1​,G2,...,Gm​​是 m m m​ 个有向图游戏。定义有向图游戏 G G G​，它的行动规则是任选某个有向图游戏 G i G_i Gi​​，并在 G i G_i Gi​​上行动一步。 G G G​ 被称为有向图游戏 G 1 , G 2 , … , G m G_1,G_2,…,G_m G1​,G2​,…,Gm​​ 的和

​ 有向图游戏的和的 S G SG SG​​函数值等于它包含的各个子游戏 S G SG SG​函数值的异或和，即: S G ( G ) = S G ( G 1 ) x o r S G ( G 2 ) x o r . . . x o r S G ( G m ) SG(G)= SG(G_1) \ xor\ SG(G_2) \ xor\ ...\ xor\ SG(G_m) SG(G)=SG(G1​)xorSG(G2​)xor...xorSG(Gm​)​

​ 定理

​有向图游戏的某个局面必胜，当且仅当该局面对应节点的 S G SG SG​​函数值大于 0 0 0

​有向图游戏的某个局面必败，当且仅当该局面对应节点的 S G SG SG​函数值等于 0 0 0​

​ 我们不再详细证明该定理。读者可以这样理解:

​ 在一个没有出边的节点上，棋子不能移动，它的 S G SG SG​​​​​​值为 0 0 0​​​​​​，对应必败局面。若一个节点的某个后继节点 S G SG SG​​​​​​值为 0 0 0​​​​​​，在$\ Mex\ ​​​​​​运算后，该节点的 ​​​​​​运算后，该节点的 ​​​​​​运算后，该节点的SG$​​​​​​值大于 0 0 0​​​​​​.这等价于，若一个局面的后继局面中存在必败局面，则当前局面为必胜局面。

​ 若一个节点的后继节点 S G SG SG​​​​值均不为 0 0 0​​​，在$\ Mex\ ​运算后，该节点的 ​运算后，该节点的 ​运算后，该节点的SG$​值为 0 0 0。这等价于，若一个局面的后继局面全部为必胜局面，则当前局面为必败局面。

1、多堆取石子

1848 Fibonacci again and again

题目大意：三堆石子，两人轮流取f个，最后取空的胜利f[1] = 1, f[2] = 2, f[3] = 3, f[4] = 5, ... , f[n] = f[n - 1] + f[n - 2]解题思路：SG函数

#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define N 1000int SG[N + 10], flag[N + 10], fib[N];void Get_Fib() {fib[1] = 1;fib[2] = 2;for (int i = 3; fib[i - 1] < N; ++i) fib[i] = fib[i - 1] + fib[i - 2];return ;}void Get_SG() {for (int i = 1; i <= N; ++i) {memset(flag, 0, sizeof(flag));for (int j = 1; i - fib[j] >= 0; ++j) flag[SG[i - fib[j]]] = 1;int ind = 0;while (flag[ind]) ++ind;SG[i] = ind;}return ;}int main() {Get_Fib();Get_SG();int m, n, p;while(scanf("%d%d%d", &m, &n, &p) && m && n && p) {printf("%s\n", SG[m] ^ SG[n] ^ SG[p] ? "Fibo" : "Nacci");}return 0;}

2、拍卖会

2149 Public Sale

题目大意：底价为0，轮流加价1~m，率先加到不小于n的胜利。依次输出先手必胜的情况第一次可以叫的价钱，如果先手必败输出none解题思路：以终点n作为博弈起点，倒序求SG值SG yyds！

#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define N 1100int SG[N + 10], flag[N + 10];void Get_SG(int n, int m) {for (int i = n; i > 0; --i) {memset(flag, 0, sizeof(flag));for (int j = 1; j <= m && i + j <= n; ++j) {flag[SG[i + j]] = 1;}for (int j = 0; ; ++j) {if (flag[j] == 0) {SG[i] = j;break;}}}return ;}int main() {int n, m;while (~scanf("%d%d", &n, &m)) {if (m >= n) {for (int i = n; i <= m; ++i) {if (i - n) putchar(' ');printf("%d", i);}putchar('\n');continue;}Get_SG(n, m);bool is = true;for (int i = 1; i <= m; ++i) {if (SG[i]) continue;if (!is) putchar(' ');printf("%d", i);is = false;}if (is) printf("none\n");else putchar('\n');}return 0;}

3、志愿者选拔

2188 悼念512汶川大地震遇难同胞——选拔志愿者

题目大意：低价为0，轮流加价1~m，率先加到不小于n的胜利。先手必胜输出Grass，反之Rabbit

#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define N 10000#define M 10 //注意这里可以节约空间花销，m<=10,一个点最多十个后继，SG值不可能大于等于10int SG[N + 10], flag[M + 10];void Get_SG(int n, int m) {for (int i = n; i > 0; --i) {memset(flag, 0, sizeof(flag));for (int j = 1; j <= m && i + j <= n; ++j) {flag[SG[i + j]] = 1;}for (int j = 0; ; ++j) {if (flag[j]) continue;SG[i] = j;break;}}return ;}int main() {int t, n, m;cin >> t;while (t--) {scanf("%d%d", &n, &m);if (m >= n) printf("Grass\n");else {Get_SG(n, m);bool is = 0;for (int i = 1; i <= m; ++i) {if (SG[i]) continue;is = 1;break;}printf("%s\n", is ? "Grass" : "Rabbit");}}return 0;}

4、组合博弈

1536 S-Nim

1944 S-Nim

题目大意：5 1 2 3 4 5 //5种取子规则3 //3次询问2 5 12 //第一次 2堆石子 分别5和12块石子3 2 4 7 //第二次4 2 3 7 12 //第三次0 //输入0结束记忆化搜索SG值，只计算用到的SG值，没有用到的SG值不计算，减少了部分时间开销

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 10000#define M 100int vis[M + 5], SG[N + 5]; //vis取子规则 int Get_SG(int x, int &k) {if (~SG[x]) return SG[x];int flag[M + 5] = {0};for (int i = 1; i <= k && x - vis[i] >= 0; ++i) {flag[Get_SG(x - vis[i], k)] = 1;}int ind = 0;while (flag[ind]) ++ind;return SG[x] = ind;}int main() {int k, t;while (scanf("%d", &k) && k) {memset(SG, -1, sizeof(SG));SG[0] = 0;for (int i = 1; i <= k; ++i) scanf("%d", vis + i);sort(vis + 1, vis + k + 1); //取子规则需提前排序scanf("%d", &t);while (t--) {int n, Xor = 0;scanf("%d", &n);for (int i = 1, x; i <= n; ++i) {scanf("%d", &x);Xor ^= Get_SG(x, k);}printf("%c", Xor ? 'W' : 'L');}putchar('\n');}return 0;}