博弈题目(四)

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

博弈题目<四>

小花梨的取石子游戏

小花梨的取石子游戏

思路

我们发现，只要这一堆的石子大于1，那么这堆石子的掌控者就能通过控制取该堆的次数来掌握先机。因此特殊情况就是看看从该堆开始有几个1，比如说 1 1 1 2 2 ，开始有3个1，那么他们每个人只能一个一个拿，第三个1的时候就是先手把第三堆取走，然后后手就可以通过对2 进行直接取走或者是分开取来掌握全局。 因此我们需要记录从该点开始向后找的连续的1的个数，开始我是直接遍历，就超时了，后来想到可以从后往前遍历进行记录。用的时候直接查询就行了。

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
#include <bits/stdc++.h>
using namespace std;
int a[300001];
int sum[300001];
int main()
{
    int n;
    cin >> n;
    int flag = 0;
    for(int i = 0; i < n; ++i)
        {
            scanf("%d",&a[i]);
            if(a[i] != 1) flag = 1;
            a[n + i] = a[i];
        }
    sum[n] = 0;
    for(int i = 2*n - 1; i >= 0; --i)
    {
        if(a[i] != 1)  sum[i] = 0;
        else  sum[i] = sum[i + 1] + 1;
    }
    if(n == 1)
    {
        for(int i = 0; i < n; ++i)
        {
            cout << "First" << '\n';
        }
    }
    else if(!flag)
    {
         for(int i = 0; i < n; ++i)
        {
            if(n & 1)
                cout << "First" << '\n';
            else
                cout << "Second" << '\n';
        }
    }
    else{
        for(int i = 0; i < n; ++i)
        {
            if(a[i] != 1) {cout << "First" << '\n';   continue;}
            if(sum[i] % 2)
                cout << "Second" << '\n';
            else
                cout << "First" << '\n';
        }
    }
}

SDUT 3893

Return of the nim

思路

当N = 2时是威佐夫博弈，当N > 2是我们需要证明其是NIM博弈

1.当现在是平衡态，即异或和为0的时候，那么1可以执行操作1或者操作2打破平衡态，但是后手可以执行操作1就再次将其转化为平衡态。即假若现在是平衡态，先手必败

2.当现在是非平衡态，那么先手可以执行操作1将其转化为平衡态，即若开始平衡，先手必赢。

以上满足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
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <math.h>
using namespace std;

int main()
{
    int t, a, b , n;
    cin >> t;
    while(t--)
    {
        cin >> n;
        if(n == 2)
        {
            cin >> a >> b;
            int num = int(((sqrt(5) + 1 )/ 2.0) * abs(b - a));
            if(num != min(a,b))
                cout << "Sherlock" << '\n';
            else
                cout << "Watson" << '\n';
            continue;
        }
        int f = 0;
        for(int i = 0; i < n; ++i)
        {
            cin >> a;
            f ^= a;
        }
        if(f)
            cout << "Sherlock" << '\n';
        else
            cout << "Watson" << '\n';
    }
}