G59 台阶型 Nim游戏【博弈论】

解析

由于只能向左移，而且不能相互交叉。我们把两个硬币之间的空间看作石子堆，一次左移相当于把某个石子堆(楼梯j)的石子移到了右边那个石子堆(楼梯j-1)，最后的区间相当于最低的一层,题目实质就变成了阶梯博弈。

#include <bits/stdc++.h>
using namespace std;
#define N 1100
int T, n, a[N];
void Solve()
{ 
    scanf("%d", &n);
    a[0] = 0; for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1); 
    int ret = 0;
    for(int i = 1; i <= n; i++) if((n + 1 - i) % 2 == 1) ret = ret ^ (a[i] - a[i - 1] - 1); 
    if(!ret) printf("Bob will win\n"); 
    else printf("Georgia will win\n"); 
} 
int main()
{
    scanf("%d", &T); 
    while(T--)Solve(); 
    return 0; 
}

G59 台阶型 Nim游戏【博弈论】

/*

【解析】
由于只能向左移，而且不能相互交叉。
我们把两个硬币之间的空间看作石子堆，
一次左移相当于把某个石子堆(楼梯j)的石子移到了右边那个石子堆(楼梯j-1)，
最后的区间相当于最低的一层,题目实质就变成了阶梯博弈。
*/

#include<bits/stdc++.h>
using namespace std;
#define N 1100
int T, n,a[N];
void Solve()
{ 
    scanf("%d", &n);
    a[0] = 0; for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1); 
    int ret = 0;
	for(int i = 1; i <= n; i++) if((n + 1 - i) % 2 == 1) ret = ret ^ (a[i] - a[i - 1] - 1); 
    if(!ret) printf("Bob will win\n"); 
    else printf("Georgia will win\n"); 
} 
int main()
{
    scanf("%d", &T); 
    while(T--)Solve(); 
    return 0; 
}