【知识点】博弈之SG函数

发表于 | 更新于 | 分类于

学习参考文章：

https://www.cnblogs.com/ECJTUACM-873284962/p/6921829.html

https://www.cnblogs.com/aiguona/p/9126324.html

模板

递推版：

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
//全部都算出来
const int N = 22;
const int M = 1111;

bool vis[M];
int f[N], SG[M];

void init()    //初始化f数组
{
    //f数组的初始化
}

void getSG(int n)	//得到SG值
{
    memset(SG, 0, sizeof(SG));
    for(int i = 1; i <= n; ++i)
    {
        //为下一步的运算进行标记
        memset(vis, 0, sizeof(vis));
        for(int j = 0; i >= f[j] && j < N; ++j)
            vis[SG[i - f[j]]] = 1;

        //得到mex的值
        for(int j = 0; ; ++j)
            if(!vis[j])
            {
                SG[i] = j;
                break;
            }
    }
}

递归版:

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
//用到哪个计算哪个
const int N = 111;
const int M = 11111;

int f[N], SG[M];

void init()
{
    memset(SG, -1, sizeof(SG));
    //f数组的初始化
}

int dfsSG(int x)	//得到SG值
{
    if(SG[x] != -1)
        return SG[x];

    //为下一步的运算进行标记
    bool vis[N] = {0};
    for(int i = 0; x >= f[i] && i < n; ++i)
    {
        dfsSG(x - f[i]);
        vis[SG[x - f[i]]] = 1;
    }

    //得到mex的值
    for(int i = 0; ; ++i)
        if(!vis[i])
            return SG[x] = i;
}

简单题目练习：

HDU 1847 最基本的应用

题意：$n$张牌，每次只能抓$2$的倍数张牌，先抓完胜，kiki先抓。

Code1：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 11;
const int M = 1111;

bool vis[M];
int f[N], SG[M];

void init()    //初始化f数组
{
    f[0] = 1;
    for(int i = 1; i < N; ++i)
        f[i] = f[i - 1] << 1;
}

void getSG(int n)	//得到SG值
{
    memset(SG, 0, sizeof(SG));
    for(int i = 1; i <= n; ++i)
    {
        //为下一步的运算进行标记
        memset(vis, 0, sizeof(vis));
        for(int j = 0; i >= f[j] && j < N; ++j)
            vis[SG[i - f[j]]] = 1;

        //得到mex的值
        for(int j = 0; ; ++j)
            if(!vis[j])
            {
                SG[i] = j;
                break;
            }
    }
}

int n;
int main()
{
    init();
    getSG(1000);
    while(~scanf("%d",&n))
    {
        puts(SG[n] ? "Kiki" : "Cici");
    }
    return 0;
}

Code2：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 111;
const int M = 11111;

int f[N], SG[M];

void init()
{
    memset(SG, -1, sizeof(SG));
    f[0] = 1;
    for(int i = 1; i <= 10; ++i)
        f[i] = f[i - 1] << 1;
}

int dfsSG(int x)	//得到SG值
{
    if(SG[x] != -1)
        return SG[x];

    //为下一步的运算进行标记
    bool vis[N] = {0};
    for(int i = 0; x >= f[i] && i < N; ++i)
    {
        dfsSG(x - f[i]);
        vis[SG[x - f[i]]] = 1;
    }

    //得到mex的值
    for(int i = 0; ; ++i)
        if(!vis[i])
            return SG[x] = i;
}

int n;
int main()
{
    init();
    while(~scanf("%d", &n))
        puts(dfsSG(n) ? "Kiki" : "Cici");
    return 0;
}

HDU 1848 划分子游戏-分别求-合并

题意：$3$堆石子分别$n$、$m$、$k$个，每次取fibonacci数个石子，fibo先取。

Code1：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 22;
const int M = 1111;

bool vis[M];
int f[N], SG[M];

void init()    //初始化f数组
{
    f[0] = f[1] = 1;
    for(int i = 2; i < N; ++i)
        f[i] = f[i - 1] + f[i - 2];
}

void getSG(int n)	//得到SG值
{
    memset(SG, 0, sizeof(SG));
    for(int i = 1; i <= n; ++i)
    {
        //为下一步的运算进行标记
        memset(vis, 0, sizeof(vis));
        for(int j = 0; i >= f[j] && j < N; ++j)
            vis[SG[i - f[j]]] = 1;

        //得到mex的值
        for(int j = 0; ; ++j)
            if(!vis[j])
            {
                SG[i] = j;
                break;
            }
    }
}

