POJ 1704 博弈
这题看懂了就是一个staircase nim,没看懂就比较难做了.对于staircase nim的理解,你可以这样想.把每两个chess的距离算出来,那么移动任何一个chess的话,会同时改变和这个chess相关的两个距离,左边的减少,右边的增加,这样你就可以把右边的看成是低的梯子,左边是高的梯子.然后用staircase nim来解决就OK了,staircase nim只与奇数层的梯子上的石子数有关,这个可以用P-positon和N-position的定义归纳来证明[每一个P-position只能到达N-position和每个N-position都能达到至少一个P-position].具体关系就是把所有的奇数层上的石子单独拿出来,做一般的nim游戏,如果某个点使P-position的话,那么还原之后的这个staircase nim也处于一个P-position的状态上.反之亦然.
代码如下:
/
ID:qcx97811
LANG:C
TASK:POJ_1704
/
#include
#include
#include
#include
int n,t
int num[1006],nim[1006],idx
int cmp(const void a,const void b)
{
if(((int )a) > ((int )b))
return 1
if(((int )a) < ((int )b))
return -1
return 0
}
int main(void)
{
int i,j,k
scanf(“%d”,t);
while(t–)
{
scanf(“%d”,n);
for(i=0i<n;i++)
scanf(“%d”,num[i]);
num[n]=0
qsort(num,n+1,sizeof(num[0]),cmp);
for(i=n,j=0i>;0;i–,j++)
{
nim[j]=num[i]-num[i-1]-1
}
k=0
for(i=0i<j;i+=2)
k^=nim[i];
if(0==k)
printf(“Bob will win\n“);
else
printf(“Georgia will win\n“);
}
return 0
}
ID:qcx97811
LANG:C
TASK:POJ_1704
/
#include
#include
#include
#include
int n,t
int num[1006],nim[1006],idx
int cmp(const void a,const void b)
{
if(((int )a) > ((int )b))
return 1
if(((int )a) < ((int )b))
return -1
return 0
}
int main(void)
{
int i,j,k
scanf(“%d”,t);
while(t–)
{
scanf(“%d”,n);
for(i=0i<n;i++)
scanf(“%d”,num[i]);
num[n]=0
qsort(num,n+1,sizeof(num[0]),cmp);
for(i=n,j=0i>;0;i–,j++)
{
nim[j]=num[i]-num[i-1]-1
}
k=0
for(i=0i<j;i+=2)
k^=nim[i];
if(0==k)
printf(“Bob will win\n“);
else
printf(“Georgia will win\n“);
}
return 0
}
