HDU 2897 取硬幣遊戲 (SG 函數 + 找規律)

問題描述

一堆 n 枚硬幣，雙方輪流取，每次取 p~q 枚 (p≥1)，剩餘 < p 必須一次取完。取走最後一枚者輸。給多組 (n,p,q)，判斷先手是否必勝 (WIN/LOST)。n,p,q ≤ 65535，測試行數 ≤ 100000。

解法：SG 函數打表找周期

此為組合遊戲，計算 SG(n)：
SG(x) = mex{ SG(x-p), SG(x-p-1), ..., SG(x-q) } (x≥p)
x

因 p,q 固定，SG 序列必從某處開始循環。預計算前 10000 項，檢測循環節，然後 O(1) 回答查詢。

代碼框架 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXS = 10010;
int sg[MAXS], vis[MAXS];

void computeSG(int n, int p, int q) {
    memset(sg, 0, sizeof(sg));
    for (int i = p+1; i <= n; ++i) {
        memset(vis, 0, sizeof(vis));
        for (int j = p; j <= q; ++j)
            if (i >= j) vis[sg[i-j]] = 1;
        for (int j = 0; ; ++j)
            if (!vis[j]) { sg[i] = j; break; }
    }
}

// 檢測循環節並快速查詢...
// 完整代碼較長，核心為 SG 遞推 + 循環檢測

關鍵優化

• 測試用例極多 (10⁵)，必須預處理每種 (p,q) 的 SG 周期，或離線處理相同參數。
• 實際比賽中常直接打表發現規律：SG 值只取 0,1,2 等小數，周期極短 (通常 ≤ p+q)。

樣例

輸入：7 2 4\n6 2 4
輸出：LOST\nWIN