【筆記】Nim

【範例】LeetCode 292. Nim Game

  • 兩個玩家輪流拿石頭,每次可以拿1~3顆石頭。拿到最後一顆石頭的人獲勝。
  • 當石頭數目為 4 的倍數時,對手必勝。
class Solution {
public:
    bool canWinNim(int n) {
        return (n % 4 != 0);
    }
};
//【範例】LeetCode 292. Nim Game
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1000;
int dp[maxn+5];

int solve(int x){
    // 定義遞迴終點
    if (x < 0) return 0;
    if (dp[x] != 0) return dp[x];
    // 枚舉所有移動
    int mn = 0;
    mn = min(mn, solve(x-1)); //先手拿1顆石頭
    mn = min(mn, solve(x-2)); //先手拿2顆石頭
    mn = min(mn, solve(x-3)); //先手拿3顆石頭
    if (mn == -1) return dp[x] = 1; //只要有一步能讓後手輸
    else return dp[x] = -1; //後手不管怎樣都贏
}

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        //dp: -1 (輸), 0 (未定), 1 (贏)
        memset(dp, 0, sizeof(dp));
        solve(n); //先手一開始看到n顆石頭
        cout << (dp[n] == 1) << endl; 
    }
}
  • 觀察找規律:數據範圍大,可以利用小數據dp找規律。
  • 神奇的技巧 XOR
    • 【範例】有 n 堆石頭,每堆初始有 Ai 顆,每次可以挑選一堆,從該堆拿任意顆,拿到最後一顆者輸。
    • 把目前的所有堆的石頭數量 XOR 得到值 x。
    • 若 x 非 0,則必然存在一步使其值變為 0。
    • 若 x 為 0,則所有移動都將使其值非 0。
    • 最後的贏點 x 為 0,且石頭在慢慢減少。
    • 若初始 x 為 0,則先手必勝,反之,後手必勝。
分享本文 Share with friends