int n, m, k;
int main()
{
    init();
    getSG(1000);
    while(scanf("%d%d%d",&n,&m,&k) && (n || m || k))
    {
        puts((SG[n] ^ SG[m] ^ SG[k]) ? "Fibo" : "Nacci");
    }
    return 0;
}

Code2：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 111;
const int M = 11111;

int f[N], SG[M];

void init()
{
    memset(SG, -1, sizeof(SG));
    f[0] = f[1] = 1;
    for(int i = 2; i <= 17; ++i)
        f[i] = f[i - 1] + f[i - 2];
}

int dfsSG(int x)	//得到SG值
{
    if(SG[x] != -1)
        return SG[x];

    //为下一步的运算进行标记
    bool vis[N] = {0};
    for(int i = 0; x >= f[i] && i < N; ++i)
    {
        dfsSG(x - f[i]);
        vis[SG[x - f[i]]] = 1;
    }

    //得到mex的值
    for(int i = 0; ; ++i)
        if(!vis[i])
            return SG[x] = i;
}

int n, m, k;
int main()
{
    init();
    while(scanf("%d%d%d", &n,&m,&k) && (n || m || k))
        puts((dfsSG(n) ^ dfsSG(m) ^ dfsSG(k)) ? "Fibo" : "Nacci");
    return 0;
}

HDU 1536 划分&合并

在$Nim$博弈的条件下加上限制：每次只能移走给定的$n$个数的个数的石子。$m$次询问，每次给出$k$堆石子的个数，问先手是否能赢。

Code1：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 111;
const int M = 11111;

bool vis[M];
int f[N], SG[M];
int n, m, k, t, res;

void init()    //初始化f数组
{
    for(int i = 0; i < n; ++i)
        scanf("%d", &f[i]);
    sort(f, f + n);
}

void getSG()	//得到SG值
{
    memset(SG, 0, sizeof(SG));
    for(int i = 1; i < M; ++i)
    {
        //为下一步的运算进行标记
        memset(vis, 0, sizeof(vis));
        for(int j = 0; i >= f[j] && j < n; ++j)
            vis[SG[i - f[j]]] = 1;

        //得到mex的值
        for(int j = 0; ; ++j)
            if(!vis[j])
            {
                SG[i] = j;
                break;
            }
    }
}

int main()
{
    while(scanf("%d",&n) && n)
    {
        init();
        getSG();    //预处理出所有的SG值来，不用每次都求一遍
        scanf("%d", &m);
        while(m--)
        {
            res = 0;
            scanf("%d", &k);
            for(int i = 0; i < k; ++i)
            {
                scanf("%d", &t);
                res ^= SG[t];
            }
            putchar(res ? 'W' : 'L');
        }
        puts("");
    }
    return 0;
}

Code2：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 111;
const int M = 11111;

int f[N], SG[M];
int n, m, k, t, res;

void init()
{
    memset(SG, -1, sizeof(SG));
    for(int i = 0; i < n; ++i)
        scanf("%d", &f[i]);
    sort(f, f + n);
}

int dfsSG(int x)
{
    if(SG[x] != -1)
        return SG[x];

    bool vis[N] = {0};
    for(int i = 0; x >= f[i] && i < n; ++i)
    {
        dfsSG(x - f[i]);
        vis[SG[x - f[i]]] = 1;
    }
    for(int i = 0; ; ++i)
        if(!vis[i])
            return SG[x] = i;
}

int main()
{
    while(scanf("%d",&n) && n)
    {
        init();
        scanf("%d", &m);
        while(m--)
        {
            res = 0;
            scanf("%d", &k);
            for(int i = 0; i < k; ++i)
            {
                scanf("%d", &t);
                res ^= dfsSG(t);
            }
            putchar(res ? 'W' : 'L');
        }
        puts("");
    }
    return 0;
}

为了AC这一题学的SG函数

LightOJ 1315 Game of Hyper Knights

题意：棋盘上有$n$个棋子，告诉你棋子的初始位置，两人轮流按照规定的移动方向移动棋子，每次只能移动一个棋子，两个棋子可以重合在一个位置。谁无法移动棋子时谁就输了。

思路：求出每个棋子的SG函数，划分后再合并。

