题目链接

BZOJ1022

题目描述

给定 $n$ 堆石子,取到最后一个的玩家为败,其余规则和 Nim 游戏相同,问先手的状态。

思路要点

博弈论,就需要动一下脑子了

首先 $Nim$ 游戏一定没有平局的情况,所以一定只存在必胜或者必败的状态。

考虑全是 $1$ 的情况,显然当异或和$=0$时,为必胜态。

然后考虑其中有 $1$ 堆 $>1$ 的情况,也比较显然异或和一定 $>0$,且当前状态一定为必胜态。

考虑其中有多堆 $>1$ 的情况,那么就存在了异或和 $=0$ 或者 $>0$ 的两种情况。

  1. 假设现在面临着一个多堆 $>1$ 异或和 $=0$ 的情况,可以转化成多堆 $>1$ 异或和 $>0$ 的情况,或者一堆 $>1$ 异或和 $>0$的情况,这时我们会发现这个状态我们并不能确定是否必胜或者必败,因为当前选择的人一定不会傻到自己选一堆 $>1$ 异或和 $>0$的情况,这样对手就处在了必胜态,自己当前局面就是必败态。为了方便描述,我们称这个状态为 $A$ 状态。
  2. 那么考虑多堆 $>1$ 异或和 $>0$ 的情况,根据 $xum\leq max$ 可以得到,当前的状态一定可以转化成 多堆 $>1$ 异或和 $=0$ 的情况,也就是这个状态结束完一定可以构成 $a$ 状态。为了方便描述,我们称这个状态为 $B$ 状态。

综上,我们可以总结出 $B$ 状态为必胜态,因为无论如何 $B$ 可以构成 $A$,而 $A$ 要不是必败态要不转化为 $B$ 状态,循环至 $A$ 不能构成 $B$ 时,那么 $A$ 就变成了必败态,也就是 $A$ 一定是必败态。

时间复杂度 $O(n)$

代码

/*
 * @Author: chhokmah 
 * @Date: 2020-03-23 13:11:55 
 * @Last Modified by:   chhokmah 
 * @Last Modified time: 2020-03-23 13:11:55 
 */
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    int n, mx = 0, xum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      int x; 
      cin >> x;
      mx = max(mx, x);
      xum ^= x;
    }
    if ((mx == 1 && xum == 0) || (mx > 1 && xum != 0)) {
      cout << "John" << '\n';
    } else {
      cout << "Brother" << '\n';
    }
  }
  return 0;
}

后言

  • 分析简单的博弈论时,可以从几个比较明显状态入手。
  • 如果存在某一个状态无法确定时,可以先考虑别的状态,再看这个状态是否为必胜或者必败的状态。
最后修改:2020 年 03 月 23 日 01 : 30 PM
如果觉得我的文章对你有用,请随意赞赏