這里是看了學長的例會以及挑戰上關于博弈的知識進行一下知識總結
1、PN法
定義：
必敗點P：位于此位置的人，在雙方操作均優的情況下，必敗，記作“0”
必勝點N：位于此位置的人，在雙方操作均優的情況下，必勝，記作“1”
性質：
游戲結束的點（通常為0點）均為必敗點
必勝點等價于必有一種方式可以到達必敗點
必敗點等價于所能到的點全為必勝點
2、巴什博弈
\(n\)個石子,A B兩個人取，操作者必須取\(1\sim m\)個石子，先取完獲勝
結論：必敗點 \(n\%\left(m+1\right)=0\) ? 必勝點\(n\%\left(m+1\right)\ne0\)
證明：（假設\(m=2\)）
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| PN | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
3、SG定理
- 局面的異或：對于平行關系下（也就是一個局面下）的\(sg\)值是所有局面下\(sg\)值的異或
即\(sg\left(n\right)= sg(s_1) \oplus sg(s_2) \oplus ...\oplus sg(s_n)\) - \(mex\)運算:\(mex(A)\)代表最小的不屬于A集合的自然數
即\(mex(A)=\{x|x\in\N \wedge\neg \left(\exist y\right)\left( y\in A \wedge y<x\right)\}\) - 當\(sg(n)=0\)時，必敗；\(sg(n)\ne0時\)，必勝
- 證明方法運用了類比（必勝點的轉移和數字的異或是否為0具有相似性）
一個其實用處不大的模板
博主實測，\(mex\)使用vis陣列速度遠快過set
int sg[maxn],f[maxn];
bool vis[maxn];
void get_sg()
{
memset(sg, 0, sizeof(sg));
for (int i = 1; i < maxn; ++i)
{
memset(vis,0,sizeof(vis));
for (int j = 0; j < N && f[j] <= i; ++j)
vis[sg[i - f[j]]];
for(int j=0;;++j)
if (!vis[j])
{
sg[i] = j;
break;
}
}
}
4、SG定理的應用
洛谷-P2197 Nim博弈（常規）
\(n\)堆石子，每堆有\(a[i]\)個，A B兩人輪流取，每次可以在一堆石子中取任意個（可一次性取完）最后率先取完者獲勝
結論：直接套用\(sg\)定理，可以發現每堆石子的\(sg\)值恰好為擁有石子的個數，再求異或和即可
HDU-2873 Bomb Game（搜索求SG值）
結論：利用記憶化搜索求得SG值
#include<bits/stdc++.h>
using namespace std;
int sg[55][55];
int get_sg(int x, int y)
{
if (~sg[x][y])
return sg[x][y];
bool vis[3000] = {0};
if (x > 1 && y > 1)
{
for (int i = 1; i < x; ++i)
for (int j = 1; j < y; ++j)
vis[get_sg(i, y)^get_sg(x, j)]=true;
}
else if (y == 1 && x > 1)
for (int i = 1; i < x; ++i)
vis[get_sg(i, 1)]=true;
else if (x == 1 && y > 1)
for (int i = 1; i < y; ++i)
vis[get_sg(1, i)]=true;
for (int i = 0;; ++i)
if (vis[i] == false)
return sg[x][y] = i;
}
char s[55];
int main()
{
int n, m;
memset(sg, -1, sizeof(sg));
sg[1][1] = 0;
while (~scanf("%d%d", &n, &m) && n + m)
{
int ans = 0;
for (int i = 1; i <= n; ++i)
{
scanf("%s", s + 1);
for (int j = 1; j <= m; ++j)
if (s[j] == '#')
ans ^= get_sg(i, j);
}
printf("%s\n", ans ? "John" : "Jack");
}
}
Gym-101908B Marbles（SG必敗點變形）
結論：根據題意可知，盡管\((0,0)\)為初始必敗點，但是只需要移動一個彈珠到終點便可勝利，于是可知只有當所有彈珠移動到下一組初始必敗點\((1,2)\)和\((2,1)\)時才能決定雙方的勝負關系
注意： 這里通過將? “存在一個即獲得勝利”\(\rightarrow\)"所有都到達某條件才獲得勝利"的思想，使得可以通過\(sg\)定理求解
#include<bits/stdc++.h>
using namespace std;
int sg[105][105];
bool vis[10005];
void get_sg()
{
for (int i = 1; i <= 100; ++i)
{
for (int j = 1; j <= 100; ++j)
{
if (i == j) continue;
memset(vis, 0, sizeof(vis));
for (int k = 1; k <= max(i, j); ++k)
{
if (i - k >= 1 && i - k != j) vis[sg[i - k][j]] = true;
if (j - k >= 1 && j - k != i) vis[sg[i][j - k]] = true;
if (i - k >= 1 && j - k >= 1) vis[sg[i - k][j - k]] = true;
}
for (int k = 0;; ++k)
if (!vis[k])
{
sg[i][j] = k;
break;
}
}
}
}
int main()
{
int N;
int a, b;
bool ok = 0;
int ans = 0;
get_sg();
scanf("%d", &N);
while (N--)
{
scanf("%d%d", &a, &b);
ans ^= sg[a][b];
ok |= a == b;
}
printf("%c", ans || ok ? 'Y' : 'N');
}
HDU-1907 John（anti-SG）
結論：將\(Nim\)博弈變形為誰最先取光誰輸，那么如果至少有一個子游戲的\(sg\)值大于1，則就當作普通的\(Nim\)進行處理，否則反過來，\(sg\)值為0時為必勝
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T, n, t;
int ans;
bool ok;
scanf("%d", &T);
while (T--)
{
ans = ok = 0;
scanf("%d", &n);
while (n--)
{
scanf("%d", &t);
ans ^= t;
if (t > 1)
ok = true;
}
printf("%s\n", ok == (bool)ans ? "John" : "Brother");
}
}
HDU-3595 GG and MM（every-SG）
結論：多執行緒博弈，所有游戲都無法繼續進行時，游戲結束，對于每一個子游戲，如果自己是必敗的，那么希望越快結束越好，自己是必勝的，那么希望越慢結束越好，
\[\begin{cases} step[i]=\max+1 &\text{if i is determined to win }\\ step[i]=\min+1 &\text{if i is determined to lose} \end{cases}\]最后檢測最大步數是否為奇數，奇數則必勝，反之必敗
#include<bits/stdc++.h>
using namespace std;
int step[1005][1005];
int pn[1005][1005];
int get_step(int x, int y)
{
if (~pn[x][y])
return pn[x][y];
if (x > y) swap(x, y);
int mx = 0, mn = 0x3f3f3f3f;
pn[x][y] = pn[y][x] = false;
for (int i = x; i <= y; i += x)
{
if (!get_step(x, y - i))
{
mx = max(mx, step[x][y - i]);
pn[x][y] = pn[y][x] = true;
}
else
mn = min(mn, step[x][y - i]);
}
if (pn[x][y])
step[x][y] = step[y][x] = mx + 1;
else
step[x][y] = step[y][x] = mn + 1;
return pn[x][y];
}
int main()
{
memset(pn, -1, sizeof(pn));
for (int i = 0; i <= 1000; ++i)
pn[i][0] = pn[0][i] = step[i][0] = step[0][i]=0;
int n, a, b;
while (~scanf("%d", &n))
{
int mx = 0;
while (n--)
{
scanf("%d%d", &a, &b);
get_step(a, b);
mx = max(mx, step[a][b]);
}
if (mx & 1)
printf("MM\n");
else
printf("GG\n");
}
}
POJ-2484 A Funny Game（環形博弈）
結論：假設有\(n\)個石子，能取連續\(1\sim k\)個石子
\[\begin{cases} First\ hand\ win&\text{if $k\ge n\vee \left(k=1\wedge k \text{ is odd} \right)$}\\ Second\ hand\ win&\text{else} \end{cases}\]證明：如果第一步不能取完，那么第二步就可以將環形圈分段為size(假設為\(x\))相同的兩部分，由\(sg[x]\oplus sg[x]=0\) 可以看出，這樣可以使得下一步必敗
#include<cstdio>
#include<cstdio>
bool circle_game(int n, int k)
{
if (k >= n || k == 1 && (n & 1)) return true;
return false;
}
int main()
{
int n;
while (~scanf("%d", &n) && n)
printf("%s\n", circle_game(n, 2) ? "Alice" : "Bob");
}
HDU-3389 Game（階梯博弈）
結論：
- 對所有奇數層進行\(Nim\)博弈即可
- 偶數層可以移動到除0外的任何層
- 奇數層可以移動石子到任意偶數層（包括第0層）
可以打表出可移動層
| A | B | A | B | A | B | A | B |
|---|---|---|---|---|---|---|---|
| 1 | \ | 5 | 4 | 9 | 6 | 13 | 2、8 |
| 2 | 1 | 6 | 3 | 10 | 5 | 14 | 1、7、13 |
| 3 | \ | 7 | 2 | 11 | 4、10 | 15 | 6、12 |
| 4 | \ | 8 | 1、7 | 12 | 3、9 | 16 | 5、11 |
此題通過打表可以發現1、3、4三層是無法挪動的，即有3個第0層
| 層數 | 0 | 1 | 2 | 3 | 4 | 5 | ... |
|---|---|---|---|---|---|---|---|
| 游戲1 | 1 | 2 | 7 | 8 | 13 | 14 | 奇數層為\(2+6i\) |
| 游戲2 | 3 | 6 | 9 | 12 | 15 | 18 | 奇數層為\(6+6i\) |
| 游戲3 | 4 | 5 | 10 | 11 | 16 | 17 | 奇數層為\(5+6i\) |
#include<cstdio>
int main()
{
int T, n, t;
scanf("%d", &T);
for (int cas = 1; cas <= T; ++cas)
{
int sg[3] = { 0 };
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &t);
switch (i % 6)
{
case 0:sg[0] ^= t; break;
case 2:sg[1] ^= t; break;
case 5:sg[2] ^= t;
}
}
printf("Case %d: %s\n", cas, sg[0] ^ sg[1] ^ sg[2] ? "Alice" : "Bob");
}
}
luogu-P2252 取石子游戲（威佐夫博弈）
結論：假設兩堆各有 \(a\ b\) 個石子
\[\begin{cases} First\ hand\ win&\text{if $ \frac{(b-a)\times(1.0+\sqrt{5.0})}{2.0}=a$}\\ Second\ hand\ win&\text{else} \end{cases}\]//做題頭
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a, b;
scanf("%d%d", &a, &b);
if (a > b)
swap(a, b);
printf("%d",int((sqrt(5) + 1) / 2 * (b - a)) != a);
}
5、K倍動態減法游戲
假設有\(n\)個石子，第一次能取\(1\sim n-1\)個，若每次取\(x\)個，則下一次可以取\(1\sim kx\)個
結論：假設存在一個必敗序列\(a[i]\)，使得必敗數列能夠造出來的最大的數不超過已構造出最大的必敗序列中的數，這個數用\(b[i]\)進行存盤，而\(a[i+1]=b[i]+1\)，又通過推理可知，設\(a[t]*k<a[i]\),可以得到 \(b[i]=a[i]+b[t]\)（另外初始化 \(a[0]=b[0]=0\)）
哎自己也不是太懂，希望以后能理解吧，現在就死記著板子~
struct kmuti_game
{
static const int MAXN = 1e5;
int a[MAXN] = { 1 }, b[MAXN] = { 1 };
void init(int k)
{
int j;
for (int i = 1; i < MAXN; ++i)
{
a[i] = b[i - 1] + 1;
for (j = 0; j < MAXN || a[j + 1] * k < a[i]; ++j);
if (a[j] * k < a[i])
b[i] = b[i - 1] + a[i];
else
b[i] = a[i];
}
}
};
6、翻硬幣類游戲
結論：
- 當x的二進制1個數為奇數個時，\(sg[x]=2x\)
- 當x的二進制1個數為偶數個時，\(sg[x]=2x+1\)
也不太懂 QAQ 待補
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205593.html
標籤：其他
下一篇：ServiceMesh案例