MyCode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 111;
const int M = 1111;
int dir[][2] = {-3,-1,-2,-1,-2,1,-1,-3,-1,-2,1,-2};

int SG[M][M];

void init()
{
    memset(SG, -1, sizeof(SG));
}

int dfsSG(int x, int y)	//得到SG值
{
    if(SG[x][y] != -1)
        return SG[x][y];

    //为下一步的运算进行标记
    bool vis[N] = {0};
    for(int i = 0; i < 6; ++i)
    {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if(xx < 0 || yy < 0)    continue;
        dfsSG(xx, yy);
        vis[SG[xx][yy]] = 1;
    }

    //得到mex的值
    for(int i = 0; ; ++i)
        if(!vis[i])
            return SG[x][y] = i;
}

int t, n, x, y, res;
int main()
{
    init();
    scanf("%d", &t);
    for(int cas = 1; cas <= t; ++cas)
    {
        res = 0;
        scanf("%d", &n);
        while(n--)
        {
            scanf("%d%d", &x, &y);
            res ^= dfsSG(x, y);
        }
        printf("Case %d: %s\n", cas, res ? "Alice" : "Bob");
    }
    return 0;
}

其他的一些练习

POJ 2425 A Chess Game【树形博弈】【SG函数】

题意：给定一个有向无环图，上面有一些棋子，棋子可以重合，两人依次对这些石子进行操作，每次操作可以将一个棋子从一个位置移动到相邻的位置，无法移动着输。问先手是否必胜。

思路：把每个棋子单独看作一个游戏，所有棋子的SG值就是这些棋子的SG值的异或和。

MyCode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 1111;

int SG[N];
int n, m, t;
vector<int> G[N];
void init()
{
    memset(SG, -1, sizeof(SG));
    for(int i = 0; i < n; ++i)
        G[i].clear();
}

int dfsSG(int x)	//得到SG值
{
    if(SG[x] != -1)
        return SG[x];

    //为下一步的运算进行标记
    bool vis[N] = {0};
    for(int i = 0; i < G[x].size(); ++i)
    {
        dfsSG(G[x][i]);
        vis[SG[G[x][i]]] = 1;
    }

    //得到mex的值
    for(int i = 0; ; ++i)
        if(!vis[i])
            return SG[x] = i;
}

int main()
{
    while(~scanf("%d", &n))
    {
        init();
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &m);
            while(m--)
            {
                scanf("%d", &t);
                G[i].push_back(t);
            }
        }
        while(scanf("%d", &m) && m)
        {
            int res = 0;
            for(int i = 0; i < m; ++i)
            {
                scanf("%d", &t);
                res ^= dfsSG(t);
            }
            puts(res ? "WIN" : "LOSE");
        }
    }
    return 0;
}

POJ 1704 Georgia and Bob【阶梯博弈】

题意：一行方格中，放置着$n$个棋子，每个棋子占据着唯一的一个方格。两人轮流移动棋子，每次选择一个向左移动至少一个方格，移动过程中不可跨越其他棋子或者越过棋盘。问谁赢。

思路：将相邻两堆一起看(如果是奇数堆则第一堆和0一起看)。前一对进行移动操作后后一对总能移动相应的位置恢复到之前的状态所以相邻两对之间的空格数对结果是没有影响的，因此只需考虑一对之间的空格数就可以了，这样将相邻一对的空格数记录一下后就成了阶梯博弈。

阶梯博弈：https://blog.csdn.net/kk303/article/details/6692506

MyCode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1111;

int t, n, a[N];
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);
        int res = 0;
        for(int i = n; i > 0; i -= 2)
            res ^= a[i] - a[i - 1] - 1;
        puts(res ? "Georgia will win" : "Bob will win");
    }
    return 0;
}

HDU 4315 Climbing the Hill【阶梯博弈】

题意：有$N$个人爬山，山顶坐标为$0$，其他人的坐标按升序给出。除山顶外，不同的坐标只能容纳一个人，Alice和Bob轮流选择一个人让他移动任意步，但不能越过前面那个人。谁能将给出ID的人移动到山顶就算谁赢。

Hint：与上一题的不同之处在于这题有$0$这个坐标。

思路：https://www.cnblogs.com/fightfordream/p/6194612.html

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1111;

