[HDU4315]Climbing the Hill（阶梯博弈）

题目描述

传送门

题解

和上一道题很像，但是有一个区别就是，山顶可以同时存在多个人，但是其它位置不可以。
首先考虑没有king的情况，也就是说没有合法操作的那个人判负。这样的话，可以发现和上一道题的阶梯博弈是等效的。只需要将区间的距离看成是一堆一堆的石子，然后将编号为奇数的堆异或起来就行了。
为什么是等效的呢？因为如果我们将编号为奇数的堆看成一个一个的区间的话，如果某一个人移动了区间的左端点，那么下一个人就可以模仿它移动区间的右端点相同的距离，这样区间的长度没变，先手后手的顺序也没变。那么我们就可以说，只有区间的长度是有用的因素，与区间的位置无关。如果某一个人移动了区间的右端点，就相当于是从石子堆中取出了一些，这就是一个正常的Nim游戏。
所以我们的目标状态只是将所有的区间挪成空区间，没有必要管区间的位置在哪里。并且，当所有的区间都是空区间了之后，再将它移动到山顶时，先手后手的顺序还是没有变化，所以说，和上一道题是完全等效的。
但是有一个比较特殊的地方，就是king需要特判一下。当一共有奇数个人并且king在第二个人时，需要将第一个区间的长度-1，因为如果将第一个区间直接移动到山顶的话其实是一个必胜态，只有将第一个区间留下才是必败态。并且如果king在第一个人的话Alice必胜。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 1005

int n,k,cnt,ans;
int a[N],b[N];

int main()
{
    while (~scanf("%d%d",&n,&k))
    {
        ans=0;cnt=0;
        for (int i=1;i<=n;++i) scanf("%d",&a[i]);
        if (k==1)
        {
            puts("Alice");
            continue;
        }
        if (n%2==0||k!=2) a[0]=-1;
        else a[0]=0;
        for (int i=n;i>=1;i-=2) ans^=a[i]-a[i-1]-1;
        if (!ans) puts("Bob");
        else puts("Alice");
    }
    return 0;
}