HDU 3951 Coin Game

2014-11-24 09:58:06 · 作者: · 浏览: 2

题意:给你n个硬币排成一圈,编号1-n,只能翻转连续的1~k个的硬币。翻最后一枚硬币者赢。

思路:博弈

1) 若k=1,则一次只能去翻一枚,奇数先手赢,偶数后手赢。

2)若k>1:

a: 先手一次翻完,先手赢;

b: 先手不能翻完,第一次必定断环。只要后手一次翻完,或将其分为相等数量的两段,

之后先手怎么操作后手就怎么操作,后手必赢。

[cpp]
#include
int main()
{
int t,i,n,k;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%d%d",&n,&k);
if(n<=k)
printf("Case %d: first\n",i);
else if(k==1)
{
if(n%2==1) printf("Case %d: first\n",i);
else printf("Case %d: second\n",i);
}
else printf("Case %d: second\n",i);
}
return 0;
}