int n, k, a[N];
int main()
{
    while(~scanf("%d%d", &n,&k))
    {
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        if(k == 1)
            puts("Alice");
        else
        {
            if(k == 2) a[0] = 0; else a[0] = -1;
            int res = 0;
            for(int i = n; i > 0; i -= 2)
                res ^= a[i] - a[i - 1] - 1;
            puts(res ? "Alice" : "Bob");
        }
    }
    return 0;
}

HDU 3389 Game【阶梯博弈】

题意：$n$堆石子，每回合可选择两堆石子A和B，满足条件：B < A && (A+B)%2 == 1 && (A+B)%3 == 0​，将A堆中石子任意颗移动到B堆里。

思路：很容易得知1,3,4这三个位置的石子无法移动，然后%6==0,2,5的位置只能移动奇数步，其余位置为偶数步。为奇数步的位置符合阶梯博弈。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int t, n, x, res;
int main()
{
    scanf("%d", &t);
    for(int cas = 1; cas <= t; ++cas)
    {
        res = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &x);
            if(i % 6 == 0 || i % 6 == 2 || i % 6 == 5)
                res ^= x;
        }
        printf("Case %d: %s\n", cas, res ? "Alice" : "Bob");
    }
    return 0;
}

ZOJ 3057 Beans Game【三维威佐夫博弈】【递推打表】

题意：在威佐夫博弈的限制下，将石子堆数改变为3堆。

思路：范围很小，可直接将所有结果计算出来。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 301;

int x, y, z;
bool dp[N][N][N];
void init()
{
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            for(int k = 0; k < N; ++k)
                if(!dp[i][j][k])
                {
                    for(int t = 1; t + i < N; ++t)
                        dp[i + t][j][k] = 1;
                    for(int t = 1; t + j < N; ++t)
                        dp[i][j + t][k] = 1;
                    for(int t = 1; t + k < N; ++t)
                        dp[i][j][k + t] = 1;
                    for(int t = 1; t + i < N && t + j < N; ++t)
                        dp[i + t][j + t][k] = 1;
                    for(int t = 1; t + i < N && t + k < N; ++t)
                        dp[i + t][j][k + t] = 1;
                    for(int t = 1; t + k < N && t + j < N; ++t)
                        dp[i][j + t][k + t] = 1;
                }
}
int main()
{
    init();
    while(~scanf("%d%d%d", &x,&y,&z))
        cout << dp[x][y][z] << '\n';
    return 0;
}

POJ 2348 Euclid’s Game【博弈】

题意：两人玩游戏，每次选一个为两个数中较小的那个数的倍数，让较大的那个数减去选的这个数(做差后就过不能为负)，谁不能进行操作谁就输了。

思路：规定$n$为两者中较大的那个数，当$n \% m == 0$时当前操作者必胜；对于$n - m$ ＜ $m$的情况，此时的操作者只能进行唯一的操作；当$n - m$ > $m$时，当前操作者可控制整个局面，必胜。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int n, m;
int main()
{
    while(scanf("%d%d", &n,&m) && (n + m))
    {
        bool fir = 1;
        while(true)
        {
            if(n < m)   swap(n, m);
            if(n % m == 0)  break;
            if(n - m > m)   break;
            fir = !fir;
            n -= m;
        }
        puts(fir ? "Stan wins" : "Ollie wins");
    }
    return 0;
}

HDU 3404 Switch lights【Nim积】

题意：在一个平面图形中有无穷多的灯，初始时有$n$盏灯亮着。两个玩家每次可选择四个点使这四个点的灯改变状态，要求是这四个点构成一个长方形且右下角的灯要亮着，无法进行操作的输。

思路：Nim积，先存个代码。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int m[2][2]= {0,0,0,1};

int Nim_Multi_Power(int x,int y)
{
    if(x<2)
        return m[x][y];
    int a=0;
    for(;; a++)
        if(x>=(1<<(1<<a))&&x<(1<<(1<<(a+1))))
            break;
    int m=1<<(1<<a);
    int p=x/m,s=y/m,t=y%m;
    int d1=Nim_Multi_Power(p,s);
    int d2=Nim_Multi_Power(p,t);
    return (m*(d1^d2))^Nim_Multi_Power(m/2,d1);
}

