python/TangDou/AcWing_TiGao/T5/GameTheory/POJ1704_StaircaseNim_8.cpp

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <math.h>
#include <cstdio>
using namespace std;
// 8个数字的用例
/*
测试用例：
1 8
1 5 6 7 9 12 14 17

输出:
i=1,a[8]-a[7]-1=2
i=3,a[6]-a[5]-1=2
i=5,a[4]-a[3]-1=0
i=7,a[2]-a[1]-1=3
Georgia will win
*/
const int N = 1010;
int a[N];
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, s = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        sort(a + 1, a + n + 1);

        /* n=8
         a[1~8] = {1 5 6 7 9 12 14 17}
         a[8]-a[7]-1=17-14-1=2  1号台阶 √
         a[7]-a[6]-1=14-12-1=1  2号台阶 ×
         a[6]-a[5]-1=12- 9-1=2  3号台阶 √
         a[5]-a[4]-1=9-7-1  =1  4号台阶 ×
         a[4]-a[3]-1=7-6-1  =0  5号台阶 √
         a[3]-a[2]-1=6-5-1  =0  6号台阶 ×
         a[2]-a[1]-1=5-1-1  =3  7号台阶 √

         需要计算
         1号台阶    3号台阶      5号台阶      7号台阶
         2      ∧    2     ∧     0    ∧     3
        */
        for (int i = 1; i <= n; i += 2) //枚举 奇数阶台阶
        {
            s ^= a[n - i + 1] - a[n - i] - 1;
            printf("i=%d,a[%d]-a[%d]-1=%d\n", i, n - i + 1, n - i, a[n - i + 1] - a[n - i] - 1);
        }

        //异或和为0，先手必败；否则先手必胜
        puts(s == 0 ? "Bob will win" : "Georgia will win");
    }

    return 0;
}