题解 P1288 【取数游戏II】

· · 题解

楼下说的都很好，但是我想应该没有那么复杂

首先，对于一条链a1,a2,a3,a4......0 如果是偶数条边，那么现手一定赢，因为他每一次都只用把后面一条取完，例如

5 4 3 6 5 0

先手取完5，后手没法回到前一个位置，而无论接下来后手去多少，先手继续取完3，再然后取完5，后手没办法再去，先手赢。就这样，如果从起点到第一个出现0的地方一共有偶数条边，先手可以一步一步将后手被迫向前逼近，直到无法移动（由于是环，还应该考虑向后逼近）。

同样的，如果这有奇数个，那么先手第一步无论怎么取，都将自己置于一个必败状态（此时对于后手来说边数变成偶数），就一定没有必胜状态

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,a[25];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1;i<=n;i++)
        if(a[i]==0){
            if(i%2==0)return puts("YES"),0;
            break;
        }
    for(int i=n;i>=1;i--)
        if(a[i]==0){
            if((n-i+1)%2==0)return puts("YES"),0;
            break;
        }
    puts("NO");
    return 0;
}