取數遊戲II_洛谷1288_博弈

題目描述

有一個取數的遊戲。初始時，給出一個環，環上的每條邊上都有一個非負整數。這些整數中至少有一個0。然後，将一枚硬币放在環上的一個節點上。兩個玩家就是以這個放硬币的節點為起點開始這個遊戲，兩人輪流取數，取數的規則如下：

（1）選擇硬币左邊或者右邊的一條邊，并且邊上的數非0；

（2）将這條邊上的數減至任意一個非負整數(至少要有所減小)；

（3）将硬币移至邊的另一端。

如果輪到一個玩家走，這時硬币左右兩邊的邊上的數值都是0，那麼這個玩家就輸了。

如下圖，描述的是Alice和Bob兩人的對弈過程，其中黑色節點表示硬币所在節點。結果圖(d)中，輪到Bob走時，硬币兩邊的邊上都是0，是以Alcie獲勝。

（a）Alice （b）Bob （c）Alice （d）Bob

現在，你的任務就是根據給出的環、邊上的數值以及起點（硬币所在位置），判斷先走方是否有必勝的政策。

輸入格式：

第一行一個整數N（N≤20），表示環上的節點數。

第二行N個數，數值不超過30，依次表示N條邊上的數值。硬币的起始位置在第一條邊與最後一條邊之間的節點上。

輸出格式：

僅一行。若存在必勝政策，則輸出“YES”，否則輸出“NO”。

Analysis

第一眼看過去毫無想法

第二眼也是

第三眼也是

于是我就可恥地看了一發題解，博弈什麼的果然很難

首先，對于一條鍊a1,a2,a3,a4……0 如果是偶數條邊，那麼現手一定赢，因為他每一次都隻用把後面一條取完，例如

5 4 3 6 5 0

先手取完5，後手沒法回到前一個位置，而無論接下來後手去多少，先手繼續取完3，再然後取完5，後手沒辦法再去，先手赢。就這樣，如果從起點到第一個出現0的地方一共有偶數條邊，先手可以一步一步将後手被迫向前逼近，直到無法移動（由于是環，還應該考慮向後逼近）。

同樣的，如果這有奇數個，那麼先手第一步無論怎麼取，都将自己置于一個必敗狀态（此時對于後手來說邊數變成偶數），就一定沒有必勝狀态

也就是說對于固定的狀态結果也是固定的

感受到nim遊戲的高大上深奧了

下次遇到這種題能做出來吧?

Code

#include <stdio.h>
#include <string.h>
#define rep(i, st, ed) for (int i = st; i <= ed; i += 1)
#define drp(i, st, ed) for (int i = st; i >= ed; i -= 1)
#define fill(x, t) memset(x, t, sizeof(x))
#define N 41
using namespace std;
int num[N];
inline int read(){
    int x = , v = ;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-'){
            v = -;
        }
        ch = getchar();
    }
    while (ch <= '9' && ch >= '0'){
        x = (x << ) + (x << ) + ch - '0';
        ch = getchar();
    }
    return x * v;
}
int main(void){
    int n = read();
    rep(i, , n){
        num[i] = read();
    }
    rep(i, , n){
        if (!num[i]){
            if (i %  == ){
                printf("YES\n");
                return ;
            }
            break;
        }
    }
    drp(i, n, ){
        if (!num[i]){
            if ((n - i + ) %  == ){
                printf("YES\n");
                return ;
            }
            break;
        }
    }
    printf("NO\n");
    return ;
}