洛谷P10507 Georgia and Bob 题解

题目链接：P10507 Georgia and Bob

题意：

有一个无限长的棋盘，从左到右编号为 \(1,2,3,\cdots\)。有 \(n\) 个棋子在棋盘上，定义一次操作为把一枚棋子向左移动至少一格，不可以逾越其他棋子，不可与其他棋子重合，不可移出棋盘。

告诉你这 \(n\) 个棋子的位置（不保证顺序且保证没有棋子重合），Georgia 和 Bob 轮流进行操作，Georgia 先手，谁无法操作谁输。问最后谁会赢？

输入格式：

本题有多组数据。

第一行一个整数 \(T\)，表示数据组数。

对于每组数据：

第一行一个整数 \(n\)。

接下来一行 \(n\) 个整数，表示每个棋子的位置。

输出格式：

对于每组数据，若 Georgia 胜输出 Georgia will win，若 Bob 胜输出 Bob will win。

首先对 \(x_i\) 排序，记 \(b_i = x_i - x_{i-1}-1\) 是每个棋子初始可以移动的格数。

注意到当第 \(i\) 个棋子移动 \(x\) 格时，会使得 \(b_i \gets b_i - x\) 且 \(b_{i + 1} \gets b_{i + 1} + x\) 。

于是这就变成了一个反着的阶梯博弈。思路和 洛谷P3480 [POI2009] KAM-Pebbles 几乎一致。

时间复杂度 \(\mathcal{O}(Tn)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

int a[N], b[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq;
    while(qwq--)
    {
        int n, res = 0; cin >> n;
        rep(i, 1, n) cin >> a[i];
        sort(a + 1, a + 1 + n);
        rep(i, 1, n) b[i] = a[i] - a[i - 1] - 1;
        for(int i = n; i > 0; i -= 2) res ^= b[i];
        cout << (res ? "Georgia" : "Bob") << " will win\n"; 
    }
    return 0;
}