UVA 11249 Game：組合博弈 SG 函數與必勝態推導

UVA 11249 Game：組合博弈 SG 函數與必勝態推導

題目大意

兩堆石子 (a,b)，雙方輪流操作。每回合可：
1. 選一堆，取任意多（≥1）。
2. 兩堆同時取，要求 取數之差的絕對值 < K。
無法操作者負。給定 K 與多組 (a,b)，判斷先手勝負。

核心理論：Wythoff 遊戲推廣

經典 Wythoff 遊戲（K=1，即兩堆取數相等）的 P-位（必敗態）為 (⌊kφ⌋, ⌊kφ²⌋)，φ=(1+√5)/2。
本題 K>1 時，P-位滿足遞推：
設 f(x) 為與 x 配對的 P-位較大值（x < f(x)）。
f(0)=0。對 x=1,2...，f(x) 為最小的未被使用的整數，使得 f(x) - x ≥ K+1 且與之前所有 P-位差值不衝突。
實際構造：mv 為當前最大已配對的 x，f(x) = f(mv) + x - mv + K + 1。
預處理 f[0..1e5]，查詢時 min(a,b)=p, max(a,b)=q，若 f[p]==q 則 LOSING，否則 WINNING。

代碼（C++）

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100000;
int K, N, f[MAXN+5];

void init() {
    memset(f, -1, sizeof(f));
    int mv = 0; f[0] = 0;
    for (int i = 1; i <= MAXN; ++i) {
        if (f[i] == -2) continue;  // 已被作為大值標記
        int nxt = f[mv] + i - mv + K + 1;
        if (nxt > MAXN) break;
        f[i] = nxt;
        f[nxt] = -2;  // 標記大值
        mv = i;
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &K, &N);
        init();
        for (int i = 0; i < N; ++i) {
            int a,b; scanf("%d%d", &a,&b);
            int p = min(a,b), q = max(a,b);
            puts(f[p] == q ? "LOSING" : "WINNING");
        }
        puts("");
    }
    return 0;
}

關鍵點

• P-位構造利用「差值單調遞增」性質，線性時間預處理。
• f[x] = -2 標記大值，避免重複使用。
• 查詢 O(1)，總複雜度 O(MAXN + T·N)。

本題是 Wythoff 遊戲的推廣，展示了組合博弈中「互補序列」構造 P-位的通用技巧。