P1288 取數游戲II

luogu原題

最近剛學了博弈論，拿來練練手qwq

其實和數值的大小並沒有關係

我們用$N/P$態來表示必勝/必敗狀態

先在草稿紙上探究硬幣在最左側（其實左右側是等價的）的一條長鏈的$N/P$態，設鏈長為$n$

我們用$1$代替其他所有非$0$數

$n=2: 11$  $N$態

$n=3: 111$ $P$態

......

我們發現，當$n$為奇數時，則為$P$態，反之為$N$態。

於是我們就找到了硬幣在最左側時的答案。

但是，實際上硬幣並不一定在最左側

此時我們只需要分別判斷硬幣左邊的鏈和硬幣右邊的鏈，只要有一種為$N$態，則Alice贏，反之Bob贏（雙方都會選擇最優走法）。

代碼如下：

#include<iostream>
#include<cstdio>
using namespace std;
int a[43],n,l=1,r=1; //記得要算上硬幣所在的點
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),a[n+i]=a[i];
    for(int i=n;a[i];--i) ++l; //左側判斷
    for(int i=n+1;a[i];++i) ++r; //右側判斷
    if((l&1)&&(r&1)) printf("NO"); //任何一個為奇數則Alice贏
    else printf("YES");
    return 0;
}