HDU 4115 石頭剪刀布：2-SAT 建模求解博弈策略

HDU 4115 石頭剪刀布：2-SAT 建模求解博弈策略

Alice 與 Bob 玩 N 輪猜拳，Bob 每輪出拳固定。Alice 每輪只能選「平局」或「贏」，不可輸。M 個約束：第 u 輪與第 v 輪出拳相同 (w=0) 或不同 (w=1)。判斷 Alice 是否存在合法策略。經典 2-SAT 問題。

2-SAT 建模

每輪 Alice 有兩種選擇：設變量 x_i 表示第 i 輪選「平局」，則 ¬x_i 表示選「贏」。
對於 Bob 出拳 b_i：
- 平局：Alice 出 b_i
- 贏：Alice 出 (b_i+1)%3

約束轉化

第 u 輪選擇 a_u ∈ {b_u, (b_u+1)%3}，第 v 輪選擇 a_v ∈ {b_v, (b_v+1)%3}。
若 w=0（相同）：a_u == a_v → 四種組合中不相等的加衝突邊。
若 w=1（不同）：a_u != a_v → 相等的組合加衝突邊。

建圖邏輯

int dfn[N], low[N], scc[N], stk[N], top, idx, sccCnt;
bool inStk[N];

void tarjan(int u) {
    dfn[u]=low[u]=++idx; stk[++top]=u; inStk[u]=true;
    for (int e=head[u];~e;e=nxt[e]) {
        int v=to[e];
        if (!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); }
        else if (inStk[v]) low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u]) {
        sccCnt++;
        do { scc[stk[top]]=sccCnt; inStk[stk[top]]=false; } while (stk[top--]!=u);
    }
}

bool solve(int n) {
    for (int i=0;i<2*n;i++) if (!dfn[i]) tarjan(i);
    for (int i=0;i

完整代碼框架

複雜度

變量數：2N ≤ 20000
邊數：每個約束最多加 8 條邊，總邊 ≤ 8M
Tarjan：O(V+E)，極快。


總結
HDU 4115 是 2-SAT 經典應用。關鍵步驟：

1. 將每輪選擇建模為布爾變量。

2. 根據 Bob 固定出拳，列出兩種選擇的實際出拳。

3. 將「相同/不同」約束轉化為變量賦值的衝突條件。

4. 衝突對應蕴含邊，構建蕴含圖。

5. Tarjan SCC 判斷可滿足性。

模板化後極易實現，是 2-SAT 入門佳作。