位元遮罩競賽程式設計：實用指南

一個整數就能代表一整套選擇，而這個簡單的想法解鎖了競賽程式設計中一些最優雅的解法。

位元遮罩（Bitmasking）是一種利用整數的二進位表示來編碼一個子集的技術。如果你有 n 個元素，那麼從 0 到 2ⁿ−1 的每一個數都恰好對應一個子集：某一位為 1 表示該元素被包含，為 0 表示被排除。由於電腦在硬體層面直接操作位元，這些運算的速度極快，這也正是為什麼 位元遮罩競賽程式設計 會出現在從暴力搜尋到進階動態規劃的各個面向。

核心位元運算工具組

在理解位元遮罩之前，你需要熟練掌握六個位元運算子：AND（&）、OR（|）、XOR（^）、NOT（~）、左移（<<）和右移（>>）。在大多數評測系統中，它們大約在初中級階段引入。你會反覆用到的幾個寫法都很簡短：

• 檢查元素 i 是否在集合中：(mask >> i) & 1
• 設定元素 i（加入它）：mask | (1 << i)
• 清除元素 i（移除它）：mask & ~(1 << i)
• 切換元素 i（反轉它）：mask ^ (1 << i)

位元遮罩本質上就是一個被壓縮進單一整數的輕量布林陣列。這種緊湊性正是它的超能力：你可以把整個狀態存進一個變數裡，用一次比較就能對比兩個狀態，還能直接把遮罩當作陣列索引使用。

子集列舉與子遮罩

有兩種列舉模式會一次又一次地出現。第一種是透過讓遮罩從 0 迴圈到 2ⁿ−1，來走訪 n 個元素的每一個子集。當 2ⁿ 個狀態在可承受範圍內時，這是撰寫完全搜尋的自然方式。

第二種更進階，是列舉給定遮罩的子遮罩，也就是該遮罩中已存在元素的每一個子集。經典寫法 for (int s = mask; s > 0; s = (s - 1) & mask) 能高效地走訪它們，對所有遮罩求和後其複雜度為 O(3ⁿ) 而非 O(4ⁿ)。這個技巧是劃分類問題的基礎——你把一個集合拆成若干組，再合併結果。

位元遮罩動態規劃

真正的回報出現在位元遮罩成為動態規劃的狀態時。位元遮罩 DP 在圍繞小規模集合的子集或排列建構的問題上大放異彩。教科書式的例子是旅行推銷員問題：DP 狀態是已走訪城市的集合（即遮罩）加上最後走訪的那座城市。在城市數最多約 20 個時，它能以 O(N² · 2^N) 的時間求解，而這正是因為 N 很小才可行。

同樣的範本也適用於指派問題、漢米頓路徑計數、鋪磚與輪廓線 DP，以及許多謎題式任務。在結構化的競賽進階階梯上，位元遮罩 DP 通常處於 Gold 層級，建立在更早教授的位元運算基礎之上。如果你的目標是那個水準，我們的指導會把每項技術對應到競賽程式設計中分級的題目上，你也可以查閱 USACO 各組別的官方結構，看看位元遮罩在其中的位置。

位元遮罩獎勵的是熟練，而非死記硬背。一旦四個核心操作變得自然而然，DP 狀態幾乎就能自己寫出來。

如何練習

這裡的進步是具體且可衡量的。一條高效的學習路徑大致如下：

1. 反覆練習設定、清除、檢查和切換操作，直到形成本能。
2. 做幾道完全子集列舉的題目，把那個迴圈內化於心。
3. 從零實作 TSP，然後把範本改造到一道新題上。
4. 進階到子遮罩列舉和劃分類任務。

由於組別、報名資格時間窗口和評分分數線可能逐賽季變化，請始終在官方賽事網站上確認當前的規則與報名詳情，而不要依賴一個固定的數字。對於同時探索機器人或研究的學生來說，同樣的組合推理能力會遷移到我們更廣泛的競賽賽道中。

BIAA 的角色

在 BIAA，我們把位元遮罩視為一項入門技能：它足夠小，能快速學會；又足夠深，能在進階動態規劃中持續帶來回報。如果你的孩子已經準備好把零散的練習轉化為穩定的組別晉級，歡迎了解我們結構化的競賽程式設計課程，並預約一次評測，找到合適的起點。