HDU 4146 詳解：Flip Game 矩陣翻轉位運算優化

題目大意

N×N 棋盤（N ≤ 1000），每格黑/白。Q 次操作（Q ≤ 100,000），操作 (x,y) 翻轉第 x 行和第 y 列所有棋子（交點 (x,y) 翻兩次等價不翻）。求最終白棋數。多測試用例（T ≤ 20）。

核心洞察：翻轉次數奇偶性

每格 (i,j) 受影響條件：操作的行 = i 或列 = j。
總翻轉次數 = rowFlip[i] + colFlip[j]（(i,j) 被計算兩次，但模 2 下 2 ≡ 0，不影響奇偶）。
最終顏色 = 初始顏色 ⊕ (rowFlip[i] + colFlip[j] % 2)。

算法流程

1. 讀取初始棋盤，統計初始白棋數（可不統計，直接按公式計）
2. 兩個布爾/位數組 rowFlip[N+1], colFlip[N+1] 初始化 0
3. 處理 Q 次操作：rowFlip[x] ^= 1; colFlip[y] ^= 1;（異或 1 實現奇偶切換）
4. 遍歷所有格子 (i,j)：
   • flips = rowFlip[i] ^ colFlip[j]（異或等價模 2 加法）
   • 若 flips == 1：顏色翻轉，初始='b' → 白，初始='w' → 黑
   • 若 flips == 0：顏色不變，初始='w' → 白
5. 統計白棋總數輸出

完整代碼

#include 
using namespace std;

const int MAXN = 1005;
char board[MAXN][MAXN];
bool rowFlip[MAXN], colFlip[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    for (int tc = 1; tc <= T; ++tc) {
        int N; cin >> N;
        for (int i = 1; i <= N; ++i) {
            cin >> (board[i] + 1);  // 從下標 1 開始存，跳過 board[i][0]
        }
        
        fill(rowFlip+1, rowFlip+N+1, false);
        fill(colFlip+1, colFlip+N+1, false);
        
        int Q; cin >> Q;
        while (Q--) {
            int x, y; cin >> x >> y;
            rowFlip[x] = !rowFlip[x];
            colFlip[y] = !colFlip[y];
        }
        
        int white = 0;
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                bool flip = rowFlip[i] ^ colFlip[j];
                if (flip) {
                    if (board[i][j] == 'b') ++white;
                } else {
                    if (board[i][j] == 'w') ++white;
                }
            }
        }
        cout << "Case #" << tc << ": " << white << '\n';
    }
    return 0;
}

關鍵優化點

1. 位運算/布爾陣列：rowFlip/colFlip 只需 0/1，用 bool 或 bitset 節省內存與時間
2. 異或代替模 2：a ^ b 等價 (a+b)%2，無分支更快
3. 輸入優化：ios::sync_with_stdio(false); cin.tie(nullptr);，字符串讀取 cin >> (board[i]+1) 避免逐字符讀取
4. 空間局部性：board[i]+1 使每行從索引 1 開始，遍歷時連續訪問

複雜度分析

• 時間：O(N² + Q) — 初始化 O(N²)，操作 O(Q)，最終統計 O(N²)
• 空間：O(N²) — 棋盤存儲
• N=1000 → N²=10⁶，Q=10⁵，總操作 ~2×10⁶，極快

常見錯誤

• 忘記 (x,y) 翻兩次等價不翻 → 需用異或/模 2 自然處理
• 用 int 計數導致溢出或慢 → 只需奇偶，用 bool
• 輸入讀取慢 → 大數據必開 sync_with_stdio(false)
• 下標越界 → 開 MAXN+5，下標 1..N

總結

HDU 4146 是「二維差分/翻轉奇偶性」的經典應用。核心技巧：將二維翻轉分解為行翻轉 + 列翻轉的獨立奇偶標記，利用 rowFlip[i] ^ colFlip[j] 在 O(1) 計算任意格子最終狀態。避免模擬每次操作翻轉整行整列（O(Q×N) 會超時）。此類「批量翻轉/區間翻轉求最終狀態」問題，奇偶性分解是通用解法。