HDU 5077 NAND 題解：暴力打表 + DFS 剪枝

題目大意

輸入三個二進制變量 x1, x2, x3，需構造 8 輸出位（對應 8 種輸入組合）。允許操作：NAND（兩輸入可為變量、常數或前序結果）與 return（輸出某變量）。求生成給定 8 位輸出所需的最少代碼行數。

解題思路：離線打表

輸入僅 8 位，共 2⁸ = 256 種可能輸出模式。可預先對所有 256 種模式離線計算最少行數，線上直接查表輸出。

DFS 搜索策略

• 狀態：當前已有變量集合（初始含 x1, x2, x3, 0, 1）。
• 每步從集合中選兩個變量做 NAND，產生新變量加入集合。
• 目標：集合中包含目標 8 位模式（作為某變量的值）。
• 剪枝：
  1. 變量值去重：集合中不保留重複值。
  2. 層級去重：同一深度不重複嘗試相同值對。
  3. 利用對稱性：NAND(a,b) = NAND(b,a)，強制 a ≤ b。

打表結果

預計算得到長度 256 的數組 ans[pattern]，線上讀入 8 字符串轉為整數 idx，輸出 ans[idx]。

複雜度

• 離線搜索：狀態空間極小（變量值僅 256 種），DFS 瞬間完成。
• 線上查詢：O(1)。

參考代碼核心

const int ans[256] = {1,5,6,3,6,3,7,4,7,8,4,5,4,5,4,1,6,3,7,4,7,4,9,7,8,8,7,5,7,5,7,4,7,8,4,5,8,8,7,5,8,9,5,6,8,8,5,5,4,5,4,1,7,5,7,4,8,8,5,5,5,7,6,4,7,8,8,8,4,5,7,5,8,9,8,8,5,6,5,5,4,5,7,5,4,1,7,4,8,8,5,7,5,5,6,4,8,9,8,8,8,8,5,7,11,9,8,9,8,9,8,8,5,6,5,5,5,5,6,4,8,9,8,8,8,8,8,7,8,9,9,9,9,9,10,9,5,7,6,6,6,6,7,6,9,9,10,9,10,9,10,10,7,6,7,7,7,7,9,7,5,7,6,6,7,6,7,7,5,6,2,3,6,6,4,3,6,6,7,6,7,7,9,7,6,6,4,3,7,7,7,6,5,7,7,6,6,6,7,7,5,6,6,6,2,3,4,3,6,6,7,7,7,6,9,7,6,6,7,7,4,3,7,6,5,6,6,6,6,6,7,7,8,9,5,6,5,6,2,5,2,3,4,3,4,3,7,6,5,6,2,5,2,5,4,1};

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        char s[10]; scanf("%s", s);
        int idx = 0;
        for (int i = 0; i < 8; ++i) idx = idx*2 + s[i]-'0';
        printf("%d\n", ans[idx]);
    }
    return 0;
}

總結

本題展示了「狀態空間極小 → 離線全量預計算 → 線上 O(1) 查表」的經典技巧，配合 DFS 剪枝可快速獲得全域最優解。