int Nim_Multi(int x,int y)
{
    if(x<y)
        return Nim_Multi(y,x);
    if(x<2)
        return m[x][y];
    int a=0;
    for(;; a++)
        if(x>=(1<<(1<<a))&&x<(1<<(1<<(a+1))))
            break;
    int  m=1<<(1<<a);
    int p=x/m,q=x%m,s=y/m,t=y%m;
    int c1=Nim_Multi(p,s);
    int c2=Nim_Multi(p,t)^Nim_Multi(q,s);
    int c3=Nim_Multi(q,t);
    return (m*(c1^c2))^c3^Nim_Multi_Power(m/2,c1);
}

int t, n, x, y, res;
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        res = 0;
        scanf("%d", &n);
        while(n--)
        {
            scanf("%d%d", &x,&y);
            res ^= Nim_Multi(x, y);
        }
        puts(res ? "Have a try, lxhgww." : "Don't waste your time.");
    }
    return 0;
}

POJ 3533 Light Switching Game【三维Nim积】

题意：上一题的由二维变成了三维。

思路：三维Nim积。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int m[2][2]= {0,0,0,1};

int Nim_Multi_Power(int x,int y)
{
    if(x<2)
        return m[x][y];
    int a=0;
    for(;; a++)
        if(x>=(1<<(1<<a))&&x<(1<<(1<<(a+1))))
            break;
    int m=1<<(1<<a);
    int p=x/m,s=y/m,t=y%m;
    int d1=Nim_Multi_Power(p,s);
    int d2=Nim_Multi_Power(p,t);
    return (m*(d1^d2))^Nim_Multi_Power(m/2,d1);
}

int Nim_Multi(int x,int y)
{
    if(x<y)
        return Nim_Multi(y,x);
    if(x<2)
        return m[x][y];
    int a=0;
    for(;; a++)
        if(x>=(1<<(1<<a))&&x<(1<<(1<<(a+1))))
            break;
    int  m=1<<(1<<a);
    int p=x/m,q=x%m,s=y/m,t=y%m;
    int c1=Nim_Multi(p,s);
    int c2=Nim_Multi(p,t)^Nim_Multi(q,s);
    int c3=Nim_Multi(q,t);
    return (m*(c1^c2))^c3^Nim_Multi_Power(m/2,c1);
}

int n, x, y, z, res;
int main()
{
    while(~scanf("%d", &n))
    {
        res = 0;
        while(n--)
        {
            scanf("%d%d%d", &x,&y,&z);
            res ^= Nim_Multi(Nim_Multi(x, y), z);
        }
        puts(res ? "No" : "Yes");
    }
    return 0;
}

ZOJ 3599 Game【K倍动态减法】

题意：两人轮流取石子，第一个人可以随意取不超过总数的石子，后面的人取不超过第一个人$k$倍的石子，最后一个取到的人赢，问石子数在$1$ ~ $n$中有多少种先手必胜的局面。

思路：$k$倍动态减法，存一下。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 3000000;
typedef long long ll;

int t, n, k;
ll a[N], b[N];

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &k, &n);

        a[0] = b[0] = 1;
        int i = 0, j = 0;
        while(n > a[i])
        {
            ++i;
            a[i] = b[i - 1] + 1;
            while(a[j + 1] * k < a[i])
                ++j;
            if(k * a[j] < a[i])
                b[i] = b[j] + a[i];
            else
                b[i] = a[i];
        }

        printf("%d\n", n - i - (n == a[i]));
    }
    return 0;
}

HDU 2486 A simple stone game【K倍动态减法】

题意：游戏规则同上，如果必胜则输出先手第一轮先取的最小的数目的石子，否则输出lose。

思路：找最小的石子就是在凑$n$的过程中所用到的最小的数。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 3000000;
typedef long long ll;

int t, n, k;
ll a[N], b[N];

int main()
{
    scanf("%d", &t);
    for(int cas = 1; cas <= t; ++cas)
    {
        scanf("%d%d", &n, &k);

        a[0] = b[0] = 1;
        int i = 0, j = 0;
        while(n > a[i])
        {
            ++i;
            a[i] = b[i - 1] + 1;
            while(a[j + 1] * k < a[i])
                ++j;
            if(k * a[j] < a[i])
                b[i] = b[j] + a[i];
            else
                b[i] = a[i];
        }

        printf("Case %d: ", cas);
        if(n == a[i])
            printf("lose\n");
        else
        {
            int res;
            while(n)
            {
                if(n >= a[i])
                {
                    n -= a[i];
                    res = a[i];
                }
                --i;
            }
            printf("%d\n", res);
        }
    }
    return 0;
}
Donate comment here
0%