NYoj 1078 漢諾塔（四）：規律、暴力模擬與二分圖匹配三解法

問題描述

有無限多個球，依次編號 1,2,3...。有若干根桿子，每次將最小編號的球放到某根桿子上，要求桿子上球的編號之和為完全平方數。求第 n 個球最多能放到第幾根桿子上（即最大桿子數）。n ≤ 50，多組測資。

三種解法對比

1. 找規律（O(1) 查詢）

手動/程序跑出前 50 個答案，發現遞推規律：

ans[1] = 1, ans[2] = 3
ans[i] = ans[i-1] + ((i+1)/2) * 2   (i ≥ 3)

預計算 ans[1..50]，查詢 O(1)。代碼極短，適合比賽快速通過。

2. 暴力模擬（貪心 + 栈）

維護每根桿子的球堆疊（用 stack）。對球編號 tmp = 1,2,3...：

1. 嘗試從第 1 根桿子開始，找第一個滿足 top + tmp = 平方數 的桿子放入。
2. 若無，開新桿子放入。
3. 記錄當桿子數達到 k 時對應的球編號 ans[k] = tmp-1。
4. 預計算至 55 根桿子覆蓋 n≤50。

複雜度極低，實測瞬間出答案。

3. 二分圖最小路徑覆蓋（出題人預期解）

建模：球為點，若兩球和為平方數連有向邊（小→大）。問題轉化為：在 DAG 中找最小路徑覆蓋，即 n - 最大匹配數。
優化：離線預處理所有平方數，邊靜態；匹配時跳過已匹配點，避免重複建圖。n=50 規模極小，匈牙利算法瞬時跑完。

參考代碼（規律法 + 暴力法 + 匹配法）

// 規律法
int ans[55];
void init_pattern() {
    ans[1]=1; ans[2]=3;
    for(int i=3;i<51;i++) ans[i]=ans[i-1]+((i+1)/2)*2;
}

// 暴力模擬
stack st[60];
int ans_brute[60];
void init_brute() {
    int tmp=1, i=1;
    while(i<55) {
        bool ok=false;
        for(i=1; !st[i].empty(); i++) {
            int sum = st[i].top() + tmp;
            int sq = sqrt(sum);
            if(sq*sq == sum) { st[i].push(tmp); ok=true; break; }
        }
        if(!ok) { st[i].push(tmp); ans_brute[i]=tmp-1; }
        tmp++;
    }
}

// 二分圖匹配（核心部分）
bool mp[1500][1500], used[1500];
int mx[1500], my[1500], ans_match[55];
bool dfs(int v) {
    for(int u=1; u55) break;
    }
}

複雜度與選擇建議

總結

NYoj 1078 以小數據範圍（n≤50）允許多種解法。比賽中優先找規律或暴力預計算；若需展示圖論建模能力，二分圖最小路徑覆蓋是標準解法。三種思路互補，掌握後可應對類似「離線預計算 + 規律/圖論」的問題。