UVALive 5029 Encoded Barcodes：條碼解碼與前綴匹配統計

問題描述

條碼由 8 條寬窄條組成，寬條為窄條 2 倍，誤差 ±5%。寬→1，窄→0，組成 8 位 ASCII 碼。給定 N 個產品名（小寫字母），M 個查詢條碼串（每條 K 字符），解碼得字符串 S，統計有多少產品名以 S 為前綴。輸出所有查詢結果之和。

條碼解碼算法

8 個寬度值，計算平均值 `avg`。大於 `avg` 為 1，小於為 0。
由高位到低位（或低到高）組合成字節值，轉為字符。
題目保證條碼合法且解碼為小寫字母。

暴力匹配與優化

N ≤ 10000, M ≤ 2000, K ≤ 30, 總長度 ≤ 60000。
暴力：對每個查詢串 S，遍歷 N 個產品名檢查 `strstr(name, S) == name`。
最壞 O(M × N × K) ≈ 6×10^8，較緊但 C++ 優化後常能通過（實測 800ms+）。

Trie 樹優化（標準解法）

• 構建產品名 Trie，每節點存 `cnt`（以此為前綴的產品數）
• 插入時沿路 `cnt++`
• 查詢 S：沿 Trie 走，若中斷返回 0，否則返回終點節點 `cnt`
• 時間：構建 O(總長度)，查詢 O(|S|)，總體 O(總長度) ≈ 10^5 級，極快

代碼片段（暴力版）

while (scanf("%d%d", &n, &m) != EOF) {
    for (i=0; i=0; v--) if (d[v] > avg) val += bit, bit <<= 1;
            s[j] = val;
        }
        for (j=0; j

總結
本題核心有二：

條碼解碼：平均值閾值法處理 ±5% 誤差，位運算組合 ASCII
前綴統計：Trie 樹是標準高效解法，暴力在數據範圍邊緣可通過但不穩定

競賽中應優先實現 Trie 樹，時間複雜度線性，且代碼模板化程度高。