Codeforces Round #254 Div.2 A/B 題解：棋盤著色與化學實驗危險度

Problem A: DZY Loves Chessboard

題意

n×m 棋盤，'.' 為好格，'-' 為壞格。好格需填 'W' 或 'B'，使相鄰 (上下左右) 好格顏色不同。輸出任一合法方案。

核心觀察

棋盤天然二分圖：(i+j)%2 決定顏色。直接按座標奇偶性著色，忽略 '-', 即滿足條件。

正確解法

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        vector g(n);
        for (int i=0;i> g[i];
        for (int i=0;i
原碼錯誤分析：原嘗試掃描四鄰域動態決定顏色，但順序依賴導致衝突 (一格鄰域同時有 W 和 B)。棋盤著色屬於二分圖著色，直接用座標奇偶性為全局最優解。



Problem B: DZY Loves Chemistry
題意
n 種化學品，m 對反應關係。依序倒入試管，危險度初始 1。若倒入的化學品與試管內現有化學品有反應，危險度 ×2。求最大可能危險度。

核心觀察
反應關係形成無向圖。每個連通分量內，第一個化學品不增加危險度，其餘每個都至少與前面某個有反應 (因連通)，故該分量貢獻 2^(size-1)。總危險度 = 2^(n - 連通分量數)。

並查集解法
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector p;
    DSU(int n): p(n+1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x]==x?x:p[x]=find(p[x]); }
    void unite(int a, int b) { a=find(a); b=find(b); if(a!=b) p[a]=b; }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        DSU dsu(n);
        for (int i=0,u,v;i>u>>v; dsu.unite(u,v); }
        int comp = 0;
        for (int i=1;i<=n;++i) if (dsu.find(i)==i) ++comp;
        // 2^(n-comp) 用長整型或大整數 (n≤50, 2^50 < 1e16, long long 足夠)
        long long ans = 1LL << (n - comp); // n≤50 時安全
        cout << ans << '\n';
    }
    return 0;
}


複雜度

A: O(n·m) 直接輸出。
B: O(n + m α(n)) 並查集，極快。


總結

A 題關鍵是識別棋盤二分圖性質，避免局部貪心導致衝突。
B 題關鍵是將「最大危險度」轉化為「連通分量計數」，並查集是標準工具。