有关阶梯博弈的别人的博客戳这里 hdu 4315 题意：在山上有n个人，每个人编号是1~n，这些位置只能同时被一个人占据，但是山顶可以同时被多个人占据，距离山顶第k近的是King，现在Alice和Bob开始向上送人，条件是不能跨越前面最近的人，问在Alice先手，双方最优的条件下谁能把King送到山顶。 思路：这道题可以转化为Nim博弈或者阶梯博弈； 从后往前将两个人分成一组，一组的长度可以看做这堆有多少个石子； 当有奇数个人的时候，第一个的长度就是其与0之间的距离，但是，当k为2的时候先手肯定不会吧第一个直接移动到山顶，应为这样后手就赢了，所以如果k!=2则第一个区间就会多一种走0号位置的选择，然后就是按照Nim博弈来做就好了； 如果将组与组之间的距离看作是偶数阶梯上的石头的话，就是阶梯博弈； 不理解的可以戳这里
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int main() { int n,k; while(~scanf("%d%d",&n,&k)) { int x[1010]; for(int i=1;i<=n;i++) scanf("%d",&x[i]); if(k==1) { printf("Alice\n"); continue; } int ans=0; if(k!=2) x[0]=-1;//可以走到0 else x[0]=0;//不能走到0 for(int i=n;i>=1;i-=2) ans^=x[i]-x[i-1]-1; if(ans) printf("Alice\n"); else printf("Bob\n"); } }