HDU 4315 阶梯博弈变形

n个棋子,其中第k个是红色的,每个棋子只能往上爬,而且不能越过、重叠其他棋子,谁将红色棋子移到顶部谁赢。

由于只能往上爬,所以很像阶梯博弈。这题有2个限制,棋子不能重叠,有红棋存在

首先不考虑红色棋,那么我们可以视棋于棋间的距离为石子堆,这样棋子两两分组就是奇数堆,组与组间的距离就是偶数堆。

有个特殊情况k=2时,此时第一个区间石子数要减小1,不能移完,否则后手直接就能取胜了。

/** @Date    : 2017-10-13 23:13:24
* @FileName: HDU 4315 阶梯博弈变形.cpp
* @Platform: Windows
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version : $Id$
*/
#include <bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std; const int INF = 0x3f3f3f3f;
const int N = 1e3+20;
const double eps = 1e-8; int a[N];
int main()
{
int n, k;
while(~scanf("%d%d", &n, &k))
{
a[0] = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d", a + i);
}
if(k == 1)
{
printf("Alice\n");
continue;
}
int sgs = 0;
if(n % 2)
{
for(int i = 0; i + 1 <= n; i += 2)
sgs ^= a[i + 1] - a[i] - 1;
if(k != 2)//特殊情况
sgs ^= a[1] ^ (a[1] - 1);
}
else
{
for(int i = 1; i + 1<= n; i += 2)
sgs ^= a[i + 1] - a[i] - 1;
}
if(sgs)
printf("Alice\n");
else printf("Bob\n");
}
return 0;
}//两两分组
上一篇:jquery 取id模糊查询


下一篇:戏说 Spring MVC 框架