http://acm.hdu.edu.cn/showproblem.php?pid=4315
题意:
由上至下有多个格子,最顶端的是山顶,有多个球,其中有一个球是king,每次可以将球向上移动任意个格子,但是不可以跨越别的球。现将king移动到山顶者赢。
思路:
和poj1704是差不多的,如果不懂阶梯博弈的话,可以看看我的这篇博客http://www.cnblogs.com/zyb993963526/p/7868315.html。
现在还是两两分组,谁没空格可移肯定是必败状态,为什么呢?首先,如果king是在每组中的右边,那么这肯定是必败的,如果king在每组中的左边,当先手移动后,后手可以选择是否药改变当前状态,所以还是必败的。
但是要注意总球数是奇数并且king在第二个的情况,此时第一个求会和-1相邻,但是这样相邻后第一个球就是在0的位置,也就是到山顶没了,这样先手直接就赢了,所以此时要将第一组的格子数-1,不能移动到山顶。
#include<iostream>
#include<cstdio>
using namespace std; int n, k;
int a[]; int main()
{
while(~scanf("%d%d",&n,&k))
{
for(int i=;i<=n;i++) scanf("%d",&a[i]);
if(k==)
{
puts("Alice");
continue;
}
a[] = -;
int ans = ;
if(n% && k==) a[]=;
for(int i=n;i>;i-=)
{
ans^= a[i]-a[i-]-;
}
if(ans) puts("Alice");
else puts("Bob");
}
return ;
}