博弈题目(一)

发表于 | 分类于 | 阅读次数：

最近开始学习博弈相关的知识了，记录一下刷题过程。

Partitioning Game

Partitioning Game

题意

有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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
bool vis[10001];
int sg[10001];
void getSG()
{
    for(int i = 1; i <= 10000; ++i)
    {
        memset(vis, 0 , sizeof(vis));
        for(int j = 1; i - j > j ; ++j)
        {
            vis[sg[j]^sg[i - j]] = 1;
        }
        for(int j = 0; ; ++j)
        {
            if(!vis[j])
            {
                sg[i] = j;
                break;
            }
        }
    }
}
int main()
{
    getSG();
    int t, n, a, caser = 1;
    cin >> t;
    while(t--)
    {
        int flag = 0;
        cin >> n;
        for(int i = 1; i <= n; ++i)
        {
            cin >> a;
            flag ^= sg[a];
        }
        cout << "Case " << caser++ << ": ";
        if(flag)
            cout << "Alice" << '\n';
        else
            cout << "Bob" << '\n';
    }
}

kiki’s game

Kiki’s game

题意

给你一个N * M的矩阵， 从（1，M）开始出发，每人可以移动一次：可以向左移动，向下移动，向左下移动，现在给你N，M，问你谁赢。

思路

本来以为需要sg函数，但总认为需要二维sg,但问题是没见过二维的模板，后来才知道其实是很普通的博弈，只需要把图中的P,N态画出来就一目了然（感觉这个图是真的奇妙啊）。需要记住3点，这也是很多博客提到的：

  1. 终结态一定为P态，即先手必败
  2. 如果一个状态的后继状态全为N态，那么该状态为P态
  3. 如果一个状态的后继状态有一个为P态，那么该状态为N态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

int main()
{
    int n, m;
    while(cin >> n >> m && n && m)
    {
        if(n & 1 && m & 1)
            cout << "What a pity!" << '\n';
        else
            cout << "Wonderful!" << '\n';
    }
}

Good Luck in CET-4 Everybody!

Good Luck in CET-4 Everybody!

思路

简单的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
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
using namespace std;
typedef long long ll;

int a[10] = {1,2,4,8,16,32,64,128,256,512};
int sg[1001];
int main()
{
    sg[0] = 0;
    sg[1] = 1;
    sg[2] = 1;
    for(int i = 3; i <= 1000; ++i)
    {
        int flag = 1;
        for(int j = 0; j < 10 && a[j] < i; ++j)
        {
            if(sg[i - a[j]] == 0)
            {
                flag = 0;
                break;
            }
        }
        if(flag == 0)
        {
            sg[i] = 1;
        }
        else
            sg[i] = 0;
    }
    int n;
    while(cin >> n)
    {
        if(sg[n] == 0)
            cout << "Cici" << '\n';
        else
            cout << "Kiki" << '\n';
    }
}