您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1733 Parity Game：帶權並查集 + 離散化

編輯：關於C++

題目大意

有 n (≤ 10¹⁰) 個節點，q (≤ 10000) 條約束：區間 [a, b] 的和為奇/偶。按順序加入約束，求最長前綴長度 x 使前 x 條約束無矛盾。節點編號極大，但實際用到的 ≤ 2q+2 個，需離散化。

核心模型：帶權並查集維護前綴和奇偶性

定義 S[i] = 前 i 個數的和。約束「a 到 b 和為奇/偶」 ⇔ S[b] - S[a-1] ≡ parity (mod 2)。即 S[b] ≡ S[a-1] + parity (mod 2)。
將 S[i] 視為並查集節點，邊權為模 2 的差值。合併時維護 rel[x] = x 到根的奇偶和。
檢測矛盾：若 find(a-1) == find(b)，則檢查 (rel[a-1] - rel[b]) % 2 == parity。

關鍵代碼


#include 
#include 
using namespace std;
const int MAXQ = 10005;
int pa[MAXQ*2], rel[MAXQ*2];
int L[MAXQ], R[MAXQ];
char type[MAXQ][10];
map mp;

int find(int x) {
    if (pa[x] != x) {
        int root = find(pa[x]);
        rel[x] = (rel[x] + rel[pa[x]]) % 2;
        pa[x] = root;
    }
    return pa[x];
}

void unite(int x, int y, int parity) { // S[y] - S[x] = parity
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    // 使 ry 掛在 rx 下，並更新 rel[ry]
    pa[ry] = rx;
    rel[ry] = (parity + rel[x] - rel[y] + 2) % 2;
}

int main() {
    int n, q;
    while (~scanf("%d", &n)) {
        scanf("%d", &q);
        mp.clear();
        int cnt = 0;
        for (int i = 1; i <= q; ++i) {
            scanf("%d%d%s", &L[i], &R[i], type[i]);
            long long u = (long long)L[i] - 1, v = R[i];
            if (!mp.count(u)) mp[u] = ++cnt;
            if (!mp.count(v)) mp[v] = ++cnt;
        }
        for (int i = 1; i <= cnt; ++i) { pa[i] = i; rel[i] = 0; }
        int ans = q;
        for (int i = 1; i <= q; ++i) {
            int u = mp[L[i]-1], v = mp[R[i]];
            int p = (type[i][0] == 'e') ? 0 : 1; // even=0, odd=1
            int ru = find(u), rv = find(v);
            if (ru != rv) {
                unite(u, v, p);
            } else {
                if ((rel[u] - rel[v] + 2) % 2 != p) {
                    ans = i - 1;
                    break;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}