UVA LA 4255 Guess：前綴和 + 拓撲排序解區間正負約束

題目大意

給定長度為 n 的序列，所有區間 [i, j] 的和的符號（+/-/0）已知。求任意一組滿足條件的序列。
n ≤ 19，多測試用例。

核心建模：前綴和變數 + 差分約束

1. 定義前綴和

S[0] = 0, S[k] = a[1] + ... + a[k] (1 ≤ k ≤ n)。
區間和 sum(i, j) = S[j] - S[i-1]。

2. 符號轉為不等式

• sum(i, j) > 0 → S[j] > S[i-1] → 有向邊 i-1 → j（權重 1）
• sum(i, j) < 0 → S[j] < S[i-1] → 有向邊 j → i-1（權重 1）
• sum(i, j) = 0 → S[j] = S[i-1] → 雙向邊 i-1 ↔ j（權重 0），即強連通分量

3. 處理等號：縮點

用 dis[u][v] = 0 表示 u=v。構圖時先將所有 0 關係合併：
遍歷節點，若 dis[u][v]==0 則賦予相同拓撲序值。

算法流程

1. 讀入符號矩陣，構建 dis[n+1][n+1] 關係矩陣（-1/0/1）與入度 du[]
2. 拓撲排序（Kahn 算法）賦值 suf[]（前綴和相對值）
3. 將 suf[0] 歸零，輸出 a[i] = suf[i] - suf[i-1]

關鍵代碼片段

// 構圖
for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) {
        char c; scanf(" %c", &c);
        if (c == '+') { du[j]++; dis[i-1][j] = 1; dis[j][i-1] = -1; }
        else if (c == '-') { du[i-1]++; dis[j][i-1] = 1; dis[i-1][j] = -1; }
        // '0' 保持 dis=0
    }

// 拓撲賦值
int tot = 0, val = 0;
while (tot < n + 1) {
    for (int i = 0; i <= n; i++) if (du[i] == 0) {
        // 收集所有與 i 相等的點
        vector same = {i};
        for (int j = 0; j <= n; j++)
            if (i != j && du[j] != -1 && dis[i][j] == 0)
                same.push_back(j);
        // 賦相同值
        for (int x : same) suf[x] = val;
        val++; tot += same.size();
        // 刪除邊
        for (int x : same)
            for (int r = 0; r <= n; r++)
                if (du[r] != -1 && dis[x][r] == 1) du[r]--;
        for (int x : same) du[x] = -1;
    }
}

// 輸出原序列
int base = suf[0];
for (int i = 1; i <= n; i++) {
    if (i > 1) putchar(' ');
    printf("%d", suf[i] - base - (suf[i-1] - base));
}

正確性論證

• 充分性：拓撲序滿足所有嚴格不等式；等號組內賦相同值滿足等式。
• 必要性：若存在解，前綴和必須滿足所有不等式/等式，構成的圖必無正權環（否則矛盾），拓撲序必存在。
• 任意解：拓撲序值僅保證偏序關係，具體數值可任意縮放平移，輸出差分即得合法序列。

複雜度

• n ≤ 19 → O(n³) 構圖 + O(n²) 拓撲，極快
• 空間 O(n²)

關鍵細節

總結

本題展示了 「區間和符號 → 前綴和差分 → 偏序圖 → 拓撲排序賦值」 的經典建模鏈路。核心洞見：等號意味著變量合併（強連通分量），不等號意味著偏序關係。這類「符號約束求任意解」問題，拓撲排序是通用利器。