博弈题目(三)

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

博弈题目(三)

HDU - 1525

Euclid’s Game

题意

没人每回合进行如下操作: 将两个数字中较大的数字减去较小的数字的倍数，但是不能使最终的数字变为0。谁先将其中一个数字变为0就赢。

思路

假设两个数字中较大的数字为N， 较小的数字为M

1.如果N == M 那么先手赢

2.如果N >= 2 * M , 我们知道一定会到达的状态是（N % M， M）, 而先手是可以判断这个状态是必胜态还是必败态的。如果该状态是必胜态，那么先手可以到达(N % M + M, M)状态，那么下个人进行操作之后的状态就是(N % M, M),所以先手赢。 如果这个状态是必败态，那么先手可以一步就到达(N % M, M)，从而获胜。

3.如果N < 2 M， 第一步的状态只能是到达(N - M, M), 接下来谁先控制到达 N >= 2 M 或者是 N % M == 0，谁就获胜。

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 <bits/stdc++.h>
using namespace std;

int main()
{
    int n,m;
    while(cin >> n >> m && n)
    {
        int num1 = min(n , m);
        int num2 = max(n , m);
        if(num2 % num1 == 0)
        {
            cout << "Stan wins" << '\n';
            continue;
        }
        else if(num2 >= 2 * num1)
        {
            cout << "Stan wins" << '\n';
            continue;
        }
        else {
            int flag = 0;
            while(1)
            {
               if(num1 > num2) swap(num1, num2);
               if(num2 % num1 == 0)  break;
               if(num2 > 2 * num1)  break;
               flag = !flag;
               num2 -= num1;
            }
            if(flag)
                cout << "Ollie wins" << '\n';
            else
                cout << "Stan wins" << '\n';
        }
    }
}

HDU - 2516

取石子游戏

思路

以前没遇到过，看了题解知道是斐波那契博弈。有如下的规定：当且仅当石子的个数是一个斐波那契数的时候，先手必败。下面给出证明：(数学归纳法)

  1. 当i = 2，显然成立。

  2. 假设当i <= k 时，结论成立。

    则当i = k + 1时，有f[i] = f[k] + f[k - 1]成立

    我们可以把这堆石子看成两堆（因为f[k] < 2 * f[k-1]，假如先手取完f[k - 1]堆，那么后手就直接赢了）

    根据 假设，在取第f[k - 1]堆时，最后一颗石子必定由后手移动。若先手在第f[k - 1]堆中取走>= f[k - 1]/3， 则后手取走的个数 <= 2 f[k - 1]/3, 当正好为2 f[k - 1]/ 3时，先手在下一次中最大移动的为4 * f[k - 1]/ 3 ，我们把这个数字和 f[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
    #include <bits/stdc++.h>
    using namespace std;
    int f[50];
    void init()
    {
        f[0] = f[1] = 1;
        for(int i = 2; i <= 45; ++i)
        {
            f[i] = f[i - 1] + f[i - 2];
        }
    }
    int main(){
      int t;
      init();
      while(cin >> t && t)
      {
          int flag = 0;
          for(int i = 2; i <= 45; ++i)
          {
              if(f[i] == t)
              {
                  flag = 1;
                  break;
              }
          }
          if(flag)
            cout << "Second win" << '\n';
          else
            cout << "First win" << '\n';
       }
    }

HDU - 3032

NIM or not NIM

思路

可以对一堆进行两种操作，问题是一堆中的石子数是很多的，求sg打表超时，后来发现sg也是有规律的，找出规律就和普通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
void getSG()    //打表函数
{
    sg[0] = 0;
    for(int i = 1; i <= 1000; ++i)
    {
        memset(vis, 0 , sizeof(vis));
        for(int j = 1; j <= i; ++j)
        {
            vis[sg[i - j]] = 1;
        }
        for(int j = 1; j < i; ++j)
        {
            vis[sg[i - j]^sg[j]] = 1;
        }
        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
#include <bits/stdc++.h>
using namespace std;
int elect(int n)
{
    if(n % 4 == 0)
        return n - 1 ;
    if(n % 4 == 3)
        return n + 1;
    return n;
}
int main()
{
    int t, n;
    cin >> t;
    while(t--)
    {
        cin >> n;
        int flag = 0;
        for(int i = 0; i < n; ++i)
        {
            int a;
            cin >> a;
            flag ^= elect(a);
        }
        if(flag)
            cout << "Alice" << '\n';
        else
            cout << "Bob" << '\n';
    }
}