POJ 1704 - 階梯博弈 / Georgia and Bob

問題描述

n 枚棋子在 x 正半軸，兩人輪流向左移動棋子，不可超過其他棋子或越界（x<0）。無法移動者負。求獲勝者。

等價轉化：階梯博弈

將棋子位置排序：x1 < x2 < ... < xn。定義間隙：g1 = x1 - 0, g2 = x2 - x1 - 1, ..., gn = xn - x_{n-1} - 1。移動棋子相當於減小某個間隙並增大右側間隙。這等價於 Nim 遊戲在**奇數編號間隙**（從右往左數）上的 XOR 和。

具體：從最右邊棋子開始，編號 1,2,3...（最右為 1）。奇數編號間隙的大小 XOR 起來，非零則先手勝（Georgia），零則後手勝（Bob）。

代碼實現（C++）

#include 
using namespace std;
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        vector a(n+1);
        for (int i=1;i<=n;i++) scanf("%d", &a[i]);
        sort(a.begin()+1, a.end());
        int x = 0;
        for (int i=n; i>=1; i-=2) {
            int gap = a[i] - a[i-1] - 1; // a[0]=0
            x ^= gap;
        }
        puts(x ? "Georgia will win" : "Bob will win");
    }
    return 0;
}

關鍵點

• 排序位置，計算間隙。
• 從右向左隔一個取間隙（即奇數級）。
• XOR 非零判定先手勝。