首页 > 代码库 > HDU 4315:Climbing the Hill(阶梯博弈)

HDU 4315:Climbing the Hill(阶梯博弈)

http://acm.hdu.edu.cn/showproblem.php?pid=4315

题意:有n个人要往坐标为0的地方移动,他们分别有一个位置a[i],其中最靠近0的第k个人是king,移动的时候在后面的人不能越过前面的人,先把king送到0的人胜。

思路:阶梯博弈。把n个人两两配对,形成一个组,即a[i]和a[i+1]是一个组,a[i+2]和a[i+3]是一个组,把a[i]和a[i+1]的距离当成阶梯博弈中的奇数阶的值,a[i+1]和a[i+2]的距离当成偶数阶(不用考虑)。首先k=1时候先手赢。偶数情况下,两两相邻是必败态,因为如果先手移动前面的,后手一定可以使得局面还是两两相邻,然后先手移动king前面的人的时候,后手只要把king移动到终点。如果n是奇数的话,把a[1]走到终点就是偶数的情况。所以如果k是第二个人并且n是奇数的话,第一个人只能移动到1的位置,否则k就能直接移动到0了,因此a[1]要-1。

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 #define N 1010
 5 int id[N];
 6 int c[N];
 7 
 8 int main() {
 9     int n, k;
10     while(scanf("%d%d", &n, &k) != EOF) {
11         for(int i = 1; i <= n; i++) scanf("%d", id+i);
12         if(k == 1) {
13             puts("Alice");
14         } else {
15             int ans = 0;
16             if(n & 1 && k == 2) id[1]--;
17             for(int i = 2 + (n & 1); i <= n; i += 2)
18                 ans ^= (id[i] - id[i-1] - 1);
19             if(n & 1) ans ^= id[1];
20             if(ans) puts("Alice");
21             else puts("Bob");
22         }
23     }
24     return 0;
25 }

 

HDU 4315:Climbing the Hill(阶梯博弈)