在蔡大神的论文+讲解和HZW的题库下，自己大概是明白什么是博弈论的皮毛了吧。
先说SG定理吧。
对于游戏中的状态，我们给每个状态定义一个必胜态和必败态。区别在于前者可以通过一次操作到达必败态，但后者无法做到（后者在一次操作后所能到达的状态全部都为必胜态）
接着引进SG函数，每个状态都有一个SG值，这个值由它所能到达的状态的SG值决定。（这里的所能到达的状态指的是经过一次操作能到达的状态，下同）
SG值有以下性质：
- SG值始终为非负整数。
- 每个状态的SG都与它能到达的状态的SG值不相同。
- 在满足上面两个条件的情况下SG值应该尽量小。
我们会发现，SG=0的状态为必败态，SG≠0的即为必胜态。
SG定理：对于一个组合游戏，它状态的SG值即为各个子游戏状态的SG值的异或和（Nim和）。
反胜利条件：上面的必胜和必败都是基于“无法操作者败”这个规则来解释的。若某组合游戏的胜利条件是“无法操作者胜”的话，必胜态必须满足：
- SG异或和>0且石子数大于1的堆数>0
- SG异或和=0且石子数大于1的堆数=0
其余的就是必败态了。
Nim阶梯：不懂。。。反正有这种东西就对了。
Every-SG游戏：每个子游戏必须同时进行的组合游戏。
设D(T)，当游戏T为先手必胜时D为最长回合数，当T为先手必败时D为最短回合数。
必胜条件当且仅当Dmax为奇数。
常见的几种公平游戏：
Nim游戏：有N堆石子，每次可从一堆石子中拿走任意数量的石子。
解法：把每堆石子看成子游戏，其SG值等于其石子数。
图上移子游戏：一个有向图上有一个棋子沿着有向边移动。
解法：赤裸裸的SG定理直接用。
树上删边：N棵树，不断删边，每次删边也会把删完无法与根相连的子树删去。
解法：把树上的每个点看成一个组合游戏，它的儿子就是子游戏。
图上删边：上一题的升级版，这次图中可以出现环。
解法：先缩环，奇数边环缩成一条边，偶数边环缩成一个点。接着解法同上题。
NimK游戏：Nim的升级版，每次可从K堆拿走任意数量的石子。
解法：把N堆石子的石子数用二进制表示，统计每一个二进制位上的1的个数，若每一位上1的个数mod(k + 1)全为0，则必败，否则必胜。（）
BZOJ 2281: [SDOI2011]黑白棋
为什么我的第一题都是最丧病的逗QAQ
首先，我们会发现，白棋必须往右移，黑棋必须往左移（最优策略），而且当黑白棋两两紧靠时就是必败态。
这样我们可以把第i个白棋和第i个黑棋之间的空格看成第i个石子堆，问题即可转化成NimK问题。
然后用组合数学算出必败态的方案数，再用总方案数减去必败方案数即可得到必胜方案数。
博弈论+组合数学+DP。。。
我要吐了。。。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define ll long long#define maxn 10009#define MAX 1<<30#define Q 1000000007using namespace std;int n, k, d, bin[16];ll dp[maxn], c[maxn][105], ans;void Add(ll &a, ll b) { a=(a+b)%Q; }int C(int a, int b){ if (b>a-b) b = a-b; return c[a][b];}int main(){ scanf("%d%d%d", &n, &k, &d); k/=2; rep(i, 0, n) c[i][0] = 1; rep(i, 0, n) rep(j, 1, min(i, k*2)) c[i][j] = (c[i-1][j-1]+c[i-1][j])%Q; dp[0] = 1; bin[1] = 1; rep(i, 2, 15) bin[i] = bin[i-1]*2; rep(i, 0, 14) down(j, n-k*2, 0) { int q = 1; while (q*(d+1)*bin[i+1]+j <= n-k*2 && q*(d+1) <= k) { Add(dp[q*(d+1)*bin[i+1]+j], dp[j]*C(k,q*(d+1))); q++; } } rep(i, 0, n-k*2) Add(ans, dp[i]*C(n-i-k,k)); ans = (C(n,k*2)%Q+Q-ans)%Q; printf("%lld", ans); return 0;}
BZOJ 2281: Nim
第一眼看到名字，以为真的是赤裸裸的Nim问题，结果还是被骗了。
尼玛这不就是一道数据结构题吗，维护一棵树支持点修改和链查询。。。
逗比的我用了树链剖分，硬是把DFS序的功能忘得一干二净QAQ
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define ll long long#define maxn 10009#define MAX 1<<30#define Q 1000000007using namespace std;int n, k, d, bin[16];ll dp[maxn], c[maxn][105], ans;void Add(ll &a, ll b) { a=(a+b)%Q; }int C(int a, int b){ if (b>a-b) b = a-b; return c[a][b];}int main(){ scanf("%d%d%d", &n, &k, &d); k/=2; rep(i, 0, n) c[i][0] = 1; rep(i, 0, n) rep(j, 1, min(i, k*2)) c[i][j] = (c[i-1][j-1]+c[i-1][j])%Q; dp[0] = 1; bin[1] = 1; rep(i, 2, 15) bin[i] = bin[i-1]*2; rep(i, 0, 14) down(j, n-k*2, 0) { int q = 1; while (q*(d+1)*bin[i+1]+j <= n-k*2 && q*(d+1) <= k) { Add(dp[q*(d+1)*bin[i+1]+j], dp[j]*C(k,q*(d+1))); q++; } } rep(i, 0, n-k*2) Add(ans, dp[i]*C(n-i-k,k)); ans = (C(n,k*2)%Q+Q-ans)%Q; printf("%lld", ans); return 0;}
BZOJ 2463: [中山市选2009]谁能赢呢？
判断奇偶即可。
证明：用多米诺铺满棋盘，然后自行观察。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define ll long long#define maxn 10009#define MAX 1<<30#define Q 1000000007using namespace std;int n, k, d, bin[16];ll dp[maxn], c[maxn][105], ans;void Add(ll &a, ll b) { a=(a+b)%Q; }int C(int a, int b){ if (b>a-b) b = a-b; return c[a][b];}int main(){ scanf("%d%d%d", &n, &k, &d); k/=2; rep(i, 0, n) c[i][0] = 1; rep(i, 0, n) rep(j, 1, min(i, k*2)) c[i][j] = (c[i-1][j-1]+c[i-1][j])%Q; dp[0] = 1; bin[1] = 1; rep(i, 2, 15) bin[i] = bin[i-1]*2; rep(i, 0, 14) down(j, n-k*2, 0) { int q = 1; while (q*(d+1)*bin[i+1]+j <= n-k*2 && q*(d+1) <= k) { Add(dp[q*(d+1)*bin[i+1]+j], dp[j]*C(k,q*(d+1))); q++; } } rep(i, 0, n-k*2) Add(ans, dp[i]*C(n-i-k,k)); ans = (C(n,k*2)%Q+Q-ans)%Q; printf("%lld", ans); return 0;}
POJ 3537: Crosses and Crosses
初始时为状态N，假设我们在第K格中打叉，那么状态N会分裂成状态K-3和状态N-K-2。SG定理搞。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 2345#define MAX 1<<30using namespace std;int n, sg[maxn];int Win(int n){ if (n<0) return 0; if (sg[n]>=0) return sg[n]; else sg[n] = 0; bool b[maxn]; rep(i, 0, maxn) b[i] = 0; rep(i, 1, n) b[Win(i-3) ^ Win(n-i-2)] = 1; while (b[sg[n]]) sg[n]++; return sg[n];}int main(){ scanf("%d", &n); rep(i, 0, n) sg[i] = -1; if (Win(n)) printf("1\n"); else printf("2\n"); return 0;}
BZOJ 1188: [HNOI2007]分裂游戏
子游戏即每颗豆子。状态分裂+SG定理。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 2345#define MAX 1<<30using namespace std;int t, n, sg[maxn], q[maxn], a, ans;int Cal(int x){ if (sg[x]>=0) return sg[x]; else sg[x] = 0; bool b[99]; rep(i, 0, 99) b[i] = false; rep(i, 1, x-1) rep(j, 1, x-1) b[Cal(i) ^ Cal(j)] = true; while (b[sg[x]]) sg[x]++; return sg[x];}int main(){ rep(i, 1, 21) sg[i] = -1; t = Cal(21); scanf("%d", &t); while (t--) { scanf("%d", &n); down(i, n, 1) scanf("%d", &q[i]); a = ans = 0; rep(i, 1, n) if (q[i]%2) a ^= sg[i]; if (!a) { printf("-1 -1 -1\n0\n"); continue; } down(i, n, 2) if (q[i]) down(j, i-1, 1) down(k, j, 1) if ((sg[i]^sg[j]^sg[k]) == a) { if (!ans) printf("%d %d %d\n", n-i, n-j, n-k); ans++; } printf("%d\n", ans); } return 0;}
POJ 3710: Christmas Game
图上删边游戏。
但这道题的图比普通图多了一个定义：每个环上只有一个度数大于2的点。所以我们可以利用这个特性来缩环。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 1234#define MAX 1<<30using namespace std;struct edge { int y, n;} e[maxn]; int t, n, m, q, x, y, ans, fir[maxn], sg[maxn], h[maxn], b[maxn];int Cal(int l, int x){ int o = fir[x], y = e[o].y; b[x] = l; while (o) { if (y != h[x] && b[y] && b[y] < l) return sg[x] = (l-b[y])%2 ? b[y]-l : b[y]-l+1; if (!b[y] || b[y] == l+1) { h[y] = x; sg[x] ^= Cal(l+1, y)+1; } o = e[o].n, y = e[o].y; } return sg[x];}int main(){ while (scanf("%d", &t) != EOF) { ans = 0; while (t--) { scanf("%d %d", &m, &n); rep(i, 1, m) sg[i] = fir[i] = h[i] = b[i] = 0; m = 0; rep(i, 1, n) { scanf("%d %d", &x, &y); e[++m].y = y; e[m].n = fir[x]; fir[x] = m; e[++m].y = x; e[m].n = fir[y]; fir[y] = m; } ans ^= Cal(1, 1); } if (ans) printf("Sally\n"); else printf("Harry\n"); } return 0;}
POJ 1704: Georgia and Bob
Nim阶梯的应用，两两分组转成Nim游戏。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 1234#define MAX 1<<30using namespace std;int t, n, a, k[maxn];int main(){ scanf("%d", &t); while (t--) { scanf("%d", &n); a = 0; rep(i, 1, n) scanf("%d", &k[i]); sort(k+1, k+1+n); for (int i=n; i>0; i-=2) a ^= k[i]-k[i-1]-1; if (a) printf("Georgia will win\n"); else printf("Bob will win\n"); } return 0;}
POJ 3480: John
Nim阶梯的应用，两两分组转成Nim游戏。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 123#define MAX 1<<30using namespace std;int t, n, ans, a[maxn], b;int main(){ scanf("%d", &t); while (t--) { scanf("%d", &n); ans = b = 0; rep(i, 1, n) scanf("%d", &a[i]); rep(i, 1, n) ans ^= a[i]; rep(i, 1, n) if (a[i]>1) b++; if (!ans && !b) printf("John\n"); else if (ans && b) printf("John\n"); else printf("Brother\n"); } return 0;}
POJ 2068: Nim
Nim的变种。SG定理搞。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 12345#define MAX 1<<30using namespace std;int n, s, q[23], b[23][maxn];int Find(int x, int l){ if (b[x][l]) return b[x][l]; rep(i, 1, min(l, q[x])) if (Find(x+1>n*2?1:x+1, l-i) == 1) return b[x][l] = 2; return b[x][l] = 1;}int main(){ scanf("%d", &n); while (n) { scanf("%d", &s); rep(i, 1, n*2) rep(j, 1, s) b[i][j] = 0; rep(i, 1, n*2) b[i][0] = 2; rep(i, 1, n*2) scanf("%d", &q[i]); printf("%d\n", Find(1, s)-1); scanf("%d", &n); } return 0;}
POJ 2960: S-Nim
Nim的变种。依旧SG定理搞。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 12345#define MAX 1<<30using namespace std;int t, n, m, s[123], a, sg[12345], ans;int main(){ scanf("%d", &m); while (m) { rep(i, 1, m) scanf("%d", &s[i]); rep(x, 0, 10000) { bool b[123]; sg[x] = 0; rep(i, 0, 100) b[i] = false; rep(i, 1, m) if (s[i]<=x) b[sg[x-s[i]]] = true; while (b[sg[x]]) sg[x]++; } scanf("%d", &t); rep(i, 1, t) { scanf("%d", &n); ans = 0; rep(i, 1, n) { scanf("%d", &a); ans ^= sg[a]; } if (ans) printf("W"); else printf("L"); } printf("\n"); scanf("%d", &m); } return 0;}
POJ 2484: A Funny Game
先考虑链的SG值，再求初始状态的SG值。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 12345#define MAX 1<<30using namespace std;int t, n;int main(){ scanf("%d", &n); while (n) { if (n < 3) printf("Alice\n"); else printf("Bob\n"); scanf("%d", &n); } return 0;}
POJ 2505: A multiplication game
2-9：必胜
10-18：必败
19-162：必胜
163-324：必败
……
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 12345#define MAX 1<<30using namespace std;long long n, a;int main(){ while (scanf("%lld", &n) != EOF) { a = 9; while (n > a*2) a *= 18; if (n <= a) printf("Stan wins.\n"); else printf("Ollie wins.\n"); } return 0;}
POJ 2425: A Chess Game
图上移子游戏。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 1234#define MAX 1<<30using namespace std;struct e{ int y, n;} e[1234567]; int f[maxn];int n, m, k, a, ans, sg[maxn];int Cal(int x){ if (sg[x]>=0) return sg[x]; else sg[x] = 0; bool b[maxn]; rep(i, 0, n) b[i] = false; int o = f[x]; while (o) { b[Cal(e[o].y)] = true; o = e[o].n; } while (b[sg[x]]) sg[x]++; return sg[x];}int main(){ while (scanf("%d", &n) != EOF) { rep(i, 0, n-1) f[i] = 0, sg[i] = -1; rep(x, 0, n-1) { int y; scanf("%d", &k); rep(i, 1, k) { scanf("%d", &y); e[++m].y = y, e[m].n = f[x], f[x] = m; } } rep(i, 0, n-1) if (sg[i] < 0) sg[i] = Cal(i); scanf("%d", &k); while (k) { ans = 0; rep(i, 1, k) { scanf("%d", &a); ans^=sg[a]; } if (ans) printf("WIN\n"); else printf("LOSE\n"); scanf("%d", &k); } } return 0;}
POJ 2975: Nim
普通Nim。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 1234#define MAX 1<<30using namespace std;int n, a[maxn], ans, m;int main(){ scanf("%d", &n); while (n) { rep(i, 1, n) scanf("%d", &a[i]); ans = m = 0; rep(i, 1, n) ans ^= a[i]; rep(i, 1, n) if (a[i] >= (a[i]^ans)) m++; if (!ans) m = 0; printf("%d\n", m); scanf("%d", &n); } return 0;}
POJ 1740: A New Stone Game
Nim+移子游戏。
游戏状态的必胜必败性可分成奇数堆和偶数堆来看。
偶数堆的话若能两两分组且每组的石子数都相等的话则为必败态（想想全部堆为空的情况）其余的为必胜态。
奇数堆全部都是必胜态。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 123#define MAX 1<<30using namespace std;int n, a[maxn], b[maxn];bool e;int main(){ scanf("%d", &n); while (n) { rep(i, 0, 100) b[i] = 0; rep(i, 1, n) scanf("%d", &a[i]); if (n%2) printf("1\n"); else { rep(i, 1, n) b[a[i]]++; e = false; rep(i, 0, 100) if (b[i]%2) e = true; if (e) printf("1\n"); else printf("0\n"); } scanf("%d", &n); } return 0;}
POJ 2234: Matches Game
普通Nim。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 123#define MAX 1<<30using namespace std;int n, a, ans, b;bool e;int main(){ while (scanf("%d", &n) != EOF) { ans = b = 0; rep(i, 1, n) { scanf("%d", &a); ans ^= a; if (a>1) b++; } if ((ans && b) || (!ans && !b)) printf("Yes\n"); else printf("No\n"); } return 0;}
CF 493D: Matches Game
判断棋盘奇偶性即可。
证明：若是奇数则必败，因为对手可以模仿你的动作（沿中轴对称模仿）。若偶数时向右移一步则变成对手的必败态了。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 100009#define MAX 1<<30using namespace std;int n, m;int main(){ scanf("%d", &n); if (n&1) printf("black\n"); else printf("white\n1 2\n"); return 0;}
CF 451A: Matches Game
一眼题，看行列的最小值的奇偶性。
#include#include #include #include #include #include #include #include #define rep(i, l, r) for(int i = l; i <= r; i++)#define down(i, l, r) for(int i = l; i >= r; i--)#define maxn 100009#define MAX 1<<30using namespace std;int n, m;int main(){ scanf("%d%d", &n, &m); if (min(n, m)&1) printf("Akshat"); else printf("Malvika"); return 0;}
共18道题。。。