sg[i]为0表示i节点先手必败。
首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。
例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Grundy函数g如下：g(x)=mex{ g(y) | y是x的后继 },这里的g（x）即sg[x]
例如：取石子问题，有1堆n个的石子，每次只能取{1，3,4}个石子，先取完石子者胜利，那么各个数的SG值为多少？
sg[0]=0，f[]={1,3,4},
x=1时，可以取走1-f{1}个石子，剩余{0}个，mex{sg[0]}={0}，故sg[1]=1;
x=2时，可以取走2-f{1}个石子，剩余{1}个，mex{sg[1]}={1}，故sg[2]=0；
x=3时，可以取走3-f{1,3}个石子，剩余{2,0}个，mex{sg[2],sg[0]}={0,0}，故sg[3]=1;
x=4时，可以取走4-f{1,3,4}个石子，剩余{3,1,0}个，mex{sg[3],sg[1],sg[0]}={1,1,0},故sg[4]=2;
x=5时，可以取走5-f{1,3,4}个石子，剩余{4,2,1}个，mex{sg[4],sg[2],sg[1]}={2,0,1},故sg[5]=3；
以此类推.....
x 0 1 2 3 4 5 6 7 8....
sg[x] 0 1 0 1 2 3 2 0 1....
计算从1-n范围内的sg值，
s[]存储可以走的步数，s[0]表示可以有多少种走法
s[]需要从小到大排序
1.可选步数为1~m的连续整数，直接取模即可，sg[x] = x % (m+1);
2.可选步数为任意步，sg[x] = x;
3.可选步数为一系列不连续的数，用sg函数计算
模板1（dfs）：
1 /*
2 s数组表示合法移动集合，从小到大排序。sNum合法移动个数
3 sg数组初始化为-1，对每个集合s仅需初始化1次
4 */
5 const int MAXN = 20;//s集合大小
6 const int MAXM = 1000 + 5;//
7 int s[MAXN], sNum;
8 int sg[MAXM];
9
10 int dfsSg(int x)
11 {
12 if (sg[x] != -1) {
13 return sg[x];
14 }
15 int i;
16 bool vis[MAXN];//sg值小于等于合法移动个数sNum
17
18 memset(vis, false, sizeof(vis));
19 for (i = 0; i < sNum && s[i] <= x; ++i) {
20 dfsSg(x - s[i]);
21 vis[sg[x - s[i]]] = true;
22 }
23 for (i = 0; i <= sNum; ++i) {
24 if (!vis[i]) {
25 sg[x] = i;
26 break;
27 }
28 }
29 return sg[x];
30 }
View Code
模板2（打表）：
求出所有sg值，有时没必要，用dfs就行
1 /*
2 s数组表示合法移动集合，从小到大排序。sNum合法移动个数
3 sg值对每个集合s仅需求一次
4 */
5 const int MAXN = 20;//s集合大小
6 const int MAXM = 1000 + 5;//
7 int s[MAXN], sNum;
8 int sg[MAXM];
9 bool exist[MAXN];//sg值小于等于合法移动个数sNum
10
11 void getSg(int n)
12 {
13 int i, j;
14 sg[0] = 0;//必败态
15 for (i = 1; i <= n; ++i) {
16 memset(exist, false, sizeof(exist));
17 for (j = 0; j < sNum && s[j] <= i; ++j) {
18 exist[sg[i - s[j]]] = true;
19 }
20 for (j = 0; j <= sNum; ++j) {
21 if (!exist[j]) {
22 sg[i] = j;
23 break;
24 }
25 }
26 }
27 }
View Code
hdu 1848 Fibonacci again and again（sg）
取石子问题，一共有3堆石子，每次只能取斐波那契数个石子，先取完石子者胜利，问先手胜还是后手胜
1 #include
2 using namespace std;
3
4 /*
5 s数组表示合法移动集合，从小到大排序。sNum合法移动个数
6 sg数组初始化为-1，对每个集合s仅需初始化1次
7 */
8 const int MAXN = 20;//s集合大小
9 const int MAXM = 1000 + 5;//
10 int s[MAXN], sNum;
11 int sg[MAXM];
12
13 int dfsSg(int x)
14 {
15 if (sg[x] != -1) {
16 return sg[x];
17 }
18 int i;
19 bool vis[MAXN];//sg值小于等于合法移动个数sNum
20
21 memset(vis, false, sizeof(vis));
22 for (i = 0; i < sNum && s[i] <= x; ++i) {
23 dfsSg(x - s[i]);
24 vis[sg[x - s[i]]] = true;
25 }
26 for (i = 0; i <= sNum; ++i) {
27 if (!vis[i]) {
28 sg[x] = i;
29 break;
30 }
31 }
32 return sg[x];
33 }
34
35 int main()
36 {
37 int i;
38 s[0] = 1;
39 s[1] = 2;
40 for (i = 2; i < MAXN; ++i) {
41 s[i] = s[i - 1] + s[i - 2];
42 //printf("%d %d\n", i, s[i]);
43 }
44 sNum = 16;
45 int m, n, p;
46 int sum;
47 memset(sg, -1, sizeof(sg));
48 while (~scanf("%d%d%d", &m, &n, &p)) {
49 if (m == 0 && n == 0 && p == 0) {
50 break;
51 }
52 dfsSg(m);
53 dfsSg(n);
54 dfsSg(p);
55 sum = sg[m] ^ sg[n] ^ sg[p];
56 if (sum != 0) {
57 printf("Fibo\n");
58 } else {
59 printf("Nacci\n");
60 }
61 }
62 return 0;
63 }
View Code
1 #include
2 using namespace std;
3
4 /*
5 s数组表示合法移动集合，从小到大排序。sNum合法移动个数
6 sg值对每个集合s仅需求一次
7 */
8 const int MAXN = 20;//s集合大小
9 const int MAXM = 1000 + 5;//
10 int s[MAXN], sNum;
11 int sg[MAXM];
12 bool exist[MAXN];//sg值小于等于合法移动个数sNum
13
14 void getSg(int n)
15 {
16 int i, j;
17 sg[0] = 0;//必败态
18 for (i = 1; i <= n; ++i) {
19 memset(exist, false, sizeof(exist));
20 for (j = 0; j < sNum && s[j] <= i; ++j) {
21 exist[sg[i - s[j]]] = true;
22 }
23 for (j = 0; j <= sNum; ++j) {
24 if (!exist[j]) {
25 sg[i] = j;
26 break;
27 }
28 }
29 }
30 }
31
32 int main()
33 {
34 int i;
35 s[0] = 1;
36 s[1] = 2;
37 for (i = 2; i < MAXN; ++i) {
38 s[i] = s[i - 1] + s[i - 2];
39 //printf("%d %d\n", i, s[i]);
40 }
41 sNum = 16;
42 int m, n, p;
43 int sum;
44 getSg(1000);
45 while (~scanf("%d%d%d", &m, &n, &p)) {
46 if (m == 0 && n == 0 && p == 0) {
47 break;
48 }
49 sum = sg[m] ^ sg[n] ^ sg[p];
50 if (sum != 0) {
51 printf("Fibo\n");
52 } else {
53 printf("Nacci\n");
54 }
55 }
56 return 0;
57 }
View Code
好文阅读
发表评论