HDU 4915 Parenthese Sequence：括號序列唯一性判定

問題描述

給定由 (, ), ? 組成的字符串，? 可替換為左或右括號。判斷合法括號匹配方案數：0（None）、1（Unique）、≥2（Many）。

核心思路：雙向掃描維護上下界

對於任意前綴，左括號數 - 右括號數 = 當前「未匹配左括號數」（稱作 balance）。合法序列要求：

• 所有前綴 balance ≥ 0
• 全串 balance = 0

? 引入不確定性。從左到右掃描，維護 balance 的可能範圍 [L, R]：

• 遇到 (：L++, R++
• 遇到 )：L--, R--；若 R < 0 則無解；L = max(L, 0)
• 遇到 ?：L--, R++；同理 L = max(L, 0)

同理從右向左掃描維護右括號視角的範圍。若左掃描最終 L=0 且右掃描最終 L=0，則至少有一解。

判斷唯一/多解

枚舉每個 ? 位置 i，假設它為 (，檢查左側範圍 [L₁, R₁] 和右側範圍 [L₂, R₂] 是否有交集（即存在某個 balance 使左右銜接合法）。再假設為 ) 檢查。若兩種假設都合法，則有多解；若所有 ? 只有一種合法，則唯一解。

參考代碼（C++）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1e6 + 5;
char s[MAXN];
int n, L[MAXN][2], R[MAXN][2]; // [0]=下界, [1]=上界

// 檢查位置 x 為 ? 時，能否分別取 ( 和 )
bool check(int x) {
    // 假設為 (
    int ldown = L[x-1][0] + 1;
    int lup   = L[x-1][1] + 1;
    if (ldown > R[x+1][1] || lup < R[x+1][0]) return false;
    // 假設為 )
    int rdown = R[x+1][0] + 1;
    int rup   = R[x+1][1] + 1;
    if (rdown > L[x-1][1] || rup < L[x-1][0]) return false;
    return true;
}

int judge() {
    n = strlen(s+1);
    if (n & 1) return 0; // 奇長度必無解
    memset(L[0], 0, sizeof(L[0]));
    memset(R[n+1], 0, sizeof(R[n+1]));
    // 從左向右
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(') { L[i][0] = L[i-1][0]+1; L[i][1] = L[i-1][1]+1; }
        else if (s[i] == ')') {
            if (L[i-1][1] == 0) return 0;
            L[i][0] = (L[i-1][0]==0 ? 2 : L[i-1][0]) - 1;
            L[i][1] = L[i-1][1] - 1;
        } else { // ?
            L[i][0] = (L[i-1][0]==0 ? 2 : L[i-1][0]) - 1;
            L[i][1] = L[i-1][1] + 1;
        }
    }
    // 從右向左
    for (int i = n; i >= 1; i--) {
        if (s[i] == ')') { R[i][0] = R[i+1][0]+1; R[i][1] = R[i+1][1]+1; }
        else if (s[i] == '(') {
            if (R[i+1][1] == 0) return 0;
            R[i][0] = (R[i+1][0]==0 ? 2 : R[i+1][0]) - 1;
            R[i][1] = R[i+1][1] - 1;
        } else {
            R[i][0] = (R[i+1][0]==0 ? 2 : R[i+1][0]) - 1;
            R[i][1] = R[i+1][1] + 1;
        }
    }
    // 枚舉 ?
    for (int i = 1; i <= n; i++)
        if (s[i] == '?' && check(i)) return 2; // Many
    return 1; // Unique
}

int main() {
    while (scanf("%s", s+1) == 1) {
        int flag = judge();
        if (flag == 2) puts("Many");
        else if (flag == 1) puts("Unique");
        else puts("None");
    }
    return 0;
}

複雜度分析

• 時間：O(n)，三次線性掃描
• 空間：O(n)
• 適用於 n ≤ 1e6

關鍵技巧

1. 區間上下界：用 [L, R] 表示所有可能的 balance 值
2. 雙向掃描：左掃描管前綴合法，右掃描管後綴合法
3. 銜接判斷：中間位置左右範圍有交集即可銜接