POJ 1704 -Georgia and Bob

题目链接:POJ 1704

题图:

题图

这题可以转化为NIM博弈.如果棋子为偶数,则从前往后两个两个成对,每对棋子中间的空位看作是一堆石子,多少个空位就多少个石子.如果棋子数为奇数,则在第0个位置加入一个虚拟棋子,然后按偶数情况处理.

容易想到,对于每一对棋子,如果将后面一个棋子往前移,则等效于将该堆石子减少,但将前面一个棋子往前移,则会造成该对棋子中间的空位数增加,就无法和nim对应上.

书上和网上大多数题解提到,如果前面的棋子前移了,后面的棋子相应也往前移相同的单位,则回到了原来的状态,所以前面棋子前移也不影响.

但至于为什么选手就一定会在前面的棋子前移后,将后面的棋子也相应往前移动呢,根据选手总是采取最优策略,我的想法是假设此时选手在原来的状态是必胜的,那么他一定会为了维持这种状态而将后面的棋子相应往前移,而且此时选手不可能是原先状态必败的那个选手,因为必胜的选手不可能会破坏他必胜的状态.而对于必败的选手,那么他无论如何怎么做,都将使对手局面转变为必胜态,或者将前面的棋子往前移,试图破坏目前的状态,可这种破坏是无济于事的,因为前面提到,必胜的选手一定会为了维持他必胜的状态而相应将后面的棋子往前移.至于相邻两对棋子中间的空位,也会由于上述操作亦步亦趋地消除.

(ps:看了一些NIM博弈,感觉只有一开始就处于必胜状态的人,才有所谓的最优策略,此最优策略将带领他胜利,而注定失败的人无论如何挣扎,都将走向失败,哇好残酷啊

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int A[1005];
int main() {
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
      cin >> A[i];
    }
    if (n & 1) A[n++] = 0;
    sort(A, A + n);
    int x = 0;
    for (int i = 0; i + 1 < n; i += 2) {
      x ^= (A[i + 1] - A[i] - 1);
    }
    if (x)
      cout << "Georgia will win" << endl;
    else
      cout << "Bob will win" << endl;
  }

  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注