HDU 5229 博弈思維：字串遊戲的先手必勝策略分析

題目大意

給定 N 個字串，從中任選兩個字串 A 和 B。兩位玩家輪流操作，每回合可執行以下兩種操作之一：

• 操作 1：從兩個字串中隨機選一個非空字串，刪除其末尾字元。
• 操作 2：僅當兩字串內容相同且非空時可執行，直接清空兩字串。

無法操作者判負，雙方均採最優策略。求先手獲勝的概率。

核心觀察與策略分析

若初始兩字串相同，先手直接執行操作 2 清空獲勝，屬必勝態。為避免落入此態，雙方會盡量拉大兩字串差距。最優策略為：優先操作長度較短的字串。如此可迫使對手面對「兩字串皆空」或「長度不等的非必勝態」。

經推導，最終勝負僅取決於所選兩字串長度之和：

• 長度和為奇數 → 先手勝
• 長度和為偶數 → 後手勝
• 初始兩字串相等 → 先手勝（屬奇數和特例，因相等意味著長度和為偶數，但操作 2 可直接獲勝）

解題思路

遍歷所有字串，統計：

1. 已出現的奇數長度字串數量
2. 已出現的偶數長度字串數量
3. 與當前字串內容完全相同的先前字串數量

對於第 i 個字串，其與前 i-1 個字串配對時的先手勝局數為：

• 若長度為奇：ou + same_count
• 若長度為偶：ji + same_count

累加所有勝局數，總配對數為 n*(n-1)/2，最後約分輸出勝率分數。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        unordered_map<string, int> cnt;
        long long win = 0, odd = 0, even = 0;
        char s[210005];
        for (int i = 1; i <= n; ++i) {
            scanf("%s", s);
            string str(s);
            win += cnt[str];                    // 相同字串：先手必勝
            cnt[str]++;
            if (strlen(s) & 1) win += even, odd++;
            else win += odd, even++;
        }
        long long total = 1LL * n * (n - 1) / 2;
        long long g = gcd(win, total);
        printf("%lld/%lld\n", win / g, total / g);
    }
    return 0;
}

複雜度分析

• 時間：O(N * L)，L 為字串平均長度
• 空間：O(N * L)，用於存儲字串雜湊表

本題關鍵在於將博弈過程抽象為長度奇偶性的組合計數，避免了複雜的狀態搜索，體現了「博弈思維」中化繁為簡的精髓。