ZOJ 3844: Easy Task - 模擬 + 狀態哈希檢測循環

問題描述

給定 n (≤10) 個整數，反複操作：找最大值 a 和最小值 b，將兩者替換為 a-b。直到所有數相等。問能否終止，能則輸出最終值，否則輸出 "Nooooooo!"。

關鍵洞察

操作保持數值和不變？實際和會變。但狀態空間有限（數值範圍有界）。若出現重複狀態則進入循環，無法終止。
用哈希表記錄已見狀態（以排序後的數組為鍵，或用和取模建桶）。每步排序，取首尾差替換，檢查是否全等或狀態重複。

代碼框架

vector a(n);
unordered_set seen;
while (true) {
    sort(a.begin(), a.end());
    if (a.front() == a.back()) { output a[0]; break; }
    string key = encode(a);
    if (seen.count(key)) { output "Nooooooo!"; break; }
    seen.insert(key);
    int diff = a.back() - a.front();
    a.front() = a.back() = diff;
}