题解 P1288 【取数游戏II】

· · 题解

这是一道数学题。。。

 我们来举个例子：有一条边R从x指向y，它的数值大于0，AB对弈，现在A走

 那么如果数值为1，A走过去，数值变为0，B就走不回来了

如果数值为2，A走过去，数值变为1，如果B走回来，A不就死了？我们认为他们都足够聪明，怎么会做这种事情呢？（假设过来的前一条边已经走完了，数值为0）

如果数值大于3（我们假定为3），A走过去，数值变为2，B如果仁慈地走回来，数值变为1，这样不就浪费了一步？

B如果按照题意残忍地用最佳行动走回来，取光所有数值，那么数值变为0，这条路就封死了，A做了一件无意义的事情，还封死了自己可以走的一条路，这对于先手的A而言是不利的，

这两种方法都明显有违双方最优的前提。

[/color][b]所以我们可以知道，无论是A走还是B走，即无论是先手走还是后手走，每走过一条路都一定取完，这样问题就简单了[/b]

因为至少有个0，所以就简单了一点。。谁把对手逼到死路（两边都是0的）就赢了

从起始点开始向两边找，只要有一边到0边距离为奇数就是先手赢反之后手赢

代码如下

#include<cstdio>
#define    judge(value) (value&1)
int n,s[1000];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&s[i]);
    int a=0;while(s[++a]);
    int b=0;while(s[n+1-(++b)]);
    if (judge(--a)||judge(--b))  printf("YES");  else printf("NO");
}