SG函数

在讲解SG函数之前先了解一下必胜点和必败点,也就是所谓的必胜态和必败态。

P点(必败点):当你处于这个情况的时候,无论进行怎样的操作,对方都能取胜。

N点(必胜点):当你处于这个情况的时候,你能进行恰当的操作,保证一定能取胜。

必胜点和必败点的性质:

1、所有终结点是必败点P。(一般都是以此为基本前提进行推理,换句话说,我们以此为假设)。

2、从任何必胜点N操作,至少有一种方式可以进入必败点P。

3、无论如何操作,必败点P都只能进入必胜点N。

算法介绍

SG函数

在讲解SG函数之前先介绍mex运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如$mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0$。

对于任意状态 x , 定义$SG(x) = mex(S)$,其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为$SG(a),SG(b),SG(c)$,那么$SG(x) = mex{SG(a),SG(b),SG(c)}$。 这样集合S的终态必然是空集,所以SG函数的终态为$SG(x) = 0$,当且仅当 x 为必败点P时。

这个SG(x)就是SG函数,用这个SG函数,我们能够将很多问题简化。

不是很理解的话来个例子就懂了。

【实例】取石子问题

有1堆n个的石子,每次只能取1, 3, 4个石子,先取完石子者胜利,那么各个数的SG值为多少?

SG[0]=0,f[]={1,3,4},

x=1 时,可以取走1 - f{1}个石子,剩余{0}个,所以 SG[1] = mex{ SG[0] }= mex{0} = 1;

x=2 时,可以取走2 - f{1}个石子,剩余{1}个,所以 SG[2] = mex{ SG[1] }= mex{1} = 0;

x=3 时,可以取走3 - f{1,3}个石子,剩余{2,0}个,所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;

x=4 时,可以取走4- f{1,3,4}个石子,剩余{3,1,0}个,所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;

x=5 时,可以取走5 - f{1,3,4}个石子,剩余{4,2,1}个,所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;

以此类推…..

x 0 1 2 3 4 5 6 7 8….

SG[x] 0 1 0 1 2 3 2 0 1….

一般当SG函数值为0表示必败态,非零代表必胜态。(在博弈中不存在不确定态)

由上述实例我们就可以得到SG函数值求解步骤,那么计算1~n的SG函数值步骤如下:

1、使用数组f将可改变当前状态的方式记录下来。

2、然后我们使用另一个数组将当前状态x的后继状态标记。

3、最后模拟mex运算,也就是我们在标记值中搜索未被标记值的最小值,将其赋值给SG(x)。

4、我们不断的重复2 - 3的步骤,就完成了计算1~n的函数值。

SG定理

游戏和的SG函数等于各个游戏SG函数的Nim和。这就是著名的SG定理,通过SG定理我们能够将多个子问题用Nim和连接起来或者将一个问题分成几个子问题来解决。表达形式为$res=SG[1]⊕SG[2]⊕SG[3]⊕…⊕SG[n]$,即每个子问题的SG函数的异或和。对一些经典博弈不是很清楚的请参照这里进行进一步理解。

经典例题

题目大意

给你三堆石子,每堆m,n,p个,两人轮流取石子,每次只能取斐波那契数列中的数,即1,2,3,5,8…等。问先手胜还是后手胜。

解题思路

先预处理出1000以下的所有sg函数值,然后用sg定理得出问题的解。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define endl '\n'
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;

set<int> s;
int sg[1010],vis[1010];

int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}

ll qpow(ll a, ll b, ll mod) {
ll ans = 1;
while (b) {
if (b & 1) ans = (ans * a) % mod;
a = (a * a) % mod, b >>= 1;
}
return ans % mod;
}

void SG(int x) {
rep(i, 1, x) {
memset(vis, 0, sizeof(vis));
for (auto x : s) {
if (x > i) break;
vis[sg[i - x]] = 1;
}
for (int j = 0;; j++) {
if (!vis[j]) {
sg[i] = j; break;
}
}
}
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("D:\\测试用\\in.txt", "r", stdin);
//freopen("D:\\测试用\\out.txt", "w+", stdout);
int a = 1, b = 1;
while (b <= 1000) {
s.insert(b);
int t = b;
b += a, a = t;
}
SG(1000);
int n, m, p;
while (cin >> n >> m >> p&&n||m||p) {
if (sg[n] ^ sg[m] ^ sg[p]) cout << "Fibo" << endl;
else cout << "Nacci" << endl;
}
return 0;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信