POJ 3537 Crosses and Crosses：博弈論 SG 函數求解井字遊戲必勝態

遊戲規則建模

1×n 棋盤，雙方輪流在空格打叉。首先形成 **連續三個叉** 者獲勝。等價於：在長度為 n 的區間中放置標記，不可在已標記位置放置，且放置後若出現三連標記則贏。
這是一個**無偏組合遊戲**，可用 Sprague-Grundy 定理求解。

SG 函數定義與遞推

sg[len] 表示長度為 len 的連續空段的 SG 值。
在長度 len 段中落子位置 i (1≤i≤len)，該位置及其左右各兩格（共 5 格）變為禁區，將原段分裂為左右兩獨立子段：
左段長 i-3，右段長 len-i-2。
轉移：
sg[len] = mex{ sg[i-3] ^ sg[len-i-2] | 1≤i≤len }

邊界條件

sg[0] = 0;
sg[1] = sg[2] = sg[3] = 1; // 手動預計算小長度
// len≥4 按公式遞推

完整代碼

int sg[2048], vis[2048];
int getSG(int n) {
    if (n < 0) return 0;
    if (sg[n] != -1) return sg[n];
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; ++i) {
        int g = getSG(i-3) ^ getSG(n-i-2);
        vis[g] = 1;
    }
    for (int i = 0; ; ++i) if (!vis[i]) return sg[n] = i;
}

int main() {
    memset(sg, -1, sizeof sg);
    sg[0]=0; sg[1]=sg[2]=sg[3]=1;
    int n;
    while (cin >> n) cout << (getSG(n) ? 1 : 2) << endl; // 1=先手勝, 2=先手敗
    return 0;
}

關鍵點解析

• i-3 和 len-i-2 可能為負，定義 sg[neg]=0。
• mex（最小非負未出現數）計算用 vis[] 標記。
• 先手必勝 ⇔ 初始狀態 SG 值 ≠ 0。

複雜度

狀態數 n ≤ 2000，每狀態 O(n) 轉移，總 O(n^2) ≈ 4e6，預計算後每查詢 O(1)。