hdu4315 - 阶梯博弈

xiaoxiao2021-03-01  18

题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=4315

题意:就是下面这个图,灰格子是山顶,可以站很多人,其他格子只能站一个人,红色的是king,Alice和Bob轮流移动人,不能跨越,谁先把king移到终点谁就胜利~这题是一个很好的思维题啊~(一共n个人,king在第k个位置)

 思路:

这题和poj1704差不多啊,不同的就是多了一个king,多了一个山顶,我们想怎转换

poj1704是全是黄球,移走最后一个黄球的人胜利,我们的做法是,让两个两个位置成对,若n为奇数,则设第0个位置是0,和第1个位置成对,但是这个题,是让我们看谁移走的红球

若红球在偶数位置上,那么,后手必胜(只要保证king所在球的前一个球是对方移走的就行),若红球在奇数位置上,只需要将红球前一个球移到第1个位置即可

所以与红球的位置无关,我们可按照poj1704方法做,不同的是这里山顶可以站人 ,所以当n为奇数时,设的第0个位置的坐标是-1,因为山顶也可以站人啦。

下面来考虑特殊情况

(1)k=1,那么Alice直接胜

(2)n为奇数,且k=2,那么第0个位置和第1个位置成对,谁先把第1个位置移到-1(山顶)谁必输,所以Alice和Bob都不会这么做,这就相当于第1堆石子数目少了一(不能移到山顶)

为什么不考虑k>2的情况,k>2这时候第1堆的石子数不用发生-1的变化啊,还是正常取,是可以将第1个位置移到山顶的,所以不用限制第1堆的石子数~

代码如下:

#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<cmath> #include<set> #include<string> #include<cstring> #define ll long long using namespace std; const int N=1005; int a[N]; int main(){ int n,k; while(scanf("%d%d",&n,&k)!=EOF){ for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } if(k==1){printf("Alice\n");continue;} int ans=0; if(n%2){ if(k==2)ans^=a[1]-1; else ans^=a[1]; for(int i=3;i<=n;i+=2){ ans^=(a[i]-a[i-1]-1); } } else{ for(int i=2;i<=n;i+=2){ ans^=(a[i]-a[i-1]-1); } } if(ans)printf("Alice\n"); else printf("Bob\n"); } }

艾玛,真的很绕qwq

转载请注明原文地址: https://www.6miu.com/read-4049958.html

最新回复(0)