UVA 457 Linear Cellular Automata — 細胞自動機高效模擬

問題描述

給定 10 位 DNA 規則表（值 0-3），初始 40 格狀態（中央為 1，其餘 0）。每步根據左右鄰居與自身值之和作為 DNA 索引更新。模擬 50 步並輸出圖形（空格/./x/W 對應 0/1/2/3）。多測試用例。

高效實現要點

• 快速 IO：自定義緩衝讀寫（fread/fwrite）。
• 狀態轉移：原地更新，用 last 保存左鄰舊值。
• 字符映射：查表轉換，避免分支。

核心邏輯

void bacterialColonies(char *dishes) {
    for (int r = 1; r < 50; ++r) {
        int last = 0;
        for (int i = 0; i < 40; ++i) {
            int k = cToInt(dishes[i]);
            int cur = k;
            if (i == 0) k += cToInt(dishes[i+1]);
            else if (i == 39) k += last;
            else k += last + cToInt(dishes[i+1]);
            last = DNA[k];
            dishes[i] = iToChar(last);
            last = cur;
        }
        wrToBuf(dishes);
    }
}

關鍵優化

• 輸入用 intFromBuf 直接解析整數，避免 scanf 開銷。
• 輸出累積緩衝區達閾值再 fwrite。
• 狀態數組固定大小 40，循環展開極快。

複雜度

• 時間：O(T × 50 × 40)，常數極小，0.015s 通過。
• 空間：O(1)。

總結

本題計算量小，核心在於 IO 優化與狀態轉移的無分支實現。展示了競技編程中「快速 IO + 緊湊循環」的實戰技巧。